大数据集的贪婪集覆盖的任何良好实现？

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

有一种众所周知的用于集合封面的贪婪近似算法,它也可以用您选择的任何语言轻松实现.算法本身在这里描述:

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