グループの割り当て

Question

セットに変数を割り当てるときに問題が発生します。各セットには、それに割り当てることができる変数の制限があり、各変数は、合計セットのサブセットに割り当てることができます。

例：

• aセットにすることができAたりB
• b セットにすることができます B
• cセットにすることができAたりB
• d セットにすることができます A

したがって、A: a, d; B: b, cまたはA: c, d; B: a,b（セット内の変数の順序は重要ではありません）/を持つことができます

もちろん、すべての変数を割り当てることができない場合、複数のオプションがある場合、および1つのオプションしかない場合があります。

この問題の単純なバージョンがあるように感じますが、私はそれに指を置くことができないようです。任意のポインタをいただければ幸いです。

Answer 1

最大フローを使用して効率的に解決できます。ソースから各変数への単位容量アーク、各変数からそれが属することができる各セットへの単位容量アーク、および各セットからセットの容量に等しい容量のシンクへのアークを備えたフローネットワークを準備します。 。例えば、

ARCS

tail head capacity
------------------
s    a    1
s    b    1
s    c    1
s    d    1
a    A    1
a    B    1
b    B    1
c    A    1
c    B    1
d    A    1
A    t    2
B    t    2

積分フローを生成するお気に入りの最大フローアルゴリズムを使用し、アークを設定する変数に応じて割り当てを抽出します。

Answer 2

この問題はNP完全であり、これに対する多項式時間解がないことを意味します。この場合、バックトラッキングを使用する必要があります。

これらのリンクを見てください：

https://www.geeksforgeeks.org/vertex-cover-problem-set-1-introduction-approximate-algorithm-2/ https://www.geeksforgeeks.org/set-cover-problem-set-1-greedy-approximate-algorithm/