python - 如何更快地实现贪心集覆盖？

Question

在对我的原始问题 here 进行了大量讨论后，我为 Greedy Set Cover 提出了以下实现方案.从我收到的帮助中，我将问题编码为“Greedy Set Cover”，并在收到更多帮助后 here ，我想出了以下实现。我感谢大家帮助我解决这个问题。以下实现工作正常，但我想让它可扩展/更快。

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

• 我的数据集在 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

我在 implemented 时使用了一个技巧Matlab 中著名的集合覆盖(无权重)贪心算法。您可能会以某种方式将此技巧扩展到加权情况，使用 set cardinality/set weight 而不是 set cardinality。此外，如果您使用 NumPy 库，将 Matlab 代码导出到 Python 应该非常容易。

技巧是这样的:

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