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セットの計算。セットあたり10個の要素は、AmazonAWSm2.2xlargeインスタンスで計算すると約4分かかります。

私はまだパフォーマンスを改善するためにいくつかのトリックに取り組んでいます

  1. MinHashでより大きなセットでカバーされているサブセットを削除します
  2. 他のセットではない1つの要素のみを含むすべてのセットを削除します
于 2013-07-16T20:09:08.190 に答える