集合覆盖问题的模型与算法

  集合覆盖问题是组合最优化和理论计算机科学中的一类典型问题，它要求以最小代价将某一集合利用其若干子集加以覆盖。在现实生产生活中，集合覆盖问题有着众多应用场合，如物流配送、道路定向、工程调度、设施选址、VLSI 设计、网络安全等。遗憾的是，集合覆盖问题在算法复杂性上属于 NP-困难问题，即它不存在多项式时间精确算法，除非P=NP。因此，近似算法成为求解集合覆盖问题的一个有效途径，其中以 Chvátal 的贪心算法最为简洁。

  基集S={e1, e2, …, en}，S1,S2,…,Sm是S的一族子集，若J ⊆ \subseteq ⊆{1, 2, …, m}，且 ⋃ \bigcup ⋃Sj = S，则称{Sj}为S的一个集合覆盖。   问题：：求 S 的一个基数最小的集合覆盖，其中基数定义为集合中元素的数目。

  借鉴贪心算法来解决集合覆盖问题。贪心算法的思路为：每次选择最大长度的集合Sj来覆盖S中元素，直至S中所有元素都被覆盖。

模型IP是一个0-1规划，可以利用LINGO来解决。

  如图所示，四个平面上的圆形区域是同种型号的传感器 S1-S4 的信号覆盖范围，e1~e9 是九个服务客户，问：设置传感器的最佳方案是什么? 将9个客户视为元素，各传感器的覆盖范围内的元素分别构成集合： S1={e1,e2,e3,e4,e5} S2={e3,e4,e5,e6,e7,e8} S3={e2,e4,e5,e7,e8,e9} S4={e1,e2,e3,e4,e8,e9} 则传感器的最佳设置方案应为集合S={e1-e9}的一个基数最小的集合覆盖。

则最佳方案为设置传感器S2和S4。

  顶点覆盖问题是一个经典的图最优化问题，在算法复杂性上也属于 NP-困难问题。   设 G = (V, E) 是一个无向图，其中 V, E 分别为顶点集和边集，若存在 C ⊆ \subseteq ⊆V ，使 ∀ \forall ∀ij ∈ \in ∈E ，都有 i ∈ \in ∈C 或 j ∈ \in ∈C（即每一条边都至少有一个顶点含于 C 中），则称 C 为 G 的一个顶点覆盖。问题：求 G 的一个基数最小的顶点覆盖。   顶点覆盖问题可等价地转化为集合覆盖问题：令基集S = E ，S 的一族子集为 S1,S2,…, S|V | ，其中 Sj = { 与顶点 j关联的边 }，j = 1,2, …, |V| 。

—————————————————————— 参考文献： [1]王继强.集合覆盖问题的模型与算法[J].计算机工程与应用,2013,49(17):15-17+72.