有没有适用于大数据集的贪心集合覆盖的好实现？

Question

这个问题是我之前在这里提到的一个相关问题的延续。@mhum建议我的问题属于覆盖问题的范畴。我尝试把我的问题转化为一个最小集合覆盖问题，目前我有一个这样的数据集：

Set        Cost
(1,2)        1
(1)          1
(1,2,3)      2
(1)          2
(3,4)        2
(4)          3
(1,2)        3
(3,4)        4
(1,2,3,4)    4

我的目标是找到一个好的集合覆盖，能够覆盖所有的数字，并且尽量减少总成本。我的数据集很大，至少有30000个集合（每个集合的大小从5到40个元素不等）。有没有什么好的贪心算法可以用来解决这个问题，还是说我得自己来实现？我对线性规划（LP）不是很精通，但任何可以解决这个问题的LP求解器（比如numpy/scipy）也可以接受。

Answer 1

我在GitHub上发布了一个用C++实现的贪心集合覆盖算法，运行时间和空间都是线性的。

https://github.com/martin-steinegger/setcover

在亚马逊AWS的m2.2xlarge实例上，计算4000万个集合，每个集合平均有10个元素，大约需要4分钟。

我还在研究一些方法来提高性能。

1. 使用MinHash去掉被更大集合覆盖的子集。
2. 去掉那些只包含一个元素且没有其他集合的所有集合。

Answer 2

有一个大家都知道的贪心算法可以用来解决集合覆盖问题，这个算法在任何你喜欢的编程语言中都很容易实现。这个算法的具体描述可以在这里找到：

http://en.wikipedia.org/wiki/Set_cover_problem#Greedy_algorithm

这个算法非常简单，最直接的办法就是从头开始写它。

值得注意的是，这是目前已知的在多项式时间内对集合覆盖问题的最佳近似算法。这意味着，如果你想要更好的最坏情况表现（也就是更小的结果集），你就需要使用运行时间不是多项式的算法（也就是对于大集合来说会很慢的算法）。

不过，维基百科的内容实际上没有涉及加权集合覆盖的问题，而这正是我们这里要讨论的。这个扩展很简单，可以在这里找到相关描述：

http://pages.cs.wisc.edu/~shuchi/courses/880-S07/scribe-notes/lecture03.pdf

还有一些有用的资料：

http://www.cs.ucr.edu/~neal/non_arxiv/Young08SetCover.pdf http://www.cs.uiuc.edu/class/sp08/cs473/Lectures/lec20.pdf