行列連鎖乗積問題とは？動的計画法で最小の掛け算回数を求める方法

複数の行列が連鎖（チェーン）として与えられたとき、それらを掛け合わせるために必要なスカラー乗算の回数が最小になるような、最適な計算順序を求める問題を考えます。これが「行列連鎖乗積（Matrix Chain Multiplication）」と呼ばれる古典的なアルゴリズムの問題です。

行列の乗算は結合法則が成り立つため、4つの行列 A・B・C・D がある場合、A(BCD)、(AB)(CD)、(ABC)D、A(BC)D のように、さまざまな順序で掛け合わせることができます。しかし、どの順序で計算しても最終結果は同じでも、途中で発生する演算の回数（計算コスト）は順序によって大きく異なります。そこで本記事では、計算量を最小にする最適な順序を動的計画法で求める方法を解説します。

入力には、各行列のサイズ情報を格納した配列 arr が与えられます。たとえば arr[] = {1, 2, 3, 4} であれば、これは (1×2)、(2×3)、(3×4) という3つの行列が連なっていることを意味します。

入力と出力

入力：
行列のサイズを表す配列 {1, 2, 3, 4}。つまり、行列は {(1×2), (2×3), (3×4)}。
出力：
これら3つの行列を掛け合わせるために必要な最小の演算回数。この例では結果は 18。

アルゴリズム

matOrder(array, n)

入力 − 行列のリスト、およびリストに含まれる行列の個数。

出力 − 行列乗算の最小回数。

開始
    n×n のサイズの表 minMul を定義し、すべての要素を 0 で初期化する
    length を 2 から n まで繰り返す：
        i を 1 から n-length まで繰り返す：
            j := i + length − 1
            minMul[i, j] := ∞
            k を i から j-1 まで繰り返す：
                q := minMul[i, k] + minMul[k+1, j] + array[i-1]×array[k]×array[j]
                もし q ＜ minMul[i, j] ならば、minMul[i, j] := q
    minMul[1, n-1] を返す
終了

アルゴリズムのポイント

すべての括弧の付け方を総当たりで試すと、計算量は行列の個数に対して指数関数的に増加してしまいます。しかし、この問題は「部分問題の最適解から全体の最適解を構成できる」という最適部分構造の性質を持つため、動的計画法を用いれば O(n³) の計算量で効率的に解くことができます。

表の各要素 minMul[i][j] は「i 番目から j 番目までの行列を掛け合わせる際に必要な最小のスカラー乗算回数」を表します。分割位置 k の候補をすべて試し、minMul[i][k] + minMul[k+1][j] + array[i-1]×array[k]×array[j] の最小値を順に表へ埋めていくのが、このアルゴリズムの核心部分です。

実装例（C++）

#include<iostream>
using namespace std;

int matOrder(int array[], int n) {
    int minMul[n][n];              // 必要なスカラー乗算の回数を保持する表

    for (int i=1; i<n; i++)
        minMul[i][i] = 0;          // 行列が1つだけの場合、コストは 0

    for (int length=2; length<n; length++) {    // 連鎖の長さを 2 から順に求める
        for (int i=1; i<n-length+1; i++) {
            int j = i+length-1;
            minMul[i][j] = INT_MAX;             // 無限大で初期化
            for (int k=i; k<=j-1; k++) {
                // 各分割位置における乗算コストを計算
                int q = minMul[i][k] + minMul[k+1][j] + array[i-1]*array[k]*array[j];
                if (q < minMul[i][j])
                    minMul[i][j] = q;
            }
        }
    }
    return minMul[1][n-1];
}

int main() {
    int arr[] = {1, 2, 3, 4};
    int size = 4;
    cout << "Minimum number of matrix multiplications: " << matOrder(arr, size);
}

出力

Minimum number of matrix multiplications: 18

この例では、(1×2) と (2×3) を先に掛けてから (3×4) を掛ける順序が最も効率的で、必要なスカラー乗算の回数は 18 回となります。逆に (2×3) と (3×4) を先に計算すると合計 32 回必要になるため、順序の選択が計算コストに大きく影響することがわかります。