python - 贪心集覆盖算法

Question

所以，我从

如何更快地实现贪婪集覆盖？

我正在尝试理解集合和设置封面，所以我对此进行了一些修改。

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；我认为这是你应该在跳跃之前查看的情况。