9

有限集合 S と S の部分集合のリストがあるとします。次に、集合パッキング問題で、リスト内の k 個の部分集合が対素であるかどうかを尋ねます。この問題の最適化バージョンである最大セット パッキングでは、リスト内の対ごとに素なセットの最大数を求めます。

http://en.wikipedia.org/wiki/Set_packing

だから、しましょうS = {1,2,3,4,5,6,7,8,9,10}

and `Sa = {1,2,3,4}`
and `Sb = {4,5,6}`
and `Sc = {5,6,7,8}`
and `Sd = {9,10}`

この場合、対素集合の最大数は 3 ( Sa, Sc, Sd ) です。

関連するアルゴリズムに関する記事は見つかりませんでした。同じことに光を当てることができますか？

私のアプローチ：

サイズに応じてセットを並べ替えます。最小サイズのセットから始めます。次のセットの要素が現在のセットと交差しない場合、セットを結合して最大セットの数を増やします。これでよろしいでしょうか？より良いアイデアはありますか？

4

2 に答える 2

9

hivert が指摘したように、この問題は NP 困難であるため、これを行う効率的な方法はありません。ただし、入力が比較的小さい場合でも、それを引き出すことができます。結局のところ、指数関数的というのは不可能という意味ではありません。入力サイズが大きくなるにつれて、指数関数の問題はすぐに実用的ではなくなります。しかし、25 セット程度の場合は、簡単に力ずくで攻撃できます。

これが1つのアプローチです。S0、S1 、...などと呼ばれるn 個のサブセットがあるとします。サブセットのあらゆる組み合わせを試して、カーディナリティが最大のものを選択できます。2^25 = 33554432 の選択肢しかないので、おそらくこれで十分です。

これを行う簡単な方法は、厳密に 2^N 未満の非負の数がサブセットの特定の選択を表すことに注意することです。数値のバイナリ表現を見て、オンになっているビットに対応するインデックスを持つセットを選択します。したがって、数字が 11 の場合、0 番目、1 番目、3 番目のビットがオンになり、[S0、S1、S3] の組み合わせに対応します。次に、これら 3 つのセットが実際に互いに素であることを確認します。

手順は次のとおりです。

  1. i を 0 から 2^N - 1 まで繰り返す
  2. i の各値について、オンになっているビットを使用して、対応するサブセットの組み合わせを見つけます。
  3. これらのサブセットが対ごとに互いに素である場合は、この組み合わせで最良の回答を更新します (つまり、現在の最良の回答よりも大きい場合はこれを使用します)。

または、バックトラッキングを使用してサブセットを生成します。2 つのアプローチは等価であり、モジュロ実装のトレードオフです。バックトラッキングにはスタックのオーバーヘッドがいくらかありますが、途中で素性をチェックすると、計算行全体が中断される可能性があります。たとえば、S1 と S2 が互いに素でない場合、これら 2 つを含むより大きな組み合わせを気にすることはなく、時間を節約できます。反復法は、このようにそれ自体を最適化することはできませんが、ビットごとの操作とタイトなループにより、高速で効率的です。

ここで唯一重要な問題は、サブセットがペアごとに互いに素であるかどうかを確認する方法です。制約に応じて、ここでもさまざまなトリックを実行できます。

簡単なアプローチは、空のセット構造から始めて (選択した言語から必要なものを選択して)、各サブセットの要素を 1 つずつ追加することです。すでにセットにある要素にヒットした場合、少なくとも 2 つのサブセットで発生し、この組み合わせをあきらめることができます。

元のセットSにm 個の要素があり、mが比較的小さい場合、各要素を範囲 [0, m-1] にマップし、各セットにビットマスクを使用できます。したがって、m <= 64の場合、Java long を使用して各サブセットを表すことができます。サブセット内の要素に対応するすべてのビットをオンにします。これにより、ビット単位の操作の速度により、非常に高速なセット操作が可能になります。ビット単位の AND は集合の交差に対応し、ビット単位の OR は和集合です。2 つのサブセットが互いに素であるかどうかは、共通部分が空かどうかを確認することで確認できます (つまり、2 つのビットマスクを AND すると 0 になります)。

要素がそれほど多くない場合でも、設定された交差を複数回繰り返さないようにすることができます。セットがほとんどないため、最初にどのセットが互いに素であるかを事前に計算します。D[i][j] = true if i と j が素であるように、ブール行列 D を格納するだけです。次に、実際のセット操作を行うのではなく、組み合わせ内のすべてのペアを調べて、ペアごとの素性を確認します。

于 2014-03-11T00:38:30.827 に答える
3

集合パッキング問題は、最大独立集合を検索して解くことができます。問題を次のようにエンコードします。

  • 頂点を置くセットごとに
  • 2 つの頂点が共通の数を共有している場合、2 つの頂点の間にエッジを配置します。

次に、2つの関連する頂点がなければ、頂点の最大セットは必要ありません。残念ながら、これは NP 困難な問題です。既知のアルゴリズムは指数関数的です。

于 2014-03-08T21:13:42.937 に答える