1

多くの個別のコンポーネントを含むグラフが表示されます。各コンポーネントは2部です。A頂点を2つのセットに分散しB、2つのセット間の差が最小になるようにするにはどうすればよいですか？

例：

1：1 -> 2 ->3 -> 4 -> 5

2：6 -> 7 -> 8

最善の解決策は

A = {1, 3, 5, 7}

B = {2, 4 ,6, 8}

他の（最適ではない）解決策は

A = {1, 3, 5, 6, 8}

B = {2, 4, 7}

グラフに多くの個別の2部コンポーネントがある場合、これをどのように解決しますか？

4

2 に答える 2

3

これはパーティションの問題で、少し偽装されています。すべての2部構成要素について、独立集合の要素数の差を取ります（実際には絶対値です）。これは、分割問題への入力です。あなたの例では、それは[1,1]（（3-2）と（2-1）から）になります。

次に、ソリューションをグラフに変換し直します。数がセットS1で終わるすべてのグラフについて、大きい方のセットをA（そして小さい方をB）入れ、数がS2で終わるすべてのグラフについて、小さい方のセットを入れますA（そして大きい方をB。）この例では、解は次のようになります。 S1=[1]およびS2=[1]。関連するグラフに戻ると、例から最適なソリューションが得られます。

于 2011-04-21T11:25:54.140 に答える
2

これは、NP完全であるパー​​ティション問題のバリエーションです。

各コンポーネントについて、両側の頂点の数、たとえば[m、n]を見つけます。次に、プールAの項の合計とプールAの項の合計の差が大きくなるように、mをプールAとプールBのどちらに配置するかを決定する必要があります。プールBは最小です。

動的計画法やIPPのバリエーションによって、この種の問題を解決するための既存の手法があります。しかし、多数のコンポーネントを使用すると、NP完全性だけで運命づけられます。

于 2011-04-21T13:07:57.233 に答える