2023年7月29日发(作者：)

组合优化

——集合覆盖问题

摘要：

不仅介绍了特殊地集合覆盖问题的贪婪算法和证明了该算法的多项式时间的近似比，而且介绍了一般地集合覆盖问题的贪婪算法和该算法的近似比。然后，将集合覆盖应用到最短超字符串问题，并将该问题进行了推广。

关键词：集合覆盖、贪婪算法、最短超字符串问题

正文：

问题1（特殊地集合覆盖）：令U为一有限集，由U的子集构成的集族S{S1,S2,,Sk}，求S的所含集合数目最少的子集族，他能覆盖U的所有元素。

贪婪算法1：

1、C。

2、While

CU do

找SS使得|CS|最大；

CCS。

3、输出所选取的集合。

定理1：贪婪算法1是集合覆盖问题的多项式时间(1ln)-近似算法。其中表示S中所含元素数目最多的集合的势。

证明：令S1,S2,,Sg为贪婪算法按顺序挑选出来的集合。令CiSj，令OPT表示为最小集合覆盖问题的最优解。

j1i由贪婪准则，Si1是在所有剩余集合（除S1,S2,,Si集合外）中能够最多覆盖未被Ci覆盖元素的集合。

未被Ci覆盖的元素数目为|U||Ci|，而这些未被覆盖的元素被最优解中的所有集合覆盖，因此，最优解中平均每个集合可覆盖|U||Ci|个未被覆盖的元素。

OPT因此，|Ci1||Ci||U||Ci|

OPT11i1)|U|(1)

OPTOPT即，|U||Ci1|(|U||Ci|)(1又因为，1xex,x0

则，|U||Ci1||S|e(1i)/OPT

选择i使得|U||Ci1|OPT|U||Ci|

则有，giOPT，

且OPT|U|ei/OPT

因此，gOPT(1ln

|U|)OPT(1ln)

OPT问题2（一般地集合覆盖）：给定有n个元素的全域U，由U的子集构成的集族S{S1,S2,,Sk}，以及费用函数c:SQ，找S的最小费用子集族，它能覆盖U的所有元素。

贪婪算法：

贪婪策略自然地应用于集合覆盖问题：逐一地选取成本效益最小的集合并删除已被覆盖的元素，直到所有元素都被覆盖。设C是某次迭代开始时已被覆盖的元素的集合。在这次迭代中，定义集合S的成本效益是S覆盖新元素的平均费用，即c(S)/|SC|。定义元素的价格是覆盖它的平均费用。等价地，当选取集合S时，可以认为S的费用平均分配给所覆盖的新元素，这个费用就是这些新元素的价格。

贪婪算法2：

1、C。

2、While

CU do

找成本效益最小的集合，比如S。

令c(S)，即S的成本效益。

|SC|选取S，并对每个eSC，规定price(e)。

CCS。

3、输出所选取的集合。

按照算法覆盖元素的次序对U中的元素进行编号，同时被覆盖的元素可任意编号。设e1,e2,,en是这个编号。

引理1：对每个k{1,,n}，price(ek)OPT/(nk1)。

证明：令S1,S2,Sg为贪婪算法按顺序挑选出来的集合。令CiSj，OPT表示为最小集合覆盖问题的最优解。则未被Ci覆盖的j1i元素数目为|UCi|，而未被覆盖的元素可以被最优解中的所有集合覆盖，即未被覆盖的元素能以至多是OPT的费用覆盖。因此，最优解中平均每个集合的成本效益是OPT/|UCi|，从而必定存在一个成本效益至多是OPT/|UCi|的集合。在用Si1覆盖元素ek的那次迭代中，UCi至少包含nk1个元素。因为这次迭代中用成本效益最小的集合覆盖ek，所以有

price(ek)OPTOPT|UCi|nk1

定理2：贪婪算法是最小集合覆盖问题的Hn因子近似算法，这里Hn111。

2n证明：因为每个选取的集合的费用分布于新覆盖的元素中，所以选取的集合覆盖的总费用等于price(ek)。由引理1可知，这至多是k1n(111)OPT。

2n

集合覆盖的应用： 最短超字符串问题1：给定有限字母表，由n个字符串构成的集合S{s1,s2,,sn}，找包含每个si作为字符串的最短字符串s。不失一般性，可以假定任何字符串si都不是另一个字符串sj的子字符串，ji。

这个问题是NP—难解的。或许找最短超字符串所想到的第一个算法就是下述的贪婪算法。定义两个字符串s,t*的重叠是s的最大长度的后缀，这个后缀同时也是t的前缀。设T是每次迭代开始时字符串集合。

贪婪算法3：

1、TS，Nn。

2、While

N1 do

从T中选取两个有最大重叠的字符串s,t，并尽可能地重叠它们，得到字符串r，用r替代s,t。

NN1。

3、输出T中的字符串。

显然，这个字符串包含每个si作为子字符串。人们猜测这个算法有近似因子2。为了说明这个算法的近似因子不会好于2，考虑由3个字符串构成的输入：abk,bkc和bk1。如果在第一次迭代中选取前两个字符串，贪婪算法所产生的字符串为abkcbk1。这几乎是最短超字符串abk1c长度的两倍。 利用集合覆盖的贪婪算法，我们可得到最短超字符串的2Hn因子近似算法。如下构造集合覆盖的一个实例，用S表示这个实例。对si,sjS和k0，如果si的最后k个字符与sj的前k个字符相同，则设

ijk是通过重叠si和sj的这k个位置所得到的字符串，如下图1所示：

图1

设M是由字符串ijk（对i,j,k的所有有效选择）所构成的集合。对字}，符串，定义set(){sS|s是的子字符串其中set()中有且仅有唯一的元素，SM。集合覆盖实例S的全集是S，S的指定子集是所有set()（对每个字符串SM）。tes()的费用是||，即字符串的长度。

设OPT和OPT分别表示S的最优解费用和S的最短超字符串的S长度。正如下面引理2所说，OPTS和OPT在彼此的2因子以内，因此能够用集合覆盖的近似算法来得到最短超字符串的近似算法。完整的算法是：

算法4（使用集合覆盖的最短超字符串） 1、利用集合覆盖的贪婪算法找到实例S的一个覆盖。

设set(1),set(2),,set(k)是这个覆盖所选取的集合。

2、以任意次序连接字符串1,2,,k。

3、输出得到的字符串，记为s。

引理2：OPTOPTS2OPT

证明：考虑最优集合覆盖，比如{set(i)|1jl}，以任意次序连j。因接字符串i,1jl，得到一个字符串，比如s。显然，|s|OPTSj为S的每一个字符串都是某个i,1jl的子字符串，所以它们都是sj的子字符串。因此OPTS|s|OPT。

为证明第二个不等式，设s是s1,s2,,sn的最短超字符串，|s|OPT。只需给出某个费用至多是2OPT的集合覆盖。

考虑字符串s1,s2,,sn在字符串s中出现的最左边位置。因为在s1,s2,,sn中没有一个字符串是令一个字符串的子字符串，所以这n个最左边的出现位置开始于s中不同的位置。由于同样的原因，它们也结束于不同的位置。按照它们出现的最左边位置的开始次序重新对这n个字符串进行编号。同样，因为没有一个字符串是令一个字符串的子字符串，所以这也是它们的结束次序。

如图2所示： 图2

按组划分字符串s1,s2,,sn的有序列表，这个划分描述如下。每组由这个列表中邻近的字符串构成。设bi和ei分别表示第i组中第一个和最后一个字符串的下标（允许biei）。因此，b11，设e1是与s1具有重叠的字符串的最大下标（至少存在一个这样的字符串，即s1自身）。一般地，如果ein，那么取bi1ei1并用ei1表示与sb具有重叠的字符i1串的最大下标。最后，对某个tn得到etn。

对每个字符串对(sb,se)，设ki0是它们在s中出现的最左边位置ii已确定情形下的重叠部分的长度（这可能不同于它们的最大重叠）。设ibek。显然，{set(i)|1it}是S的解，它的费用是i|i|。

iii一个关键的结论是i不会重叠i2。首先对i1证明这个断言；相同的论证适用于任意的i。反证，假定1重叠3。那么sb在s中的3出现位置重叠se的出现位置。但是，sb却不会重叠sb（否则会把sb放1323入第二组）。由此推出se在sb后面结束，这与先前建立的字符串的结12束性质相矛盾。

根据这个结论，s的每个符号至多被两个i覆盖。因此，OPTSi|i|2OPT。

集合覆盖实例S中的全集的大小是n，而n是给定的最短超字符串实例中的字符串的数目。这个事实再加上引理2和定理2，可立即给出下述定理。

定理3：算法是最短超字符串问题的2Hn因子算法，这里n是给定实例中的字符串的数目。

推广一：

给定有限字母表，由n个字符串构成的集合S{s1,s2,,sn}，其中，当ij时，任何字符串si都不是另一个字符串sj的子字符串，利用集合覆盖找最短字符串，对每个字符串siS，这个最短字符串同时包含si和siR作为其子字符串。（这里sR是字符串s的倒转）

分析：

对于该问题，可以转化为：给定有限字母表，由2n个字符串构RR成的集合S{s1,s1R,s2,s2其中，当ij时，任何字符串si,,sn,sn}，都不是另一个字符串sj的子字符串，利用集合覆盖找包含每个si和siR作为子字符串的最短字符串s。

则可利用最短超字符串问题的结论，得：

定理4：算法是最短超字符串问题的2Hn因子算法，这里n是给定实例中的字符串的数目的两倍。

推广二：

给定有限字母表，由n个字符串构成的集合S{s1,s2,,sn}，其中，当ij时，任何字符串si都不是另一个字符串sj的子字符串，利用集合覆盖找最短字符串，对每个字符串siS，这个最短字符串包含每个si或者siR作为其子字符串。（这里sR是字符串s的倒转）

分析：

利用集合覆盖的贪婪算法，我们可得到最短超字符串的2Hn因子近似算法。如下构造集合覆盖的一个实例，用S表示这个实例。对si,sjS和k0，如果si的最后k个字符与sj的前k个字符相同，则设21是通过重叠si和sj的这k个位置所得到的字符串，设ijk是通过重ijk3叠siR和sj的这k个位置所得到的字符串，设ijk是通过重叠si和sRj的这4k个位置所得到的字符串，设ijk是通过重叠siR和sRj的这k个位置所得到的字符串，如下图3所示： 图3

1234设M是由字符串ijk（对i,j,k的所有有效选择）所构成的,ijk,ijk和ijkRR集合。定义SR{s1R,s2,,sn}，又对字符串，定义其中set()中有且仅有唯一的元素set(){sS|s或者sR是的子字符}，串，SSM。集合覆盖实例S的全集是S，S的指定子集是所R有set()（对每个字符串SSRM）。tes()的费用是||，即字符串的长度。必须强调的一点是：这里的覆盖的意思是若s或者sR是set()中元素的子字符串。

设OPT和OPT分别表示S的最优解费用和S的最短字符串的长S度。正如引理所说，OPTS和OPT在彼此的2因子以内，因此能够用集合覆盖的近似算法来得到最短字符串的近似算法。完整的算法是：

算法（使用集合覆盖的最短字符串）

1、利用集合覆盖的贪婪算法找到实例S的一个覆盖。

设set(1),set(2),,set(k)是这个覆盖所选取的集合。

2、以任意次序连接字符串1,2,,k。

3、输出得到的字符串，记为s。

引理：OPTOPTS2OPT

证明：考虑最优集合覆盖，比如{set(i)|1jl}，以任意次序连j。因接字符串i,1jl，得到一个字符串，比如s。显然，|s|OPTSj为S的每一个字符串或者字符串的倒转都是某个i,1jl的子字符j串，所以它们或者它们的倒转都是s的子字符串。因此OPTS|s

|OPT。RR为证明第二个不等式，设s是s1(s1R),s2(s2),,sn(sn)的最短字符串，|s|OPT。只需给出某个费用至多是2OPT的集合覆盖。

RR考虑字符串s1(s1R),s2(s2),,sn(sn)在字符串s中出现的最左边位RR置。因为在s1(s1R),s2(s2),,sn(sn)中没有一个字符串是令一个字符串的子字符串，所以这n个最左边的出现位置开始于s中不同的位置。由于同样的原因，它们也结束于不同的位置。按照它们出现的最左边位置的开始次序重新对这n个字符串进行编号。同样，因为没有一个字符串是令一个字符串的子字符串，所以这也是它们的结束次序。

如图所示： 图4

RR按组划分字符串s1(s1R),s2(s2),,sn(sn)的有序列表，这个划分描述如下。每组由这个列表中邻近的字符串构成。设bi和ei分别表示第i组中第一个和最后一个字符串的下标（允许biei）。因此，b11，设e1是与s1(s1R)具有重叠的字符串的最大下标（至少存在一个这样的字符串，即s1(s1R)自身）。一般地，如果ein，那么取bi1ei1并用ei1表示与R最后，对某个tn得到etn。

sbi1(sb)具有重叠的字符串的最大下标。i1对每个字符串对(sb(sbR),se(seR))，设ki0是它们在s中出现的最左iiii边位置已确定情形下的重叠部分的长度（这可能不同于它们的最大重叠）。设i1bieiki(2bieiki,3bieiki,4bieiki)。显然，{set(i)|1it}是S的解，它的费用是i|i|。

一个关键的结论是i不会重叠i2。首先对i1证明这个断言；相同的论证适用于任意的i。反证，假定1重叠3。那么sb(sbR)在s中33RR的出现位置重叠se(seR)的出现位置。但是，（否)sb(sb)却不会重叠sb(sb1i3322则会把sb(sbR)放入第二组）。由此推出se(seR)在sb(sbR)后面结束，这与331122先前建立的字符串的结束性质相矛盾。

根据这个结论，s的每个符号至多被两个i覆盖。因此，OPTSi|i|2OPT。

集合覆盖实例S中的全集的大小是n，而n是给定的最短超字符串实例中的字符串的数目。这个事实再加上引理和定理，可立即给出下述定理。

定理5：算法是最短超字符串问题的2Hn因子算法，这里n是给定实例中的字符串的数目。

摘录：

1、《贪婪近似算法与次模势函数》——王卫；

2、《Approximation Algorithms》——Vijay ni；