動的計画法を用いて最適なかっこ付け（行列連鎖乗算）を求めるC++プログラム

本記事では、動的計画法（Dynamic Programming）を用いて、行列連鎖乗算における最適なかっこ付け（Optimal Parenthesization）を求めるC++プログラムを紹介します。

複数の行列を連続して掛け合わせる場合、計算の順序（どのペアから先に掛けるか）によって必要なスカラー乗算の回数が大きく変化します。動的計画法を活用すれば、すべての順序を総当たりすることなく、乗算回数が最小となる分割位置を効率的に求めることができます。

アルゴリズム

まず、使用する変数と配列の意味を確認しておきましょう。

• a[i][j]：行列 A[i]A[i+1]…A[j]（= A[i..j]）を計算するために必要なスカラー乗算の最小回数。なお、A[i] の次元は p[i-1] × p[i] です。a[i][i] = 0、つまり行列が1つだけの場合のコストは0となります。
• b[i][j]：最適な分割位置 k を記録する配列。
• L：連鎖の長さ。
• m：計算途中のコスト（スカラー乗算回数）。

手続きの流れ：
    行列の個数 n と各次元 p[] を入力として受け取る。
    for i = 1 to n-1
        a[i][i] = 0 で初期化
    for L = 2 to n-1
        for i = 1 to n - L + 1
            j = i + L - 1
            a[i][j] = INT_MAX
            for k = i to j - 1
                m = a[i][k] + a[k + 1][j] + p[i - 1] * p[k] * p[j]
                if (m < a[i][j])
                    a[i][j] = m
                    b[i][j] = k
    return a[1][n - 1]

このアルゴリズムでは、短い連鎖から順に最適解を求めていき、その結果を利用しながらより長い連鎖の最適解を構築していくのがポイントです。

C++サンプルコード

#include<limits.h>
#include<iostream>
using namespace std;
int MatrixChain(int p[], int n) {
    int a[n][n];
    int b[n][n];
    int i, j, k, L, m;
    for (i = 1; i < n; i++)
       a[i][i] = 0;
    for (L = 2; L < n; L++) {
       for (i = 1; i <= n - L + 1; i++) {
          j = i + L - 1;
          a[i][j] = INT_MAX;
          for (k = i; k <= j - 1; k++) {
             m = a[i][k] + a[k + 1][j] + p[i - 1] * p[k] * p[j];
             if (m < a[i][j]) {
                a[i][j] = m;
                b[i][j] = k;
             }
          }
       }
    }
    return a[1][n - 1];
}
int main() {
    cout << "Enter the length:";
    int n;
    cin >> n;
    int a[n];
    cout << "Enter the dimensions: ";
    for (int v = 0; v < n; ++v) {
       cin >> a[v];
    }
    cout << "Minimum number of multiplications is: " <<
    MatrixChain(a,n);
    return 0;
}

実行結果

Enter the length:5
Enter the dimensions: 2 3 7 6 4
Minimum number of multiplications is: 174

実行結果の解説

入力された次元「2 3 7 6 4」は、それぞれ A1(2×3)、A2(3×7)、A3(7×6)、A4(6×4) という4つの行列を表しています。このとき得られる最小の乗算回数 174 は、((A1×A2)×A3)×A4 という順序で計算した場合に対応します。

• A1×A2：2×3×7 = 42 回
• (A1A2)×A3：2×7×6 = 84 回
• (A1A2A3)×A4：2×6×4 = 48 回

合計は 42 + 84 + 48 = 174 回となり、これが他のどのかっこ付けよりも少ないことが動的計画法によって保証されます。

このアルゴリズムの計算量は O(n³)、必要なメモリ量は O(n²) です。すべてのかっこ付けを試す指数時間の探索に比べて非常に効率的であり、行列の数が増えても現実的な時間で最適解を求められる点が大きな魅力です。