7

这个问题来自我在此处发布的一个相关问题。@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）也是可以接受的。

4

2 回答 2

9

有一个众所周知的用于集合覆盖的贪婪逼近算法，它也很容易用您选择的任何语言实现。算法本身在此处描述：

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

于 2011-10-29T00:41:28.800 回答
3

我的 C++ 中贪婪集覆盖的线性时间/空间实现可在 github 上找到。

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

平均 40.000.000 套的计算。在 Amazon AWS m2.2xlarge 实例上计算每组 10 个元素大约需要 4 分钟。

我仍在研究一些技巧来提高性能

  1. 使用MinHash删除被更大集合覆盖的子集
  2. 删除所有仅包含一个元素且没有其他集合的集合
于 2013-07-16T20:09:08.190 回答