集合覆盖问题(Set Cover Problem)和点覆盖问题及归约

发布网友发布时间：2023-05-28 01:28

共1个回答

热心网友时间：2024-11-15 19:34

集合覆盖问题(Set Covering Problem，简称SCP)是运筹学研究中典型的组合优化问题之一，工业领域里的许多实际问题都可建模为集合覆盖问题，如资源选择问题、设施选址问题（移动基站的选址、物流中心的选址）等。

-m种软件
-我们希望我们的系统能有n个软件，集合为U（比如手机里面有视频软件，学习软件等等）
-第i种软件包含的软件为Si，且Si包含在U中（比如Si可以为视频软件的集合）
-用最少的软件分类标签去包含这所有的软件。（比如说腾讯课堂又可以归为视频软件，又可以归为学习软件）

首先想到，比如在上面的例子中，如果6在S2中，那么在S6中我们就可以不用要，不过也可以要，这就有点像点覆盖问题中的如果一个边的一个端点选到集合中去之后，另外一个端点可以不要，所以我们不难想到把点覆盖问题归约到集合覆盖问题，假设点覆盖问题是一个NP难的问题，那么集合覆盖问题也是一个NP难的问题。（*因为点覆盖能归约到集合覆盖，说明，集合覆盖比点覆盖还要难）

那么问题是怎么归约？刚刚分析了，集合覆盖似乎和点覆盖有点“像”，集合S2中有，则S6中的6可以不用有，那么我们把每个子集合当成一个顶点，如果两个子集合中都同时存在某个元素，那么就连一条边（并且是带编号的边，因为需要表明清楚共同拥有的到底是子集合中的哪个元素。在别的应用场景下可以当成权重）

参考： https://www.jianshu.com/p/247999af00ed