矩陣鏈乘積

矩陣鏈乘積（英語：Matrix chain multiplication，或Matrix Chain Ordering Problem，MCOP）是可用動態規劃解決的最佳化問題。給定一序列矩陣，期望求出相乘這些矩陣的最有效方法。此問題並不是真的去執行其乘法，而只是決定執行乘法的順序而已。

因為矩陣乘法具有結合律，所有其運算順序有很多種選擇。換句話說，不論如何括號其乘積，最後結果都會是一樣的。例如，若有四個矩陣$A$、$B$、$C$和$D$，將可以有：

$ABCD=(AB)(CD)=A(BCD)=A(BC)D=...$

但括號其乘積的順序是會影響到需計算乘積所需簡單算術運算的數目，即其效率。例如，設$A$為一$10\times 30$矩陣，$B$為$30\times 5$矩陣與$C$為$5\times 60$矩陣，則：

• $(AB)C$有$(10\times 30\times 5)+(10\times 5\times 60)=1500+3000=4500$個運算
• $A(BC)$有$(30\times 5\times 60)+(10\times 30\times 60)=9000+18000=27000$個運算

明顯地，第一種方式要有效多了。既然已確認過此問題了，那要如何決定n個矩陣相乘的最佳順序呢？可以比較每一順序的運算量（使用蠻力），但這將需要時間O(2ⁿ)，是一種非常慢且對大n不實在的方法。那解決方法，如我們將看到的，是將問題分成一套相關的子問題。以解答子問題一次而再使用其解答數次，即可以徹底地得出其所需時間。此一方法稱為動態規劃。

動態規劃的算法

一開始，假定真的想知道的是乘完矩陣所需的最小成本，或算術運算的最小量。若只有兩個矩陣相乘，則只會有一種方法去乘它們，所有其最小成本為乘積的成本。一般地，可以用下列的遞迴演算法求出最小成本：

• 取得矩陣的序列且將其分成兩個子序列。
• 找出乘完每一子序列的最小成本。
• 將成本加起來，並加上兩個結果矩陣相乘的成本。
• 在每一矩陣序列可分開的位置運作，並取其最小值。

例如，若有四矩陣$ABCD$，計算每一分法$(A)(BCD)$、$(AB)(CD)$和$(ABC)(D)$所需的成本，遞迴計算$ABC$、$AB$、$CD$和$BCD$的最小成本。然後選擇最好的一個。這方法不只找出其最小成本，也決定做這乘積的最好辦法：儘只是以最小總成本分開，並對每一因子做相同的事情。

不幸地，若真實作此演算法，將會發現它和比較每一順序的運算量一樣慢！發生什麼事了嗎？答案是因為多做了許多多餘的工作。例如，上述遞迴計算了$ABC$與$AB$以找到最小成本，但在找出$ABC$的最小成本時，亦需要去找出$AB$的最小成本。當遞迴較深時，會有越來越多這種不需要的重複產生。

一簡單的解決方法為備忘錄法：每次計算乘完一特定子序列所需的最小成本時，儲存其數值。若再遇到相同子序列時，便只需讀取已存的答案，而不需要再重計算一次。當$n$個矩陣會有約$n^{2}$個不同的子序列，其所需空間是合理的。可證明此一簡單的技術可使得運算時間由$O(2^{n})$降至$O(n^{3})$，使得其對實際應用有足夠的效率。此為由上而下動態規劃。

偽代碼：

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;
                }
            }
        }
    }
}

另一種解決方法是預先知道需要計算的成本並事先計算它們。其運作如下：

• 對每一由2至矩陣數目$n$的$k$：
  • 計算長度$k$的子序列的最小成本，使用已計算過的成本。如此做過之後，將可以得到整個序列的最小成本。即使其亦需要$O(n^{3})$的時間，此一方法有其實作的優點，它不需要使用遞迴，不需要測試是否為已計算的值，而且可以丟掉一些已不需要的結果來節省空間。此為由下而上動態規劃：可解答此問題的第二種方法。

更有效率的算法

1981年由Hu與Shing發表了時間複雜度$O(n\log(n))$的算法。

實作

• 於Alex Le's Blog上的JavaScript實作
• 另一於Data Structures and Algorithms上的JavaScript實作

引用

• Viv. Dynamic Programming （頁面存檔備份，存於網際網路檔案館）. A 1995 introductory article on dynamic programming.
• Cormen, T.H., C.E. Leiserson, and R.L. Rivest. Introduction to Algorithms. McGraw-Hill, New York, NY. 1990. ISBN 0-262-03293-7. Section 15.2. The most popular reference where people encounter this algorithm.
• G. Baumgartner, D. Bernholdt, D. Cociorva, R. Harrison, M. Nooijen, J. Ramanujam and P. Sadayappan. A Performance Optimization Framework for Compilation of Tensor Contraction Expressions into Parallel Programs （頁面存檔備份，存於網際網路檔案館）. 7th International Workshop on High-Level Parallel Programming Models and Supportive Environments (HIPS '02). Fort Lauderdale, Florida. 2002.
• Heejo Lee, Jong Kim, Sungje Hong, and Sunggu Lee. Parallelizing matrix chain products （頁面存檔備份，存於網際網路檔案館）. Tech. Rep. CS-HPC-97003, Pohang University of Science and Technology. 1997.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 15.2: Matrix-chain multiplication, pp.331–339.