01、问题分析——递归关系

1●问题

给定n个矩阵{A1,A2,A3,…,An}，其中Ai与Ai+1(i=1,2,3,…,n-1)是可乘的。用加括号的方法表示矩阵连乘的次序，不同加括号的方法所对应的计算次序是不同的。

【例1】三个矩阵A1A2A3连乘，用加括号的方法表示其计算次序。

3个矩阵相乘，其加括号的方法一共有两种，具体如下：

【例2】4个矩阵连乘，用加括号的方法表示其计算次序。

4个矩阵连乘，其加括号的方法共有5种，具体如下：

不同加括号的方法所对应的计算量也是不同的，甚至差别很大。由于在矩阵相乘的过程中，仅涉及加法和乘法两种基本运算，乘法耗时远远大于加法耗时，故采用矩阵连乘所需乘法的次数来对不同计算次序的计算量进行衡量。

【例3】三个矩阵A1,A2,A3的行列分别为10×100、100×5、5×50，求例4-2中的两种加括号方法所需要乘法的次数。

两种加括号方法所需要乘法的次数分别为

那么，矩阵连乘问题就是对于给定n个连乘的矩阵，找出一种加括号的方法，使得矩阵连乘的计算量最小。

容易想到的解决方法是穷举法，即对n个矩阵连乘的每一种加括号方法进行乘法次数的统计，从中找出最小的计算量所对应的加括号方法。这种方法的复杂性取决于加括号的方法的种数。对于n个矩阵连乘，其加括号的方法有多少种呢？

考查矩阵连乘，不管哪种加括号的方法，最终都归结为两部分结果矩阵相乘，这两部分从n个连乘矩阵中的哪个矩阵处分开呢？设可能从Ak和Ak+1处将n个矩阵分成两部分，其中k=1,2,…,n-1。令P(n)代表n个矩阵连乘不同的计算次序，即不同加括号的方式，则n个矩阵连乘加括号的方式可通过两步操作来实现：①分别完成对两部分加括号；②对所得的结果加括号。由此

解此递推方程可得P(n)实际上是Catalan数，即P(n)=C(n-1)，其中

。故穷举法的复杂性非常高，是n的指数级函数，显然，该方法不可行。

2●分析最优解的性质，刻画最优解的结构——最优子结构性质分析

设n个矩阵连乘的最佳计算次序为(A1A2…Ak)(Ak+1Ak+2…An)，则(A1A2…Ak)连乘的计算次序是最优的，(Ak+1Ak+2…An)连乘的计算次序也是最优的。

证明(反证法)： 设(A1A2…Ak)(Ak+1Ak+2…An)的乘法次数为c，(A1A2…Ak)的乘法次数为a，(Ak+1Ak+2…An)乘法次数为b，(A1A2…Ak)和(Ak+1Ak+2…An)的结果矩阵相乘所需要的乘法次数为d，则c=a+b+d。从这个表达式可以看出，无论(A1A2…Ak)和(Ak+1Ak+2…An) 这两部分的计算次序是什么，都不影响这两部分的结果矩阵相乘的乘法次数d。因此，如果c是最小的，那么一定包含a和b都是最小的。如果a不是最小的，那么它所对应的(A1A2…Ak)的计算次序也不是最优的。那么，对于(A1A2…Ak)来说，肯定存在最优的计算次序，设(A1A2…Ak)的最优计算次序所对应的乘法次数为a′，即a′<a，用a′代替a得到c′=a′+b+d，则c′<c，这说明c对应的n个矩阵连乘的计算次序不是最优的，这与前提矛盾，故a一定是最小的。同理，b也是最小的。最优子结构性质得证。

3●建立最优值的递归关系式

AiAi+1…Aj矩阵连乘，其中矩阵Am的行数为pm，列数为qm(m=i,i+1,…,j)且相邻矩阵是可乘的(即qm=pm+1)。设它们的最佳计算次序所对应的乘法次数为mi，则AiAi+1…Ak的最佳计算次序对应的乘法次数为mi，Ak+1Ak+2…Aj的最佳计算次序对应的乘法次数为mk+1。

当i=j时，只有一个矩阵，不用相乘，故mi=0； 当i<j时

将n个矩阵的行数和列数存储在一维数组P［0：n］中(由于qm=pm+1，因此P中只需要存储n+1个元素)，则第i个矩阵的行数存储在P的第i-1位置，列数存储在P的第i位置，则上述递归式可改写为

02、Python实战

1●数据结构选择

Python中，选用二维列表表示二维数组m和s，用一维列表p存储矩阵行列值、res存储计算次序。

2●编码实现

首先定义一个MatrixChain()函数，接收矩阵行列数据p和问题规模n，输出最优值二维表m和最优决策二维表s。

定义一个Traceback()函数构造问题的最优解，接收矩阵连乘子问题的规模i,j(即Ai…Aj)、决策矩阵s，输出最优计算次序res。

Python的入口——main()函数，在main()函数中，给定一个实例的所有矩阵行列arr，然后将其压缩存储在列表p中，调用MatrixChain()函数计算最优值，调用 Traceback()函数构造最优解，最后将计算次序输出到显示器上。

输出结果为

(A1((A2(A3A4))A5))