C++で解く行列連鎖乗算問題 ― O(N^3)の動的計画法アルゴリズム

複数の行列の連鎖が与えられたとき、スカラー乗算の回数が最小になる正しい掛け合わせ順序を見つける必要があります。

行列の乗算は結合法則が成り立つため、4つの行列ABCDに対して、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 x 2), (2 x 3), (3 x 4)}.

出力 − これら3つの行列を掛け合わせるために必要な最小の演算回数。この場合、結果は18になります。

この問題は動的計画法を用いて効率的に解くことができます。部分連鎖ごとの最小コストを表に記録しながら、連鎖の長さを2から順に拡張していくことで、全体の最小コストをO(N^3)の計算量で求められます。

アルゴリズム

matOrder(array, n)
入力: 行列のリスト、リスト内の行列の個数
出力: 行列乗算の最小回数
Begin
    n x n のサイズの表 minMul を定義し、初期値をすべて0で埋める
    for length := 2 to n, do
        for i := 1 to n-length, do
            j := i + length – 1
            minMul[i, j] := ∞
            for k := i to j-1, do
                q := minMul[i, k] + minMul[k+1, j] + array[i-1]*array[k]*array[j]
                if q < minMul[i, j], then
                    minMul[i, j] := q
                done
            done
        done
    return minMul[1, n-1]
End

実装例

#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 << "行列乗算の最小回数: " << matOrder(arr, size);
}

出力

行列乗算の最小回数: 18