矩阵链乘积

矩阵链乘积（英语：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.