dynamic-programming
行列チェーンの乗算

再帰的ソリューション

行列チェーンの乗算は、動的プログラミングを使用して解決できる最適化の問題です。一連の行列が与えられた場合、目的はこれらの行列を乗算する最も効率的な方法を見つけることです。この問題は実際には乗算を行うのではなく、関連する行列乗算のシーケンスを決定するだけです。

次元m * nとp * qの 2つの行列A ₁とA ₂があるとしましょう。行列の乗算の規則から、我々は、

1. n = pの場合にのみ、 A ₁とA _2を掛けることができます。つまり、 A ₁の列の数はA ₂の行の数と等しくなければなりません。
2. 最初の条件が満たされ、 A ₁とA _2を掛け合わせると、新しい行列が得られます。それを次元m * qの A ₃としましょう。
3. A ₁とA ₂を乗算するには、いくつかのスケーラー乗算を行う必要があります。スケーラ乗算の総数は、（ m * n * q ）または（ m * p * q ）である必要があります。
4. A ₁ * A ₂はA ₂ * A ₁と等しくない。

次元m * n 、 n * pおよびp * qをそれぞれ有する3つの行列A ₁ 、 A ₂およびA ₃を有する場合、 A ₄ = A ₁ * A ₂ * A ₃はm * qの次元を有する。今度は、この行列乗算を2つの方法で実行できます。

• まず、 A ₁とA ₂を乗算し、その結果をA ₃に乗じます。すなわち、（ A ₁ * A ₂ ）* A ₃ 。
• まず、 A ₂とA ₃を乗算し、その結果をA ₁に乗じます。すなわち、 A ₁ *（ A ₂ * A ₃ ）である。

乗算の順番は変わっていないことに気付くことができます。つまり、有効でない可能性があるため、乗算（ A ₁ * A ₃ ）* A _2をしません。 括弧を変更して剰余を掛ける前に、 括弧を変更するだけです。これらのかっこをどのように配置するかが重要です。どうして？ ₂と_3は 10 * 100、* 5 100、5 * 50です、3の寸法は_1行列 、のは、言ってみましょう。次に、

1. _{3 *（1} * _2）のために、スケーラ乗算の合計数は、（10 * 100 * 5）+（10 * 5 * 50）= 7500回。
2. A ₁ *（ A ₂ * A ₃ ）の場合、スケーラー乗算の合計数は、（ 100 * 5 * 50 ）+（ 10 * 100 * 50 ）= 75000回です。

2番目のタイプの場合、スケーラーの乗算の数は1番目のタイプの数の10倍です！したがって、合計スケーラー乗算を最小限に抑えるために必要な括弧の正しい方向を見つける方法を考案できれば、行列乗算に必要な時間とメモリーの両方が削減されます。これは行列の連鎖乗算が便利になる場所です。ここでは、行列の実際の乗算には関心がありません。スカラー乗算の数が最小になるように、正しい括弧の順序のみを調べます。私たちは行列A ₁ 、 A ₂ 、 A ₃ ... A _nを持ち、これらを乗算するのに必要なスカラー乗算の最小数を見つけるでしょう。与えられた次元が有効であると仮定します。つまり、行列の乗算の最初の要件を満たします。

この問題を解決するには、分割統治法を使用します。共通の問題のために動的プログラミングが必要です。例えば、 n = 5の場合、 5つの行列A ₁ 、 A ₂ 、 A ₃ 、 A ₄およびA _{5を有する} 。この行列乗算を実行するのに必要な乗算の最小数を求める必要があります。A ₁ * A ₂ * A ₃ * A ₄ * A ₅ 。多くの方法のうち、1つに集中しよう：（ A ₁ * A ₂ ）*（ A ₃ * A ₄ * A ₅ ）。

これについては、 A _left = A ₁ * A _2を見つけるでしょう。 _右 = ₃ * ₄ * _5。それから私たちはAの_答え = Aの_左 * Aの_権利を見つけるでしょう。 _{その答えを}見つけるために必要なスケーラ乗算の総数は：* _左 + _右 + _左を決定するために必要なスケーラ乗算の合計数を決定するために必要なスケーラ乗算の合計数を決定するために必要なスケーラ乗算の総数= A _権利 。

最後の項、のように記述することができます_右 * _左決定するために必要なスケーラ乗算の総数： _左の行数* _左の列数* _右の列数を。 （行列乗算の第2の規則に従って）

しかし、カッコを他の方法で設定することもできます。例えば：

• A ₁ *（ A ₂ * A ₃ * A ₄ * A ₅ ）
• （ A ₁ * A ₂ * A ₃ ）*（ A ₄ * A ₅ ）
• （ A ₁ * A ₂ * A ₃ * A ₄ ）* A ₅等

すべての可能なケースについて、 A _leftとA _right 、次にA _left * A _rightを求めるために必要なスケーラー乗算の数を決定します。再帰に関する一般的な考え方がある場合、このタスクの実行方法はすでに理解しています。私たちのアルゴリズムは次のようになります：

- Set parenthesis in all possible ways.
- Recursively solve for the smaller parts.
- Find out the total number of scaler multiplication by merging left and right.
- Of all possible ways, choose the best one.

なぜこれが動的プログラミング問題ですか？ （ A ₁ * A ₂ * A ₃ ）を決定するには、すでに（ A ₁ * A ₂ ）を計算しておけば、この場合に役立ちます。

この再帰の状態を判断するには、それぞれの場合について解くために、私たちが作業している行列の範囲を知る必要があることがわかります。だから、 始まりと終わりが必要です。私たちが分裂と征服を使用しているとき、私たちの基本的なケースは2つ未満の行列（ begin > = end ）を持つことになります。ここでは、何も乗算する必要はありません。 行と列の 2つの配列があります 。 row [i]とcolumn [i]は行列A _iの行数と列数を格納します。既に計算された値を格納し、 -1で初期化するdp [n] [n]配列があります。ここで-1は値がまだ計算されていないことを表します。 dp [i] [j]は、 A _i 、 A _{i + 1} 、...、 A _jを乗算するのに必要なスケーラー乗算の数を表す。擬似コードは次のようになります。

Procedure matrixChain(begin, end):
if begin >= end
    Return 0
else if dp[begin][end] is not equal to -1
    Return dp[begin][end]
end if
answer := infinity
for mid from begin to end
    operation_for_left := matrixChain(begin, mid)
    operation_for_right := matrixChain(mid+1, right)
    operation_for_left_and_right := row[begin] * column[mid] * column[end]
    total := operation_for_left + operation_for_right + operation_for_left_and_right
    answer := min(total, answer)
end for
dp[begin][end] := answer
Return dp[begin][end]

複雑：

開始および終了の値は、1からnまでの範囲とすることができます。 n ^2つの異なる状態が存在する。各状態について、内部のループはn回実行されます。合計時間複雑度： O(n³)とメモリの複雑さ： O(n²) 。