矩阵连乘详解

言归正传，首先让我们复习一下矩阵连乘的有关知识。对于矩阵知识很了解的人可以跳过矩阵知识这块内容，不过笔者建议最好复习一下。

矩阵知识:

矩阵的乘法：

矩阵相乘只有在第一个矩阵的列数和第二个矩阵的行数相同時才有定义。假如A为m×n矩阵，B为n×p矩阵，则他們的乘AB(有时记做A·B)会是一个m×p矩阵。
例如一个2x3的矩阵与一个3x2的矩阵的乘会是一个2x2的矩阵 。

例子：

矩阵连乘：

设有矩阵M1,M2,M3,M4，
其维数分别是10×20, 20×50, 50×1 和1×100，现要求出这4个矩阵相乘的结果。我们知道，若矩阵A的维数是p×q，矩阵B的维数是q×r，则A与B相乘后所得矩阵AB的维数是p×r。按照矩阵相乘的定义，求出矩阵AB中的一个元素需要做q次乘法（及q-1次加法）。这样，要计算出AB就需要做p×q×r次乘法。为简单起见，且由于加法比同样数量的乘法所用时间要少得多，故这里我们暂不考虑加法的计算量。由于矩阵连乘满足结合律，故计算矩阵连乘的方式可以有多种。

例如，我们可以按M1(M2(M3M4))的方式去计算，
也可以按(M1(M2M3))M4的方式去计算，所得结果是相同的。
但是值得注意的是，
按前一方式计算需要做125,000次乘法，
而按后一方式计算只需要做2,200次乘法。
由此可见，矩阵连乘的运算次序对于所需要的计算量
（所需乘法次数）有着极大的影响。
M3M4：501100=5,000；M2(M3M4)：2050100=100,000
M1(M2(M3M4))：1020100=20,000
(M2M3)：20501=1000；(M1(M2M3))：10201=200 ；
(M1(M2M3))M4：101100=1000

如何解决矩阵连乘问题：

分析：

设要求出矩阵连乘MiMi+1……Mj-1Mj（i<j）所需的最少乘法次数。

```
因共有j-i+1个矩阵，故称这个矩阵连乘的规模是j-i+1
按照做最后一次乘法的位置进行划分，该矩阵连乘一共可分为j-i种情况即有(j-i)种断开方式：Mi(Mi+1┅Mj)，(MiMi+1)(Mi+2┅Mj)，┅，(MiMi+1┅Mj-1)Mj。其中任一对括号内的矩阵个数（即规模）不超过j-i。若我们已知任一个规模不超过j-i的矩阵连乘所需的最少乘法次数，我们就可以很容易地计算出矩阵连乘MiMi+1┅Mj-1Mj（i<j）所需的最少乘法次数，其方法如下。将上述的j-i种情况表示为通式：`(Mi┅Mk) (Mk+1┅Mj)（i≤k<j）。
记第t个矩阵Mt的列数为rt，并令rt-1为矩阵Mt的行数。
则Mi┅Mk连乘所得是ri-1×rk维矩阵，
Mk+1┅Mj连乘所得是rk×rj维矩阵，
故这两个矩阵相乘需要做ri-1×rk×rj次乘法

由于在此之前我们已知
任一个规模不超过j-i的矩阵连乘所需的最少乘法次数，故(Mi┅Mk)和(Mk+1┅Mj)所需的最少乘法次数已知，将它们分别记之为mi,k和mk+1,j。
形为(Mi┅Mk)(Mk+1┅Mj)的矩阵连乘所需的最少乘法次数为：
mi,k + mk+1,j + ri-1×rk×rj。

对满足i≤k<j 的共j-i种情况逐一进行比较，我们就可以得到
矩阵连乘MiMi+1┅Mj-1Mj（i<j）所需的最少乘法次数mi,j为：
mi,j=min { mi,k + mk+1,j + ri-1×rk×rj } （i≤k<j）

于是在初始时我们定义mi,i=0（相当于单个矩阵的情况）
求m1,2：即i=1, j=2，
就是2个矩阵，无需划分 (k=1,因为i<=k<j)
m1,2=min{ m1,1 + m2,2 + ri-1×ri×ri+1
=ri-1×ri×ri+1=r0×r1×r2= 10×20×50=10000，
求m23：即i=2, j=3，故ri-1×ri×ri+1=r1×r2×r3=20×50×1=1000，
求m13：即i=1, j=3，min（i≤k<j）{mik+mk+1,j+ri-1×rk×rj}=
min{ (m11+m23+r0×r1×r3)(k=1)，(m12+m33+r0×r2×r3)(k=2)}=
min{(0+1000+200), (10000+0+500)}= min{1200,10500}=1200

矩阵在C语言中的表示方法：

A[i][j] (i为行，j为列)

拥有了上面的准备知识看下面的内容就会轻松很多。

注：下文所用的mi,j或者m[i][j]表示MiMi+1┅Mj-1Mj（i<j）所需的最少乘法次数

首先，让我们自己思考一下怎么解决一个n个矩阵连乘的问题，也许有了上面的知识你会想到下面的递归的方法：

假设已经算好了Mi┅Mk和Mk+1┅Mj这两个子矩阵各自相乘的最小的次数，剩下的只需要算最后一次乘积的次数就可以了，也就是这里的两个子矩阵相乘所涉及的乘法次数ri-1×rk×rj然后加上前面所得的两个子矩阵各自所需的最小的相乘次数就可以了。这样就得到了上面所说的这个式子：mi,j = mi,k + mk+1,j + ri-1×rk×rj 然后依次判断在k等于某个数的时候所得的mi,j的值，剩下的只需要对所有的mi,j的值取一个最小值就ok了，于是我们就得到了上面所说的这个式子： mi,j=min { mi,k + mk+1,j + ri-1×rk×rj } （i≤k<j）
然而这样做并不能求出mi,j的最小值，因为我们不知道 mi,k 和 mk+1,j的值。但是，这并不会难倒我们，因为我们知道对于 mi,k 和 mk+1,j 的求解可以基于递归思想。方法和求解mi,j的最小值一样。这样我们就得到了递归的式子：

下面代码的p[i]表示的是第i个矩阵的列数，当然他的行数就用i-1表示，呵呵。