在对我的原始问题 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 的优化都会非常好。
最佳答案
我在 implemented 时使用了一个技巧Matlab 中著名的集合覆盖(无权重)贪心算法。您可能会以某种方式将此技巧扩展到加权情况,使用 set cardinality/set weight 而不是 set cardinality。此外,如果您使用 NumPy 库,将 Matlab 代码导出到 Python 应该非常容易。
技巧是这样的:
- (可选)我根据基数(即它们包含的元素数量)按降序对集合进行排序。我还存储了他们的基数。
- 我选择一个集合 S,在我的实现中它是最大的(即列表的第一组),我计算它包含多少未覆盖的元素。假设它包含 n 个未被覆盖的元素。
- 因为现在我知道有一个集合 S 有 n 个未覆盖的元素,我不需要处理所有基数低于 n< 的集合/em> 元素,因为它们不可能比 S 更好。所以我只需要在基数至少为 n 的集合中搜索最优集合;通过我的排序,我们可以轻松地关注它们。
关于python - 如何更快地实现贪心集覆盖?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7942312/