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

Question

在对我在这里的原始问题进行了大量讨论后，我为贪婪的集封面想出了以下实现。从我得到的帮助，我编码的问题转化为“贪婪的集合覆盖”，并得到了一些更多的帮助后，在这里，我想出了下面的实现。我感谢所有帮助我解决这个问题的人。以下实现工作正常，但我想使其可扩展/更快。

通过可扩展/更快，我的意思是说：

• 我的数据集在 S 中包含大约 50K-100K 集
• U 本身的元素数量非常少，在 100-500 的数量级
• S 中每个集合的大小可以是 0 到 40

这是我的尝试：

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

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

我不是 Python 专家，但对这段代码的任何特定于 Python 的优化都会非常好。

Answer 1

我用了一招，当我实现了著名贪心算法在Matlab机壳（没有权重）。您可以以某种方式将此技巧扩展到加权情况，使用设置基数/设置权重而不是设置基数。此外，如果您使用 NumPy 库，将 Matlab 代码导出到 Python 应该非常容易。

这是诀窍：

1. （可选）我根据基数（即它们包含的元素数）按降序对集合进行排序。我还存储了它们的基数。
2. 我选择了一个集合S，在我的实现中它是最大的（即列表的第一个集合），并且我计算它包含多少未被覆盖的元素。假设它包含n 个未覆盖的元素。
3. 因为现在我知道有一个包含n 个未覆盖元素的集合S，所以我不需要处理所有基数低于n 个元素的集合，因为它们不可能比S更好。所以我只需要在基数至少为n的集合中搜索最优集合；通过我的排序，我们可以轻松地专注于它们。