Matrix chain multiplication

Matrix chain multiplication は最適化問題の一種で、dynamic programming(動的計画法)の例題としてよく見かけます。

問題は、一列の行列が与えられ、その積を求める。その計算コストを最小化せよというもの。どのような順番で計算しても、最終的な結果はかわらないのですが、行列の積は行列のサイズによって計算量がかわるので、トータルの計算量は計算順序に依存します。例えば行列Aを10x30、Bを30x5、Cを5x60とすると、計算コストに以下のような違いが出ます。

• (AB)C = (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 operations
• A(BC) = (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 operations

brute forceなアルゴリズムだとすぐに組み合わせ爆発してしまうので、dpを使って解きます。方針は、まず行列の数列を2分割し、それぞれのサブ数列につき再帰的に最適解を求めます。その際、同じ計算が何度も出てくるので、メモ化が効果的です。以下はwikipediaからの疑似コードです。

Matrix-Chain-Order(int p[])
{
    n = p.length - 1;
    for (i = 1; i <= n; i++) 
       m[i,i] = 0;

    for (l=2; l<=n; l++) { // l is chain length
        for (i=1; i<=n-l+1; i++) {
            j = i+l-1;
            m[i,j] = MAXINT;
            for (k=i; k<=j-1; k++) {
                q = m[i,k] + m[k+1,j] + p[i-1]*p[k]*p[j];//Matrix Ai has the dimension  p[i-1] x p[i].
                if (q < m[i,j]) {
                    m[i,j] = q;
                    s[i,j] = k;
                }
            }
        }
    }
}

配列mにiからjのサブ数列の最適解をメモしています。その下のループでは、サブ数列の長さを2から最大長までループさせ、それぞれについて全ての2分割のしかた（分割ポイントを左から順に動かしている）を見ています。

一般化

この問題を一般化すると、

• あるオブジェクトの線形の数列が与えられる
• オブジェクト同士の二項演算が与えられる
• 各オブジェクトについて計算コストが与えられる。

以上の条件の下でのコスト最小化問題になります。

例として、文字列の連結問題があります。Cではm文字の文字列とn文字の文字列を連結する場合、strcat()を使うとコストはO(m+n)になります。それぞれ文字数の異なる文字列の配列が与えられた場合、このコスト関数を使うことで、mcmと同じ考え方で解くことができます。