Matrix Chain Multiplication
行列の連鎖は dims で表されます。行列 i は dims[i] 行 dims[i+1] 列を持つため、各行列は次の行列と適合します。p × q 行列と q × r 行列の乗算には p × q × r 回のスカラー乗算が必要で、結果は p × r 行列になります。括弧の付け方をどう変えても最終的な積は同じですが、計算コストは同じとは限りません。連鎖全体の乗算に必要なスカラー乗算の最小回数を返してください。
関数
- dimsinteger-array
- 連鎖に沿ったサイズ：行列 i は dims[i] × dims[i+1] です
- 戻り値integer
- 連鎖全体を乗算するために必要なスカラー乗算の最小回数
制約
2 ≤ dims.length ≤ 100なので、連鎖には1〜99個の行列が含まれます。1 ≤ dims[i] ≤ 100- 答えは最大でも 98 × 106 であり、32 ビット符号付き整数の範囲内に十分収まります。
例
- 入力
- dims = [4, 10, 3, 12]
- 出力
- 264
- 説明
- 最初の2つを掛けると 4 × 10 × 3 = 120 となり、4 × 3 行列が残ります。これに 3 × 12 行列を掛けると 144 が加わり、合計は 264 です。もう一方の順序では 360 + 480 = 840 かかります。
- 入力
- dims = [6, 2, 7, 3, 5]
- 出力
- 132
- 説明
- 2 × 7 に 7 × 3 を掛け（42）、2 × 3 の結果に 3 × 5 を掛け（30）、次に 6 × 2 に 2 × 5 の結果を掛けます（60）。合計は 132 です。
- 入力
- dims = [3, 7]
- 出力
- 0
- 説明
- 行列は 3 × 7 の1つだけなので、何も乗算されず、コストは 0 です。
発展問題
最小コストを実現する異なる括弧の付け方の数も数えられますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
最初の掛け算は忘れて、最後の掛け算について考えましょう。どの順序を選んでも、最後のステップでは、連鎖の左側の一部の積と残りの部分の積を掛け合わせます。
2つの境界
leftとrightの間の行列の積は、常にdims[left] × dims[right]行列になります。したがって、最後のステップでその区間を境界splitで分割する場合、コストはdims[left] × dims[split] × dims[right]となり、2つの部分は同じ問題のより小さなものになります。境界
leftとrightの間にある行列を乗算する最もコストの低い方法をbest[left][right]に格納します（行列が1つの場合は0）。これは、それらの間にあるすべてのsplitについて、best[left][split] + best[split][right] + dims[left] × dims[split] × dims[right]の最小値です。幅の狭い区間から幅の広い区間へと計算します。
解説
順序によってコストが変わります。最初の例では、840に対して264です。最後の乗算に注目してください。これは、連鎖の左側部分と右側部分の積を結合します。それぞれの部分は、より短い連鎖に対する同じ問題です。連鎖の区間ごとの表を使えば、それぞれを一度ずつ、O(n³)時間で解けます。
単純な再帰ですべての分割を試す
正しいが、最大のテストでは終わらない
考え方
連鎖の境界に 0 から m-1 まで番号を付けます。ここで m = dims.length です。境界 k のサイズは dims[k] です。境界 left と right の間にある行列をどの順序で掛け合わせても、dims[left] × dims[right] の行列になります。したがって、その範囲を最後のステップで split の位置に分割する場合、2つのブロックの内部で何が起きたかに関係なく、コストは dims[left] × dims[split] × dims[right] です。それぞれのブロックは可能な限り低コストで構築する必要があるため、cheapest(left, right) は、すべての split について、両ブロックのコストと最後のステップのコストを足した値のうち最小のものです。最後のステップをすべて試すことで、正しい結果が得られます。
同じ範囲を何度も解き直します。行列が n 個の場合、呼び出し回数は 3^(n-1) となり、行列が20個なら約 1.2 × 10^9 回です。一方、異なる範囲は約 m²/2 個しかありません。
アルゴリズム
- 境界が
leftとrightの間にある行列について、cheapest(left, right)を記述します。 right - left < 2の場合、行列は1つです。0を返します。- それらの間にあるすべての
splitについて、cheapest(left, split)、cheapest(split, right)、およびdims[left] × dims[split] × dims[right]を加算します。 - 最小の合計を返します。
- 答えは
cheapest(0, m-1)です。
def matrixChainOrder(dims):
def cheapest(left, right):
# The fewest multiplications for the matrices between boundaries left and right
if right - left < 2:
return 0 # a single matrix costs nothing
best = None
for split in range(left + 1, right):
cost = (cheapest(left, split) + cheapest(split, right)
+ dims[left] * dims[split] * dims[right])
if best is None or cost < best:
best = cost
return best
return cheapest(0, len(dims) - 1)メモを使った再帰
考え方
呼び出しはleftとrightだけに依存します。その結果をmemo[left][right]に保存します。すべてのセルは、実際のコストでは取り得ない値である-1で初期化し、以降の呼び出しでは再帰する代わりにそのセルを読み取ります。約m²/2個の各ペアは、それぞれm未満の分割を使って一度だけ解かれます。計算量はO(n³)で、99個の行列の場合、分割のチェックは161,700回です。再帰の深さはチェーンの長さを超えないため、どのような呼び出しスタックでも境界100個分を処理できます。
アルゴリズム
memoを、すべてのセルが-1の、m行m列の配列として確保します。cheapest(left, right)では、行列が1つだけの区間なら0を返し、セルの値が-1以外なら保存済みのコストを返します。- そうでない場合は、単純な再帰とまったく同じように、すべての
splitのコストを計算し、最小値を取ります。 - 返す前に、その最小値を
memo[left][right]に書き込みます。 - 答えは
cheapest(0, m-1)です。
def matrixChainOrder(dims):
m = len(dims)
# memo[left][right]: the answer for boundaries left and right, -1 while unknown
memo = [[-1] * m for _ in range(m)]
def cheapest(left, right):
if right - left < 2:
return 0 # a single matrix costs nothing
if memo[left][right] != -1:
return memo[left][right]
best = None
for split in range(left + 1, right):
cost = (cheapest(left, split) + cheapest(split, right)
+ dims[left] * dims[split] * dims[right])
if best is None or cost < best:
best = cost
memo[left][right] = best
return best
return cheapest(0, m - 1)表を幅いっぱいに広げて埋める
考え方
各セルはより狭い範囲のみに依存するため、ループで幅の狭い範囲から広い範囲へとbest[left][right]を埋めていけます。幅1は単一の行列なので値は0のままです。より広い範囲に進むと、すべての分割について両側の部分はすでに計算済みです。dims = [6, 2, 7, 3, 5]の場合：
- 幅2：
best[0][2] = 84、best[1][3] = 42、best[2][4] = 105。 - 幅3：
best[0][3]は78（分割1：0 + 42 + 36）、best[1][4]は72（分割3：42 + 0 + 30）です。 - 幅4：分割1、2、3のコストはそれぞれ0 + 72 + 60 = 132、84 + 105 + 210 = 399、78 + 0 + 90 = 168なので、
best[0][4] = 132です。
最上位の分割が境界1になるため、2つ目の例と同様に6 × 2の行列が最後に結合されます。時間とメモリの使用量はメモ化版と同じで、再帰はありません。
アルゴリズム
m = dims.lengthとし、すべて0のm × mテーブルbestを確保します。widthを2からm-1までループします。その中で、right = left + widthがまだ境界内にある間、leftを0から増やしながらループします。- その区間について、
splitをleft+1からright-1まで動かし、それぞれの値best[left][split] + best[split][right] + dims[left] × dims[split] × dims[right]を計算し、最小値をbest[left][right]に格納します。 - 答えは
best[0][m-1]にあります。
def matrixChainOrder(dims):
m = len(dims)
# best[left][right]: the fewest multiplications for the matrices
# between boundary left and boundary right (0 for a single matrix)
best = [[0] * m for _ in range(m)]
for width in range(2, m):
for left in range(m - width):
right = left + width
low = None
for split in range(left + 1, right):
# the last product joins a dims[left] x dims[split] block
# with a dims[split] x dims[right] block
cost = best[left][split] + best[split][right] + dims[left] * dims[split] * dims[right]
if low is None or cost < low:
low = cost
best[left][right] = low
return best[0][m - 1]
落とし穴と境界ケース
- 最もコストの低いペアを最初に掛けること。
[10, 10, 1, 9]では最後のペアが最も低コスト（90）ですが、その次のステップに900かかるため、合計は990です。最初のペアから掛けると190かかります。 - 答えを間違ったセルから読み取ること。
dimsの要素数は行列の数より1つ多いため、答えはbest[0][m-1]であり、best[0][m]ではありません。 - 外側のループで
leftを増やしながら回すこと。この場合、行leftは、まだ0のままの後続の行からbest[split][right]を読み取ってしまいます。幅を外側のループにするか、leftを減らしながら数えてください。 - 行列が1つだけの場合を見落とすこと。
[3, 7]は0を返す必要があります。また、Rではループ2:(m-1)が2:1となって逆方向に実行されるため、ガードを入れてください。
よくある質問3
行列連鎖乗算の時間計算量はどのくらいですか？
表には約 n²/2 個の区間があり、それぞれ最大 n 個の分割を試すため、動的計画法は O(n³) の時間と O(n²) のメモリを使用します。メモ化を行わない単純な再帰では、n 個の行列に対して 3^(n-1) 回の呼び出しが発生します。
行列の乗算では、なぜ順序が重要なのでしょうか？
行列の乗算には結合法則が成り立つため、(AB)C と A(BC) は同じ行列になりますが、中間行列のサイズは異なります。最初の例では、(AB)C は 4 × 3 の行列を作り、コストは 264 ですが、A(BC) は 10 × 12 の行列を作り、コストは 840 です。
最適な括弧付けそのものは、どのように見つければよいでしょうか？
勝利した分割をbest[left][right]の隣にあるchoice[left][right]に保存します。出力する際、行列が1つだけの場合はその名前を出力します。より長い範囲の場合は、開き括弧、choice[left][right]までの部分、その後の部分、閉じ括弧の順に出力します。これによりO(n²)のメモリが追加で必要になります。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def matrixChainOrder(dims):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
dims = [4, 10, 3, 12]
期待される出力
264