問題タブ [set-cover]

セット カバー アルゴリズムは、カバーするセットの最小数を見つけるためのソリューションを 1 つだけ提供する傾向があります。そのようなすべての解決策を見つけるにはどうすればよいでしょうか?

それぞれが 0 個以上のポイントを含む一連のノードがあります。ノード間には重複するポイントがありますが、各ノードにはそのノードに固有のポイントが含まれる場合があります。

例えば：

• ノード A
  • ポイント1
  • ポイント2
  • ポイント3
• ノード B
• ノード C
  • ポイント1
  • ポイント4
• ノード D
  • ポイント2

等

特定の制限まで、最大数のポイントを含むノードの最小数を見つけるアルゴリズムまたは方法はありますか?

上記の例では、4 つの一意のポイントが必要な場合、ノード A とノード C、またはノード A とノード D を取得します。

現在、ノードのリストをポイントの数で降順​​に並べ替え (ノード A、ノード C、ノード D)、ポイントを持たないノード (ノード B) を破棄することで、この問題を解決しています。次に、一意のポイントの定義されたしきい値に達するまで、そのノードのリストを反復処理し、一意のポイントをカウントします (そして、どのノードが参照されているかを記録します)。したがって、上記の例では、結果はノード A とノード C になります。

価値のあることとして、私はこれをJavascriptで行っていますが、私の質問は「問題を解決する方法」であり、特定の言語とは関係がないと思います. 投稿先が間違っていたらすみません。

Python で itertools を呼び出しています (以下を参照)。このコードでsnp_dicは、 は整数のキーとセットを値として持つ辞書です。ここでの目標は、値の和集合が集合の和集合の組み合わせであり、set_union. (これは、興味のある方のために、人気のある NP 硬グラフ理論問題セットカバーのグローバル最適解を解くことと同じです)! 以下のアルゴリズムは機能しますが、ここでの目標は最適化です。

私が目にする最も明白な最適化は itertools に関するものです。長さ r の場合、snp_dic には、union = set_union である r セットの組み合わせが存在するとします。基本確率は、この組み合わせが存在し、組み合わせ全体にわたってランダムに一様に分布している場合、平均して、このセットをカバーする組み合わせを見つけるために組み合わせを反復処理するだけでよいと予想されます。ただし、Itertools はすべての可能な組み合わせを返し、各反復でチェックすることにより set_unions をチェックする予想時間の 2 倍の時間がかかります。

論理的な解決策は、単純に itertools.combinations() をローカルに実装することです。python docs の itertools.combinations() の「同等の」python 実装に基づいていますが、 itertools.combinations は python ネイティブのものではなく C レベルの実装を呼び出すため、時間は約 2 倍遅くなります。

(最後に) 問題は、どのように itertools.combinations() の結果を 1 つずつストリーミングして、進むにつれてセット ユニオンをチェックして、 itertools.combinations の Python 実装とほぼ同じ時間で実行できるかということです。 (). 答えとして、新しいメソッドのタイミングの結果を含めて、Python ネイティブの実装と同じ時間に実行されることを証明していただければ幸いです。他の最適化も高く評価されています。

次の質問について助けが必要です。

クラスで示されている貪欲なアルゴリズムが 2 近似を提供しないセット カバー問題への入力の例を示します。

貪欲なアルゴリズム:

X - 有限集合

F - 和集合が X を与えるような X の部分集合の族

C - X をカバーする最小サイズの目的のセット。

要素を含むセットのリストが与えられた場合:

Lおよびカバーするために必要な要素のリスト:[x, y, z, ...]

和集合が list のすべての要素を含む L から集合の最小のリストを見つけますL。

この問題は Set-Cover (NP-Complete であることを意味する) と同じですか? または、これを扱いやすくするために私が見逃しているものはありますか?

要素 x がセットに存在するかどうかを一定時間で判断できると仮定します。