nセットの整数が与えられた場合、重複しないセットの数を最大化する方法は?
たとえば、与えられたsetsものを、
{1,2,3}
{1,4,5}
{6,7,8}
{2,3}
{8,9}
{9}
すると答えは4、
{1,4,5}, {6,7,8}, {2,3}, {9}
{1,2,3}1 は両方のセットで共通であるため、重複し{1,4,5}ないセットで構成することはできません。それはNPが聞いた問題ですか？その問題に対する効率的な解決策があれば、少し詳しく説明します。
[NB]入力セットの数は最大1000で、各セットには最大1000 個の整数が含まれます。
これは、セットがノードに対応し、少なくとも 1 つの要素を共有するセットに対応するノードがそれらの間にエッジを持つ、最大独立セットの問題です。これは NP 困難であり、一定の係数に近似することも困難です。
たとえば、整数線形計画法を使用して、まだ解決を試みることができます。
maximize: sum x[i]
for each pair of sets (i,j) that overlap: x[i] + x[j] <= 1
x[i]i 番目のセットが、検索している MIS の一部であるかどうかを示すブール値です。
この場合、答えは簡単です: セットが空でないと仮定すると、セットが元のセットの 1 つのスーパーセットではない最大セットを常に見つけることができます。最大セットであり、オーバーラップを作成せずにスーパーセットをサブセットに置き換えることができます。
ここで、{1, 2, 3} と {8, 9} は除外でき、残りの 4 つのセットは重複していません。