痛い。このアルゴリズムは間違っています。それが間違っているので証明はありません、そしてそれ故にそれが正しいことを証明することは不可能です。;）完全に削除するにはあまりにも執着しているので、ここに残しておきます。これは、「これは正しく見えます。これが機能しない可能性はありません！」と言う代わりに、アルゴリズムを正式に証明する必要がある理由の良いデモンストレーションです。
とりあえず、この解決策を証明なしで提供します。証明スケッチがありますが、この問題に最適な下部構造を証明するのに問題があります。ともかく...
問題
数値の正方形の配列が与えられた場合、選択された数値の合計が最大になるように、できるだけ多くの「重複しない」数値を選択します。「重複しない」とは、2つの数値が同じ行または同じ列からのものであってはならないことを意味します。
アルゴリズム
A数の正方形の配列にしましょうn by n。- th行とth列の
Aijの要素を示します。Aij
- 行と列の共通部分を含む
S( i1:i2, j1:j2 )正方形のサブ配列の重複しない数の最適な合計を示します。Ai1i2j1j2
次に、重複しない数値の最適な合計が示さS( 1:n , 1:n )れ、次のように与えられます。
S( 1:n , 1:n ) = max { [ S( 2:n , 2:n ) + A11 ]
[ S( 2:n , 1:n-1 ) + A1n ]
[ S( 1:n-1 , 2:n ) + An1 ]
[ S( 1:n-1 , 1:n-1 ) + Ann ] }
(recursively)
Note that S( i:i, j:j ) is simply Aij.
つまり、サイズの正方形配列の最適な合計は、サイズnの4つのサブ配列のそれぞれの最適な合計を個別に計算しn-1、サブ配列と「除外された」要素の合計を最大化することによって決定できます。 "。
S for |# # # #|
|# # # #|
|# # # #|
|# # # #|
Is the best of the sums S for:
|# | | #| |# # # | | # # #|
| # # #| |# # # | |# # # | | # # #|
| # # #| |# # # | |# # # | | # # #|
| # # #| |# # # | | #| |# |
実装
上記の再帰的アルゴリズムは、再帰的な解決策を示唆しています。
def S(A,i1,i2,j1,j2):
if (i1 == i2) and (j1==j2):
return A[i1][j1]
else:
return max ( S( A, i1+1, i2, j1+1, j2) + A[i1][j1] ],
S( A, i1+1, i2, j1, j2-1) + A[i1][j2] ],
S( A, i1, i2-1, j1+1, j2) + A[i2][j1] ],
S( A, i1, i2-1, j1, j2-1) + A[i2][j2] ], )
これにより!!がO(4^n)呼び出されることに注意してください。S()これは、「ブルートフォース」ソリューションの階乗時間計算量よりもはるかに優れていますO(n!)が、それでもパフォーマンスはひどいものです。
ここで注意すべき重要なことは、呼び出しの多くが同じパラメーターで繰り返されることです。たとえば、3 * 3配列を解く場合、各2*2配列は何度も解かれます。
これは、スピードアップのための2つの可能な解決策を示唆しています。
- 再帰関数のキャッシュ結果を作成して、各に対して1回
S()だけ必要になるようにします。これは、結果を計算するだけでよいことを意味します。他のすべてのリクエストはキャッシュから満たされます。（これはメモと呼ばれます。）S(A,i1,i2,j1,j2)i1,i2,j1,j2S()O(n^3)
- 大きな
n*n配列で上から始めて、連続して小さなサブ問題を処理する代わりに、可能な限り最小のサブ問題で下から始めて、ケースに積み上げていきます。n*nこれは動的計画法と呼ばれます。これもですが、常にキャッシュをヒットする必要がないためO(n^3)、はるかに高速です。O(n^3)
動的計画法ソリューションは、次のように進行します。
- すべての1x1サブアレイに対する最適なソリューションを見つけます。（トリビアル。）
- すべての2x2サブアレイに最適なソリューションを見つけます。
- すべての3x3サブアレイに最適なソリューションを見つけてください。
- ..。
- すべてのn-1*n-1サブアレイの最適なソリューションを見つけます。
- 完全なn*nサブアレイの最適なソリューションを見つけます。
このソリューションに関する注意：
- まだ証拠はありません。私はそれに取り組んでいます。
S()上記のアルゴリズムでは、最適な合計のみが得られることに注意してください。どの数値が実際にその合計を構成しているかはわかりません。ソリューションへのパスをバックトレースする独自の方法を追加できます。- 上記のアルゴリズムは、
2,2vs 。のような関係1,3が壊れるという特性を保証するものではなく、すべての個々の数をできるだけ大きくすることを支持します（勝つために）。最大数を支持して関係を壊すように2,2定義できると思います。max()可能であり、それはあなたが望むことをするでしょう、しかし私はそれを証明することができません。
一般的な注意事項：
動的計画法は、次の2つの特性を示す問題に対して高速アルゴリズムを考案するための強力な手法です。
- 最適な下部構造：問題はわずかに小さい部分に分割でき、それぞれが元の問題の解決策の一部として使用できます。
- サブ問題が重複しているということは、解決すべき実際のサブ問題がほとんどなく、サブ問題の解決策が何度も再利用されることを意味します。
問題に最適な部分構造があり、問題がわずかに小さい問題に分解される場合（たとえば、サイズの問題がサイズnのサブ問題に分解される場合）、問題は動的計画法n-1によって解決できます。
問題をはるかに小さなチャンクに分割できる場合（たとえば、サイズの問題nを半分に分割し、それぞれのサイズn/2）、それは分割統治法であり、動的計画法ではありません。分割統治法は一般に非常に高速です。たとえば、二分探索では、ソートされた配列内の要素がO(log n)時間内に検出されます。