python - 贪心集覆盖算法

Question

所以，我从

中获取了这段代码

How do I make my implementation of greedy set cover faster?

我正在尝试理解布景和布景，所以我稍微修改了一下。

U = set([1,2,3,4])
R = U
S = [set([1,2]), 
     set([1]), 
     set([1,2,3]), 
     set([1]), 
     set([3]), 
     set([1,2]), 
     set([3]), 
     set([1,2,3])]
w = [1, 1, 1, 1, 1, 1, 1, 1]

C = []
costs = []

def findMin(S, R):
    minCost = 99999.0
    minElement = -1
    for i, s in enumerate(S):
        try:
            cost = w[i]/(len(s.intersection(R)))
            if cost < minCost:
                minCost = cost
                minElement = i
        except:
            # Division by zero, ignore
            pass
    return S[minElement], w[minElement]

while len(R) != 0:
    S_i, cost = findMin(S, R)
    C.append(S_i)
    R = R.difference(S_i)
    costs.append(cost)

print "Cover: ", C
#print "Total Cost: ", sum(costs), costs

可以看出，U 的值为 1,2,3,4。没有一套有 4 个。我不懂权重，所以把它们设为 1。

预期输出:set([1,2]), set([3]), set([1,2,3])，或覆盖最大可用量的东西。

Answer 1

您的代码的问题是没有覆盖，因为有一个额外的 4。我的理解是，根据定义，集合覆盖问题指定 中所有集合的并集S 必须等于 U。所以不应该有额外的 4 个。

由于您的程序在找到完美覆盖之前不会停止(即只要 len(R) != 0)，它永远不会停止在此输入上。您将无效输入传递给算法。

附带说明一下，我强烈建议不要使用笼统的 except 子句来测试零除法。这不是 try/except 的好用法；我认为在这种情况下，您应该三思而后行。