algorithm - 一种为集合覆盖问题找到最小尺寸集合覆盖的算法

Question

在集合覆盖问题中，我们给定一个宇宙 U，使得 |U|=n，集合 S1,……,Sk 是 U 的子集。集合覆盖是一些集合 C 的集合 C S1,……,Sk 的联合是整个宇宙 U。

我正试图想出一个算法来找到最小数量的集合覆盖，这样我就可以证明集合覆盖的贪心算法有时会找到更多的集合。

下面是我想出的:

对每组重复。 1.覆盖<-Seti(i=1,,,n) 2. 如果一个集合不是任何其他集合的子集，则将该集合隐藏起来。

但它在某些情况下不起作用。 请帮我想出一个算法来找到最小集合覆盖。

我仍然无法在线找到此算法。有人有什么建议吗？

Answer 1

集合覆盖是 NP-hard，因此不太可能有比查看集合的所有可能组合并检查每个组合是否为覆盖更有效的算法。

基本上，先查看 1 组、2 组等的所有组合，直到它们形成一个封面。

编辑

这是一个示例伪代码。请注意，我并不声称这是有效的。我只是声称没有更有效的算法(算法将比多项式时间更糟糕，除非发现一些非常酷的东西)

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

其中 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 执行覆盖测试。嗯。