はじめに

こんにちは！今回は動的計画法(Dynamic Programming)を使って行列連鎖積問題(Matrix Chain Multiplication)を解くプログラムを紹介します。

行列連鎖積問題とは？

行列A1,A2,....,Anが与えられたとき、これらを掛け合わせる順序によって計算量が変化します。行列の掛け算は結合法則が成り立つため、計算結果は変わりませんが計算回数が最小となる括弧の付け方を求めるのがこの問題です。
例えば、行列の次元が以下のような場合を考えます。A1(13×30),A2(30×8),A3(8×4),A4(4×41)これらを掛ける順序によって、掛け算の回数は大きく変わります。

実装コード

以下がPythonで実装したコードです。動的計画法を用いて、最小の掛け算回数を計算し、最適な括弧付けを出力します。

def matrix_chain_order(dimensions):
    n = len(dimensions) - 1
    m = [[0] * n for _ in range(n)]
    s = [[0] * n for _ in range(n)]
    parens = [[f"A{i+1}" for i in range(n)] for _ in range(n)]

    for l in range(2, n + 1):
        for i in range(n - l + 1):
            j = i + l - 1
            m[i][j] = float('inf')
            for k in range(i, j):
                q = m[i][k] + m[k + 1][j] + dimensions[i] * dimensions[k + 1] * dimensions[j + 1]
                if q < m[i][j]:
                    m[i][j] = q
                    s[i][j] = k
                    parens[i][j] = f"({parens[i][k]}{parens[k+1][j]})"
    return m, s, parens

def print_optimal_parens(s, i, j):
    if i == j:
        print(f"A{i+1}", end="")
    else:
        print("(", end="")
        print_optimal_parens(s, i, s[i][j])
        print_optimal_parens(s, s[i][j] + 1, j)
        print(")", end="")

# 使用例
dimensions = [13, 30, 8, 4, 41]
print("行列の次元:", dimensions)
m, s, parens = matrix_chain_order(dimensions)
print("\n最適な括弧付け:")
print_optimal_parens(s, 0, len(dimensions) - 2)
print("\n最小の乗算回数:", m[0][len(dimensions) - 2])

アルゴリズム解説

このプログラムは動的計画法を用いてm[i][j]に「行列AiからAj」までの最小乗算回数」を格納します。

計算手順

① m[i][j]の初期化

m[i][i]=0 (1つの行列の場合、掛け算は不要)

② 鎖の長さ(l) を増やしながら最小値を更新

l=2 からnまでループし、すべての部分問題を解く

③ 再帰的に括弧を付ける

すべてのKを試して最小の計算回数を見つける

→計算量はO(n^3)ですが、nが大きくなると直接計算するより圧倒的に速くなります。

実行例

次のような入力の場合、最適な括弧付けと最小の乗算回数が計算されます。

行列の次元: [13, 30, 8, 4, 41]

鎖の長さ 2:
m(0, 1):
    (A1)(A2) : 0 + 0 + 13*30*8 = 3120
    m(0, 1) = 3120
m(1, 2):
    (A2)(A3) : 0 + 0 + 30*8*4 = 960
    m(1, 2) = 960
m(2, 3):
    (A3)(A4) : 0 + 0 + 8*4*41 = 1312
    m(2, 3) = 1312

現在の状態:
          0       1       2       3
   --------------------------------
0: |      0    3120       0       0 | 13x30
1: |      0       0     960       0 | 30x8
2: |      0       0       0    1312 | 8x4
3: |      0       0       0       0 | 4x41


鎖の長さ 3:
m(0, 2):
    (A1)((A2A3)) : 0 + 960 + 13*30*4 = 2520
...
((A1(A2A3))A4)
最小の乗算回数: 4652

最終的な括弧付け表現: ((A1(A2A3))A4)

まとめ

行列連鎖積問題を解くことで、アルゴリズム設計の基本的な考え方である「動的計画法」の理解が深まります。今回のプログラムを活用し、より大規模な行列計算や関連問題に応用してみてください。最後まで読んでくださり、ありがとうございました。もし改善点や質問があれば、ぜひコメントしてください！