查找Set-cover问题的最小尺寸集覆盖的算法

Question

在Set Covering问题中,我们给出了一个宇宙U,例如| U | = n,并且设置S1,......,Sk是U的子集.集合封面是来自S1的一些集合的集合C,... ......,Sk的联盟是整个宇宙U.

我正在尝试提出一种算法,该算法将找到最小数量的集合覆盖,以便我可以证明集合覆盖的贪婪算法有时会找到更多集合.

以下是我提出的:

重复每一组.1.覆盖<-Seti(i = 1 ,,, n)2.如果一个集合不是任何其他集合的子集,则将该集合置于封面.

但它在某些情况下不起作用.请帮我弄清楚找到最小集合覆盖率的算法.

我仍有问题在网上找到这个算法.有人有什么建议吗？

Answer 1

设置封面是NP难的,所以不太可能比查看所有可能的组合组合更有效,并检查每个组合是否是封面.

基本上,看看1套,然后2套等的所有组合,直到它们形成一个封面.

编辑

这是一个伪代码示例.请注意,我并不认为这是有效的.我只是声称没有更高效的算法(算法会比多项式时间更糟,除非发现真的很酷)

for size in 1..|S|:
    for C in combination(S, size):
          if (union(C) == U) return C

where combination(K, n)返回n其元素来自的所有可能的大小集K.

编辑

但是,我不太清楚为什么你需要一个算法来找到最小值.在问题中,您声明要表明集合覆盖的贪婪算法有时会发现更多集合.但这很容易通过一个反例来实现(并且在维基百科条目集中显示了一个反例).所以我很困惑.

编辑

可能的实现combination(K, n)是:

if n == 0: return [{}] //a list containing an empty set
r = []
for k in K:
    K = K \ {k} // remove k from K.
    for s in combination(K, n-1):
        r.append(union({k}, s))
return r

但结合封面问题,人们可能希望从基础案例中进行覆盖测试n == 0.好.