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])、または利用可能な最大値をカバーするもの。