天荒地老总会明
范文一：最小集合覆盖
最小集合覆盖的启发式算法
摘 要
本文给出了一种求解集合覆盖问题的新的启发式算法，对该算法的合理性、时间复杂性以及解的精度进行了分析。主要创新点是用完备策略建立启发式算法。该方法具有一定的普遍性、可行性，可以应用到其他的NP困难问题。 关键词:最小集合覆盖;启发式算法;完备策略;NP困难问题
集合覆盖问题是NP困难问题中具有代表性的问题之一，它在模式识别、机器学习等领域中具有重要的应用。目前已有许多比较有效的启发式算法，但由于问题本身固有的难度，这些启发式算法具有各种的缺陷，本文提出的启发式算法由多个启发式策略组成，同时考虑到计算复杂度，具有一定的效果。
1 相关概念和完备策略
最小集合覆盖问题:S是一个集合，S1，S2，?，Sm是S的子集，且构成S的覆盖，即?Si=S，求最小覆盖。
例1 设S={0，1，2，3，4，5，6，7，8，9};S1={0，1，2，3，4};
S2={0，1， 5，6，7};S3={3，4，5，6，7};S4={5，6，7，9};
S5={2，8，9};S6={1，3，5，7};S7={0，4，6，8};
S8={0，3，6};S9={1，4，7}
定义1 设 NPH(NP-hard)是一个给定的 NP困难问题(例如，集合覆盖问题，TSP等)，ST是一个求解NPH的策略，如果ST的前提条件的验证以及策略的操作者都可以在多项式时间内完成，则称ST为多项式时间策略。
一般的启发式策略都是多项式时间策略，例如，集合覆盖问题，选取最大基数的集合作为覆盖中的一员;对TSP来说，选择最邻近的点构成回路等都是多项式策略。
定义2 NPH是一个NP困难问题，ST是求解NPH的一个多项式时间策略，NPHO是NPH 经过ST操作后得到的一个新的问题，如果问题NPHO的规模比问题NPH小，并且NPHO的最优解都是NPH的最优化解，则称ST为完备策略。
通俗地讲，一个完备策略是，当问题满足策略条件时，把原闸题化简成更
易解的问题，并且新问题的最优化解都是原问题的最优化解，即保留一些最优化解的策略。
在求解NP困难问题时，用完备策略既能降低问题的求解难度，又能保留最优解，所以它是求解NP困难问题的最重要的策略(如果有的话)。因此用启发式算法求解NP困难问题时，我们首先应该考虐寻找完备策略。
集合覆盖问题的完备策略:
完备策略1 如果S1，S2，?，Sm中一个集合Si=S，则选择Si作为最优覆盖中的唯一一个集合Si。
完备策略2 如果存在x?S,x只属于S1，S2，…，Sm中的一个集合Si,则选择Si作为最优化中的一个集合Si。
完备策略3 如果Si?Sj，则排出Si。
完备策略4 Sn(x)表示包含x?S集合的序号组成的集合，即Sn(x)=|x?S|，如果Sn(x) ?Sn(y)，则删除S中的元素y.
下表给出了例1的特征矩阵A，元素aij=1表示第i个集合S的元素在子集Sj中出现，aij=0表示没有出现:
表1 例1的特征矩阵
S1 S2 S3 S4 S5 S6 S7 S8 S9
(0) 1 1 0 0 0 0 1 1 0
(1) 1 1 0 0 0 1 0 0 1
(2) 1 0 0 0 1 0 0 0 0
(3) 1 0 1 0 0 1 0 1 0
(4) 1 0 1 0 0 0 1 0 1
(5) 0 1 1 1 0 1 0 0 0
(6) 0 1 1 1 0 0 1 1 0
(7) 0 1 1 1 0 1 0 0 1
(8) 0 0 0 0 1 0 1 0 0
(9) 0 0 0 1 1 0 0 0 0
|Si| 5 5 5 4 3 4 4 3 3
不难看出以上四个策略都是多项式时间策略，下面依次来证明四个策略满足定义2。
策略1显然满足定义2.
考虑策略2，当问题的实例满足策略2的条件时，即存在x?S只属于覆盖中的一个集合，不妨设x?S1，则S1一定在任何覆盖中(否则不能形成一个覆
盖)，于是S1属于任何一个最优化覆盖中，这就是说，选择S1之后求解难度降低了，但还保留着所有最优化覆盖，故策略2是完备策略。
考虑策略3，问题的实例满足策略3的条件时，即存在两个集合Si，Sj满足Si?Sj，如果一个最优覆盖含有Si之后，则在覆盖中用Sj来代替Si后仍然是一个最优化覆盖，故排出Si之后问题的难度降低了，但不增加最优化覆盖，因此策略3是完备策略。
考虑策略4，问题的实例满足策略4的条件时，即存在两个集合Sn(x)，Sn(y)满足Sn(x) ?Sn(y)，则包含x的集合都包含了y，所以覆盖x的任何一个覆盖总能覆盖y，于是删除S中的元素y之后问题的难度降低了，但并增加最优化覆盖，因此策略4是完备策略。
2 启发式算法
在上节中给出了四个完备策略，在这一节中我们给出基于完备策略的启发函数算法。
初值，COVER={Φ}，COVER0={S1，S2，?，Sm};
第一步:如果S1，S2，?，Sm中的一个集合Si=S，则COVER=COVER+{Si}，停止。
第二步:如果存在x?S,x只属于S1，S2，?，Sm中的一个集合Si，则COVER=COVER+{Si}，COVER0=COVER0-{Si}，S=S-{Si}。
第三步:如果存在两个集合Si?Sj，则COVER0=COVER0-{Si}。
第四步:如果存在两个元素x，y?S，满足Sn(x) ?Sn(y)，则S=S-{y}。
第五步:如果上述四个条件都不满足，则选择一个基数最大的集合Si，COVER=COVER+{Si}，COVER0=COVER0-{Si}，S=S-{Si}，返回第一步。
下面以例1的数据为例来详细说明本算法的求解过程。
第一步:不满足完备策略1、2、3，现在看是否满足策略4，现列出包含每个元素的集合序列:
Sn(0)=S1 S2 S7 S8 Sn(1)=S1 S2 S6 Sn(2)=S1 S5
Sn(3)=S1 S3 S6 S8 Sn(4)=S1 S3 S7 S9 Sn(5)=S2 S3 S4 S6
Sn(6)= S2 S3 S4 S6 S7 S8 Sn(7)=S2 S3 S4 S6 S9
Sn(8)=S5 S7 Sn(9)=S4 S5
由上可知存在两个元素5、7?S，满足Sn(5) ?Sn(7)，故S=S-{7}= {0、1、2、3、4、5、6、8、9}。
删除元素7后的集合序列变为:
S1={0，1，2，3，4}; S2={0，1， 5，6};S3={3，4，5，6};
S4={5，6，9};S5={2，8，9};S6={1，3，5};S7={0，4，6，8};
S8={0，3，6};S9={1，4}
第二步:不满足完备策略1、2，但满足完备策略3，即存在两个集合 S9?S1，故COVER0=COVER0-{S9}，即COVER0={S1 S2 S3 S4 S5 S6S 7S8}。
第三步:四个完备策略都不满足，所以选择基数最大的集合，在第二步删除元素7和S9后每个集合的基数变为:
?S1?=5 ?S2?=4 ?S3?=4 ?S4?=3
?S5?=3 ?S6?=3 ?S7?=4 ?S8?=3
由上可知基数最大的集合为S1，COVER=COVER+{S1}，COVER0=COVER0-{S1}，S=S-S1，即COVER={S1}，COVER0={S2 S3 S4 S5 S6
S7 S8}，S={5、6、8、9}。
将S2，S3，?，Sm中与S1中重复的元素删除掉后的结果为:
S2={5，6}，S3={5，6}，S4={5，6，9}，
S5={8，9}，S6={5}，S7={6，8}，S8={6}。
第四步:不满足完备策略1、2，但满足完备策略3，即由第三步结果可知，S2、S3、S6、S8?S4，故COVER0=COVER0-{S2，S3，S6，S8}，即COVER0= {S4，S5，S7}。
第五步:满足策略2，即元素5只属于集合S4，故COVER=COVER+{S4}，COVER0=COVER0-{S4}，S=S-{S4}，即COVER={S1 S4}，COVER0= {S5，S7}，S={8}，将S5，S7中与S4中重复的元素删除掉后的结果为:S5={8}，S7={8}。
第六步:由上一步结果可知只有元素8和包含该元素的两个集合S5，S7，故COVER=COVER+{S5}，停止，最后得到的最小覆盖是S1，S4，S5，不难看出S1，S4，S5是例1的一个最优解。
3 算法的计算复杂性与解的精度估计
下面分析本文算法的计算复杂性:
N和M分别表示集合S的基数与集合的个数
1)完备策略 1的计算复杂性为 O(NM)(
2)完备策略 2的计算复杂性为 O(NM)(
23)完备策略 3的计算复杂性为 O(NM)(
24)完备策略4的计算复杂-睦为 O(NM)(
5)“贪心”策略的计算复杂性为 O(NM)(
因此本算法的计算复杂性上界为
222T(N，M)?(O(NM)+O(NM)+O(NM)+ O(NM)(N+M) ?O(NM(N+M))
4 总结
本文以一个特定的例子详细讲解了求一个集合最小覆盖的启发式算法，
算法的核心思想就是循环不断的对集合进行扫描，判断是否符合完备策略，
然后根据完备策略的要求选出最小覆盖的集合，从而最终得到一个最优解。
参考文献
[1] 李国杰(人工智能的计算复杂性研究[J](模式识别与人工智能，1992 [2] 姜成志，金光浩(集合覆盖问题的一种启发式算法[J](黑龙江矿业学院学
报，1997
[3] 洪炳熔，叶风(集合覆盖问题的启发函数算法[J](软件学报，1998 [4] 陈端兵，黄文奇(一种求解集合覆盖问题的启发式算法[J](计算机科学，
2007
[5] 周海岩(最优集合覆盖的一种启发式算法[J](忻州师范专科学校学报，2000 [6] 宋晓晨(集合覆盖问题的遗传算法求解方法[J](黑龙江工程学院学报，2007
范文二：集合覆盖问题
组合优化 ——集合覆盖问题
摘要：
不仅介绍了特殊地集合覆盖问题的贪婪算法和证明了该算法的多项式时间的近似比，而且介绍了一般地集合覆盖问题的贪婪算法和该算法的近似比。然后，将集合覆盖应用到最短超字符串问题，并将该问题进行了推广。
关键词：集合覆盖、贪婪算法、最短超字符串问题 正文：
问题1（特殊地集合覆盖）：令U 为一有限集，由U 的子集构成的
集族S ={S1, S 2, , S k }，求S 的所含集合数目最少的子集族，他能覆盖U
的所有元素。
定理1：贪婪算法1是集合覆盖问题的多项式时间(1+ln γ) -近似算法。其中γ表示S 中所含元素数目最多的集合的势。
证明：令S 1, S 2, , S g 为贪婪算法按顺序挑选出来的集合。令
C i = S j ，令OPT 表示为最小集合覆盖问题的最优解。
j =1i
由贪婪准则，S i +1是在所有剩余集合（除S 1, S 2, , S i 集合外）中能够最多覆盖未被C i 覆盖元素的集合。
未被C i 覆盖的元素数目为|U |-|C i |，而这些未被覆盖的元素被最优解中的所有集合覆盖，因此，最优解中平均每个集合可覆盖
|U |-|C i |
个未被覆盖的元素。 OPT
因此，|C i +1|-|C i |≥
|U |-|C i |
OPT
11i +1
) ≤|U |(1-) OPT OPT
即，|U |-|C i +1|≤(|U |-|C i |)(1-又因为，1-x ≤e -x , x ≥0 则，|U |-|C i +1|≤|S |e -(1+i ) /O PT
选择i 使得|U |-|C i +1|
|U |
) ≤OPT (1+ln γ) OPT
问题2（一般地集合覆盖）：给定有n 个元素的全域U ，由U 的子
+
集构成的集族S ={S1, S 2, , S k }，以及费用函数c :S →Q ，找S 的最小
费用子集族，它能覆盖U 的所有元素。
贪婪算法：
贪婪策略自然地应用于集合覆盖问题：逐一地选取成本效益最小的集合并删除已被覆盖的元素，直到所有元素都被覆盖。设C 是某次迭代开始时已被覆盖的元素的集合。在这次迭代中，定义集合S 的成本效益是S 覆盖新元素的平均费用，即c (S ) /|S -C |。定义元素的价格是覆盖它的平均费用。等价地，当选取集合S 时，可以认为S 的费用平均分配给所覆盖的新元素，这个费用就是这些新元素的价格。
按照算法覆盖元素的次序对U 中的元素进行编号，同时被覆盖的元素可任意编号。设e 1, e 2, , e n 是这个编号。
引理1：对每个k ∈{1, , n }，price (e k ) ≤OPT /(n -k +1) 。
证明：令S 1, S 2, S g 为贪婪算法按顺序挑选出来的集合。令
C i = S j ，OPT 表示为最小集合覆盖问题的最优解。则未被C i 覆盖的
j =1i
元素数目为|U -C i |，而未被覆盖的元素可以被最优解中的所有集合覆盖，即未被覆盖的元素能以至多是OPT 的费用覆盖。因此，最优解中平均每个集合的成本效益是OPT /|U -C i |，从而必定存在一个成本效益至多是OPT /|U -C i |的集合。在用S i +1覆盖元素e k 的那次迭代中，
U -C i 至少包含n -k +1个元素。因为这次迭代中用成本效益最小的集
合覆盖e k ，所以有
price (e k ) ≤
OPT OPT
≤
|U -C i |n -k +1
定理2：贪婪算法是最小集合覆盖问题的H n 因子近似算法，这里
H n =1+
11+ +。 2n
证明：因为每个选取的集合的费用分布于新覆盖的元素中，所以选取的集合覆盖的总费用等于∑price (e k ) 。由引理1可知，这至多是
k =1n
(1+
11
+ +) OPT 。 2n
集合覆盖的应用：
最短超字符串问题1：给定有限字母表∑，由n 个字符串构成的集合S ={s 1, s 2, , s n }?∑+，找包含每个s i 作为字符串的最短字符串s 。不失一般性，可以假定任何字符串s i 都不是另一个字符串s j 的子字符串，j ≠i 。
这个问题是NP —难解的。或许找最短超字符串所想到的第一个算法就是下述的贪婪算法。定义两个字符串s , t ∈∑*的重叠是s 的最大长度的后缀，这个后缀同时也是t 的前缀。设T 是每次迭代开始时字符串集合。
显然，这个字符串包含每个s i 作为子字符串。人们猜测这个算法有近似因子2。为了说明这个算法的近似因子不会好于2，考虑由3个字符串构成的输入：ab k , b k c 和b k +1。如果在第一次迭代中选取前两个字符串，贪婪算法所产生的字符串为ab k cb k +1。这几乎是最短超字符串ab k +1c 长度的两倍。
利用集合覆盖的贪婪算法，我们可得到最短超字符串的2H n 因子
近似算法。如下构造集合覆盖的一个实例，用S 表示这个实例。对
s i , s j ∈S 和k >0，如果s i 的最后k 个字符与s j 的前k 个字符相同，则设
σijk 是通过重叠s i 和s j 的这k 个位置所得到的字符串，如下图1所示：
图1
设M 是由字符串σijk （对i , j , k 的所有有效选择）所构成的集合。对字
}，符串π∈∑+，定义set (π) ={s ∈S |s 是π的子字符串其中set (π) 中有且仅有
唯一的元素π，π∈S ?M 。集合覆盖实例S 的全集是S ，S 的指定子
集是所有set (π) （对每个字符串π∈S ?M ）。t e s (π) 的费用是|π|，即字符串π的长度。
设OPT 和OPT 分别表示S 的最优解费用和S 的最短超字符串的
S
长度。正如下面引理2所说，OPT S 和OPT 在彼此的2因子以内，因此能够用集合覆盖的近似算法来得到最短超字符串的近似算法。完整的算法是：
引理2：OPT ≤OPT S ≤2?OPT
证明：考虑最优集合覆盖，比如{set (πi ) |1≤j ≤l }，以任意次序连
j
。因接字符串πi , 1≤j ≤l ，得到一个字符串，比如s 。显然，|s |=OPT S
j
为S 的每一个字符串都是某个πi , 1≤j ≤l 的子字符串，所以它们都是s
j
的子字符串。因此OPT S =|s |≥OPT 。
为证明第二个不等式，设s 是s 1, s 2, , s n 的最短超字符串，
|s |=O P T 。只需给出某个费用至多是2?OPT
的集合覆盖。
考虑字符串s 1, s 2, , s n 在字符串s 中出现的最左边位置。因为在
s 1, s 2, , s n 中没有一个字符串是令一个字符串的子字符串，所以这n 个
最左边的出现位置开始于s 中不同的位置。由于同样的原因，它们也结束于不同的位置。按照它们出现的最左边位置的开始次序重新对这
n 个字符串进行编号。同样，因为没有一个字符串是令一个字符串的
子字符串，所以这也是它们的结束次序。 如图2所示：
图2
按组划分字符串s 1, s 2, , s n 的有序列表，这个划分描述如下。每组由这个列表中邻近的字符串构成。设b i 和e i 分别表示第i 组中第一个和最后一个字符串的下标（允许b i =e i ）。因此，b 1=1，设e 1是与s 1具有重叠的字符串的最大下标（至少存在一个这样的字符串，即s 1自身）。一般地，如果e i
i +1
串的最大下标。最后，对某个t ≤n 得到e t =n 。
对每个字符串对(s b , s e ) ，设k i >0是它们在s 中出现的最左边位置
i
i
已确定情形下的重叠部分的长度（这可能不同于它们的最大重叠）。设πi =σb e k 。显然，{set (πi ) |1≤i ≤t }是S 的解，它的费用是∑i |πi |。
i i i
一个关键的结论是πi 不会重叠πi +2。首先对i =1证明这个断言；
相同的论证适用于任意的i 。反证，假定π1重叠π3。那么s b 在s 中的
3
出现位置重叠s e 的出现位置。但是，s b 却不会重叠s b （否则会把s b 放
1
3
2
3
入第二组）。由此推出s e 在s b 后面结束，这与先前建立的字符串的结
1
2
束性质相矛盾。
根据这个结论，s 的每个符号至多被两个πi 覆盖。因此，
≤OPT S ∑i |πi |≤2?OPT
。
集合覆盖实例S 中的全集的大小是n ，而n 是给定的最短超字符
串实例中的字符串的数目。这个事实再加上引理2和定理2，可立即给出下述定理。
定理3：算法是最短超字符串问题的2H n 因子算法，这里n 是给定实例中的字符串的数目。 推广一：
给定有限字母表∑，由n 个字符串构成的集合S ={s 1, s 2, , s n }?∑+，其中，当i ≠j 时，任何字符串s i 都不是另一个字符串s j 的子字符串，利用集合覆盖找最短字符串，对每个字符串s i ∈S ，这个最短字符串同时包含s i 和s i R 作为其子字符串。（这里s R 是字符串s 的倒转） 分析：
对于该问题，可以转化为：给定有限字母表∑，由2n 个字符串构
R R
成的集合S ={s 1, s 1R , s 2, s 2其中，当i ≠j 时，任何字符串s i , , s n , s n }?∑+，
都不是另一个字符串s j 的子字符串，利用集合覆盖找包含每个s i 和s i R 作为子字符串的最短字符串s 。
则可利用最短超字符串问题的结论，得：
定理4：算法是最短超字符串问题的2H n 因子算法，这里n 是给定实例中的字符串的数目的两倍。 推广二：
给定有限字母表∑，由n 个字符串构成的集合S ={s 1, s 2, , s n }?∑+，其中，当i ≠j 时，任何字符串s i 都不是另一个字符串s j 的子字符串，利用集合覆盖找最短字符串，对每个字符串s i ∈S ，这个最短字符串包含每个s i 或者s i R 作为其子字符串。（这里s R 是字符串s 的倒转） 分析：
利用集合覆盖的贪婪算法，我们可得到最短超字符串的2H n 因子
近似算法。如下构造集合覆盖的一个实例，用S 表示这个实例。对
s i , s j ∈S 和k >0，如果s i 的最后k 个字符与s j 的前k 个字符相同，则设
21
是通过重叠s i 和s j 的这k 个位置所得到的字符串，设σijk 是通过重σijk
3叠s i R 和s j 的这k 个位置所得到的字符串，设σijk 是通过重叠s i 和s R j 的这4k 个位置所得到的字符串，设σijk 是通过重叠s i R 和s R j 的这k 个位置所得
到的字符串，如下图3所示：
图3
1234
设M 是由字符串σijk （对i , j , k 的所有有效选择）所构成的, σijk , σijk 和σijk R R 集合。定义S R ={s 1R , s 2, , s n }，又对字符串π∈∑+，定义
其中set (π) 中有且仅有唯一的元素set (π) ={s ∈S |s 或者s R 是π的子字符}，串
π，π∈S ?S ?M 。集合覆盖实例S 的全集是S ，S 的指定子集是所
R
有set (π) （对每个字符串π∈S ?S R ?M ）。t e s (π) 的费用是|π|，即字符串π的长度。必须强调的一点是：这里的覆盖的意思是若s 或者s R 是
set (π) 中元素的子字符串。
设OPT 和OPT 分别表示S 的最优解费用和S 的最短字符串的长
S
度。正如引理所说，OPT S 和OPT 在彼此的2因子以内，因此能够用集合覆盖的近似算法来得到最短字符串的近似算法。完整的算法是：
引理：OPT ≤OPT S ≤2?OPT
证明：考虑最优集合覆盖，比如{set (πi ) |1≤j ≤l }，以任意次序连
j
。因接字符串πi , 1≤j ≤l ，得到一个字符串，比如s 。显然，|s |=OPT S
j
为S 的每一个字符串或者字符串的倒转都是某个πi , 1≤j ≤l 的子字符
j
串，所以它们或者它们的倒转都是s 的子字符串。因此OPT S =|s |≥OPT 。
R R
为证明第二个不等式，设s 是s 1(s 1R ), s 2(s 2), , s n (s n ) 的最短字符串，
|s |=OPT 。只需给出某个费用至多是2?OPT 的集合覆盖。
R R 考虑字符串s 1(s 1R ), s 2(s 2), , s n (s n ) 在字符串s 中出现的最左边位R R
置。因为在s 1(s 1R ), s 2(s 2), , s n (s n ) 中没有一个字符串是令一个字符串的
子字符串，所以这n 个最左边的出现位置开始于s 中不同的位置。由于同样的原因，它们也结束于不同的位置。按照它们出现的最左边位置的开始次序重新对这n 个字符串进行编号。同样，因为没有一个字符串是令一个字符串的子字符串，所以这也是它们的结束次序。 如图所示：
图4
R R
按组划分字符串s 1(s 1R ), s 2(s 2), , s n (s n ) 的有序列表，这个划分描述如
下。每组由这个列表中邻近的字符串构成。设b i 和e i 分别表示第i 组中第一个和最后一个字符串的下标（允许b i =e i ）。因此，b 1=1，设e 1是与s 1(s 1R ) 具有重叠的字符串的最大下标（至少存在一个这样的字符串，即s 1(s 1R ) 自身）。一般地，如果e i
R
最后，对某个t ≤n 得到e t =n 。 s b i +1(s b ) 具有重叠的字符串的最大下标。i +1
对每个字符串对(s b (s b R ), s e (s e R )) ，设k i >0是它们在s 中出现的最左
i
i
i
i
边位置已确定情形下的重叠部分的长度（这可能不同于它们的最大重叠）。设πi =σ
1
b i e i k i
(σ
2b i e i k i
, σ
3b i e i k i
, σ
4b i e i k i
) 。显然，{set (πi ) |1≤i ≤t }是S 的解，
它的费用是∑i |πi |。
一个关键的结论是πi 不会重叠πi +2。首先对i =1证明这个断言；
相同的论证适用于任意的i 。反证，假定π1重叠π3。那么s b (s b R ) 在s 中
3
3
R R
的出现位置重叠s e (s e R ) 的出现位置。但是，（否) s b (s b ) 却不会重叠s b (s b
1
i
3
3
2
2
则会把s b (s b R ) 放入第二组）。由此推出s e (s e R ) 在s b (s b R ) 后面结束，这与
3
3
1
1
2
2
先前建立的字符串的结束性质相矛盾。
根据这个结论，s 的每个符号至多被两个πi 覆盖。因此，
≤OPT S ∑i |πi |≤2?OPT
。
集合覆盖实例S 中的全集的大小是n ，而n 是给定的最短超字符
串实例中的字符串的数目。这个事实再加上引理和定理，可立即给出下述定理。
定理5：算法是最短超字符串问题的2H n 因子算法，这里n 是给定实例中的字符串的数目。
摘录：
1、《贪婪近似算法与次模势函数》——王卫； 2、《Approximation Algorithms》——Vijay V.Vazirani；
范文三：最大覆盖模型
中国科学院研究生院
2012年招收攻读硕士学位研究生入学统一考试试题
科目名称：遥感概论
考生须知：
1．本试卷满分为150分，全部考试时间总计180分钟。
2．所有答案必须写在答题纸上，写在试题纸上或草稿纸上一律无效。
一.名词解释（每题5分，共40分）
1. 遥感平台 2. SAR 3. 直方图 4. 光谱反射曲线
5. 镜面反射 6. 维恩位移定律 7. 比辐射率 8.辐射亮度
二.简答题（每题10分，共50分）
1. 阐述瑞利散射和米氏散射的特点？
2. 存储与分发多波段数字图像时，通常采用哪几种数据格式？请分别介绍其数据排列方法。
3. 简述几何校正时重采样的方法有哪些？
4. 简要说明植被指数为什么可以突出植被信息？
5. 简要对比中值滤波和均值滤波的特点。
三.论述题（每题20分，共60分）
1. 什么是数据融合？以洪水监测为例说明数据融合的意义。
2. 说明遥感图像分辨率（空间、波谱、辐射及时间分辨率）的含义及其在遥感应用中的意义。
3. 试比较监督分类和非监督分类方法的特点，并举例说明监督分类的过程。
科目名称：遥感概论 第1页 共1页
范文四：最大覆盖问题研究
最大覆盖问题研究
摘要 最大覆盖问题是运筹学中一个经典组合优化问题。通常是
现实生活中邮政服务站点，加油站点，银行选址等问题的数学抽象。
最大覆盖问题一般被描述为有被服务点若干，选取若干服务点对被
服务点进行服务的最小代价。最大覆盖问题已经被证明是一类np
问题，也就是不能在多项式时间内求得最优值的问题。目前国内外
学者对于此问题的研究多是使用遗传，蚁群，退火模拟等启发式搜
索求的近似值的方法来进行讨论。本文主要分析了最大覆盖问题的
穷举解法，剪枝搜索解法和启发式搜索解法。对这三种解法进行了
测试，比较算法的优劣和适用范围。通过提出对于待选边进行性价
比的计算，设计出启发式函数来搜索近似最优值，最后的测试将近
似最优值保持在平均2的差异值范围内。
关键词 最大覆盖问题；穷举解法；剪枝搜索解法；启发式搜索解
法
中图分类号tp39 文献标识码a 文章编号 1674-6708
（2011）55-0218-02
1 问题描述
1.1 具体问题
最大覆盖问题是现实生活中对邮政站点，加油站点，银行等一系
列选址问题的数学抽象。一般被描述为有被服务点若干，选取若干
服务点对被服务点进行服务的最小代价。
范文五：最大覆盖问题算法设计
最大覆盖问题
问题描述:
给定n个整数a1,a2,...,an组成的序列。如果对于i <= k=""><= j=""><=|aj|， 则称aj覆盖序列区间ai,ai+1,...,aj相应的覆盖区间长度为j-i+1。="">
最大覆盖问题要求给定序列的最大覆盖区间长度L，即:
L=max{j-i+1 | ak<=|aj|,><><=j}><><><=n>
例如，当n=10，相应序列为:1，6，2，1，-2，3，5，2，-4，3 时，L=5。 算法设计:
给定n 个整数a1,a2,...,an组成的序列，试设计一个O(n)时间算法，计算其最大覆盖区间
长度。
数据输入:
由文件input.txt 提供输入数据。文件的第1 行是正整数n，第2 行是整数序列
a1,a2,...,an 。
结果输出:
将计算出的最大覆盖区间长度输出到output.txt中。
输入文件示例 input.txt
10
1 6 2 1 -2 3 5 2 -4 3
输出文件示例 output.txt
5
问题分析:本题就是在n个数中，找出“按绝对值递增的子序列”的最大长度。
因此在解决此问题时，总是预先对每个数求绝对值。
此外本题目只要求我们求出最大的长度，至于怎么求，求解过程改变的东西我们可以完全不理会。
下面是我的做法:
先把在自己(a[i])前面且比自己小的数设置为与自己一样的值;当然很容易就可以想到，从后到前进行此操作是最理想的。
经过上述的操作之后，我们就能很容易的把问题转化为“找相同连续数字的最大长度”了。
这也是非常简单的，只需一次扫描数组就能计算结束了。
因此上述的解法的时间复杂度就为O(n)
代码: //最大覆盖问题的O(n)解
#include #include using namespace std; #define N 100000 int a[N]; int main() { int n,i,j,m; freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); while(cin>>n) { if(!n)break; for(i=0;i { scanf("%d",&a[i]); if(a[i]<0)a[i]=-a[i];> } for(i=n-1;i>0;i--)//将自己前面且比自己小的数设置为自己的值 { if(a[i]>a[i-1]) a[i-1]=a[i]; } m=1; for(i=0;i { for(j=i+1;j if(j-i>m)m=j-i; i=j; } printf("%d\n\n",m); } return 0; }
