查找集线覆盖问题的最小尺寸集的算法

查找集线覆盖问题的最小尺寸集的算法

集合覆盖是NP难的，因此不可能有一种算法比查看集合的所有可能组合并检查每个组合是否是覆盖要有效得多。

基本上，先看一下1套，然后2套等的所有组合，直到形成封面为止。

编辑

这是一个示例伪代码。请注意，我并不声称这是有效的。我只是声称没有一种更有效的算法（算法会比多项式时间更糟糕，除非发现了真正很酷的东西）

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

其中

combination(K, n)

返回大小的所有可能的集合

n

，其元素来自

K

。

编辑

但是，我不太确定为什么您需要一种算法来找到最小值。在该问题中，您指出要证明集合覆盖的贪婪算法有时会找到更多集合。但这可以通过反例轻松实现（并且反例在Wikipedia条目中显示为封面）。所以我很困惑。

编辑

一个可能的实现

combination(K, n)

是：

if n == 0: return [{}] //a list containing an empty setr = []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

。好。