赞
踩
集合覆盖问题是组合最优化和理论计算机科学中的一类典型问题,它要求以最小代价将某一集合利用其若干子集加以覆盖。在现实生产生活中,集合覆盖问题有着众多应用场合,如物流配送、道路定向、工程调度、设施选址、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.
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。