ここに別の動的プログラミングの質問があります（Vazirani ch6）
次の 3-PARTITION 問題を考えてみましょう。整数 a1...an が与えられたとき、{1...n} を次のように 3 つの互いに素な部分集合 I、J、K に分割できるかどうかを判断したいと考えています。
合計(I) = 合計(J) = 合計(K) = 1/3*合計(すべて)
たとえば、入力 (1; 2; 3; 4; 4; 5; 8) の場合、パーティション (1; 8)、(4; 5)、(2; 3; 4) があるため、答えは「はい」です。一方、入力 (2; 2; 3; 5) の場合、答えはノーです。n と (Sum a_i) の時間多項式で実行される 3-PARTITION の動的計画法のアルゴリズムを考案して解析します。
どうすればこの問題を解決できますか? 2パーティションは知っていますが、まだ解決できません
2 セットの解を 3 セットの場合に一般化するのは簡単です。
元のバージョンでは、ブール値の配列を作成しますsums。ここで、セットの数値でsums[i]合計iに到達できるかどうかを示します。次に、配列が作成されると、それsums[TOTAL/2]がどうかを確認しますtrue。
古いバージョンは既に知っているとのことでしたので、両者の違いについてのみ説明します。
3 パーティションの場合、 boolean の配列を保持しますsums。ここで、sums[i][j]最初のセットが sumiと second-sumを持つことができるかどうかを示しjます。次に、配列が作成されると、それsums[TOTAL/3][TOTAL/3]がどうかを確認しますtrue。
元の複雑さが である場合O(TOTAL*n)、ここではO(TOTAL^2*n)です。
厳密な意味では多項式ではないかもしれませんが、元のバージョンも厳密には多項式ではありません:)
削減すると、次のようになると思います。
2 パーティションから 3 パーティションへの縮小:
S を元のセット、A をその総和とすると、S'=union({A/2},S) とします。したがって、セット S' に対して 3 分割を実行すると、3 つのセット X、Y、Z が生成されます。X、Y、Z のうち、そのうちの 1 つが {A/2} である必要があります。 2分割。S' 上の 3 パーティションの証人は、S 上の 2 パーティションの証人であるため、2 パーティションは 3 パーティションに縮小されます。
この問題が解決可能である場合。sum(ALL)/3整数でなければなりません。どのソリューションにも が必要SUM(J) + SUM(K) = SUM(I) + sum(ALL)/3です。これは 上の 2 分割問題の解を表していconcat(ALL, {sum(ALL)/3})ます。
あなたは2パーティションの実装を持っていると言います:それを使ってその問題を解決してください。次に、(少なくとも) 2 つのパーティションの 1 つに番号が含まれます。そのパーティションsum(ALL)/3から番号を削除すると、I. もう一方のパーティションについては、2-partition を再度実行して、から分割JしKます。結局のところ、合計自体が等しくなければなりませんJ。K
編集：この解決策はおそらく間違っています - 連結セットの2分割にはいくつかの解決策があります（I、J、Kのそれぞれに少なくとも1つ） - しかし、他の解決策がある場合、「反対側」はそうではないかもしれませんI、J、K の 2 つの結合で構成され、まったく分割できない場合があります。あなたは実際に考える必要があるでしょう、私は恐れています:-)。
試行 2:次のマップを維持しながら、マルチセットを反復処理します。、、R(i,j,k) :: Booleanを持つ 3 つのマルチセットに分割できるかどうかを表します。つまり、次の状態の任意の次の数andと を 保持します。複雑さ (excersize による) は、入力数値の大きさに依存することに注意してください。これは疑似多項式時間アルゴリズムです。Nikita のソリューションは概念的には似ていますが、3 番目のセットの合計を追跡しないため、このソリューションよりも効率的です。簡単に計算できるため、これは不要です。ijkR(i,j,k)nR'R'(i+n,j,k)R'(i,j+n,k)R'(i,j,k+n)
セット$X = {x_1, ..., x_n}$を$k$パーティションに分割するとします。$ n \ timesk$テーブルを作成します。コストが$j$パーティション内$M[i,j]$の要素の最大合計であると想定します。$i$次の最適性基準を再帰的に使用して、それを埋めます。
M[n,k] = min_{i\leq n} max ( M[i, k-1], \sum_{j=i+1}^{n} x_i )
Using these initial values for the table:
M[i,1] = \sum_{j=1}^{i} x_i and M[1,j] = x_j
The running time is $O(kn^2)$ (polynomial )
Korf の完全な Karmarkar-Karp アルゴリズム ( http://ac.els-cdn.com/S0004370298000861/1-s2.0-S0004370298000861-main.pdf、http://ijcai.org/papers09/Papers/IJCAI09- 096.pdf )。3分割への一般化が与えられます。このアルゴリズムは、問題の複雑さを考えると驚くほど高速ですが、実装が必要です。
KK の基本的な考え方は、同様のサイズの大きなブロックが異なるパーティションに表示されるようにすることです。ブロックのペアをグループ化すると、通常どおり配置できるサイズの差に等しいサイズの小さなブロックとして扱うことができます。これを再帰的に行うと、配置しやすい小さなブロックになります。次に、反対の配置が確実に処理されるように、ブロック グループを 2 色で塗りつぶします。3 パーティションへの拡張は少し複雑です。Korf 拡張機能は、KK 順序で深さ優先探索を使用して、可能なすべての解を見つけるか、解をすばやく見つけることです。