[科普中国]-集合覆盖

集合覆盖有多个义项，它可以指集合论中的一个概念，在集合论中， 集合的覆盖推广了集合划分的概念，其定义如下，设A是集合，如果这些非空子集的并集等于A，则由A的若干非空子集构成的集合称为A的覆盖( covcring)。

集合覆盖还可以指一种典型的组合优化问题，其基本思路是：首先找出满足区域覆盖条件的点集，然后在满足区域覆盖条件的点集中找出满足条件的点。集合覆盖问题已经被广泛应用到航空的人员行程安排、电路设计、运输的车辆路线安排等领域。该问题已被证明是一个NP完全问题。

集合的覆盖与划分划分设A是非空集，称 是集合A的划分，若 是A的非空子集的集合，即 ，且满足1：

① ；

② 。

覆盖非空集A的一个覆盖C是A的非空子集的集合，即 ，满足 。

集合的覆盖与划分的区别在于：覆盖不要求各个子集两两之交为空集。

例1 设集合 ，则

(1) 是S的一个覆盖，不是划分，因为不满足划分定义中的条件①：

(2) 不是S的覆盖，更不是划分，因为B的任意一个子集均没有元素 ；

(3) 是S的覆盖，也是其划分。

任一给定集合S，其覆盖或划分，均不一定是唯一的：给定了非空集合S的一个覆盖或划分，则S唯一确定1。

优化求解问题基本介绍集合覆盖是一种优化求解问题，对很多组合数学和资源选择问题给出了漂亮的抽象模型。问题是这样的：给定一个集合s，集合P由集合S的子集到组成，集合C由集合P中的一个或多个子集组成。如果S中的每个成员都包含在C的至少一个子集中则称集合C覆盖集合S。此外，C包含的P的子集应该越少越好2。

举例图1中的点代表一组城镇。在国家建设规划的初期，需要决定在什么地方建设一些新的学校。这里有两个具体的要求：一是所有的学校都必须建在城镇上，二是从任意一个城镇出发，都应该可以在30英里的范围到到达其中的某一所学校。那么，最少需要建多少所学校呢?

这是一个典型的集合覆盖问题。对每个城镇，令为在其30英里范围内的城镇集合。建在的学校显然能够“覆盖”中的所有城镇。于是我们的问题就是，需要多少个这样的才能覆盖全国的所有城镇3。

集合覆盖问题输入：元素集合B。集合。

输出：选出的一部分集合，使其并为B。

成本：所选出的集合数量。

(在我们的例子中，集合B中的元素就是城镇。)这个问题本身很自然地引出了如下的贪心解法3。

不断重复：直到B中的所有元素都被覆盖：

选取包含未被覆盖元素的最大集合。

这是极其自然和符合直觉的。让我们看看它如何处理此前的那个小例子。首先它会在城镇建立一所学校，因为这样能覆盖最多的城镇。此后，它将进一步选择c，j以及f和g之一建立另三所学校。这样最终所需的学校总数为4。不幸的是，实际上还存在一个更好的解，那就是将学校分别建在b、e和i，如此只需要三所学校就可以覆盖所有城镇。在这里贪心方法并不是最优的!

幸运的是，贪心算法的解与最优解的距离其实并不遥远。

断言 设B有n个元素，且其最优覆盖共包含k个集合，则贪心算法所得结果最多包含个集合。

设为贪心算法中经过t次迭代后仍未覆盖的元素数量(显然)。由于这些剩余的元素能被最优的k个集合覆盖，因此，当前一定存在某个包含其中个元素的集合。这意味着，贪心策略能够使得

从而。进一步，由

“对任意，当且仅当时等号成立”

(以上不等式的正确性如图2可证)

可得

因此当时，严格小于，即再也没有未被覆盖的元素了。

贪心算法的解与实际的最优解的规模之比可能因问题输入的不同而不同，但是总小于。对于某些特定的输入，这一比例会非常接近于。我们称这一最大比值为该贪心算法的逼近因子。看起来对这样的结果应该还有很大的改进余地，但事实上这种改进的空间并不存在。目前已知的结论是，在某些广泛成立的复杂性假设之下，可以证明对以上问题不存在具有更小逼近因子的多项式时间算法3。

本词条内容贡献者为:

王海侠 - 副教授 - 南京理工大学