矩阵连乘问题

目录：矩阵连乘问题：1. 描述矩阵连乘问题2. 分析矩阵连乘问题以及对递归式的推导（1） 直接递归思路（2） 备忘录思路（3） 动态规划思路3. 伪代码的方式描述算法：（1）直接递归算法（2）备忘录算法（3）动态规划算法4. 把算法转换成程序实现的过程及结果（1）直接递归算法程序（2）备忘录算法程序（3）动态规划算法程序1.描述矩阵连乘问题：给定n个矩阵，其中和是可乘的，i=1,2,n-1。考察这n个矩阵的连乘积。由于矩阵乘法具有结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说连乘积已完全加括号，则可依次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘可递归地定义为：（1）单个矩阵是完全加括号的；（2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘B和C的乘积并加括号，即A=（BC）。矩阵A和B可乘的条件是矩阵A的列数等于矩阵B的行数。若A是一个pq的矩阵，B是一个qr的矩阵，那么C=AB就是一个pr矩阵。它的计算是三重循环的，计算量是pqr。如果加括号后矩阵的量是不同的，所以我们的问题就是要讨论如何给连乘的矩阵加括号才能使矩阵的计算量最少。穷举搜索法：对于n个矩阵的连乘积，设有不同的计算次序P(n)。由于可以先在第k个和第k+1个矩阵之间将原矩阵序列分为两个矩阵子序列，k=1,2,.,n-1；然后分别对这两个矩阵子序列完全加括号；最后对所得的结果加括号，得到原矩阵序列的一种完全加括号方式。由此可得P(n)的递归式如下： 1 n=1P（n）= n1 解此递归方程可得，P(n)=C(n-1),而C(n)是一个指数增长的函数。因此穷举搜索法不是一个有效的算法。以下将用三种方法来解决矩阵连乘问题的最优加括号方式以及最优解。2. 分析矩阵连乘问题以及对递归式的推导将矩阵连乘积简记为Ai:j。考察计算A1:n的最优计算次序。这个问题的一个关键特征是：计算A1:n的最优次序包含的计算矩阵子链A1:k和Ak+1:n的次序也是最优的。这是因为：定义矩阵Ai的维数为pi-1pi,则Ai:k的计算次数为pi-1pk，Ak+1,j的计算次数为pkpj，而这两个总的矩阵最后相乘时的计算量是固定的，为pi-1pkpj。所以，矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。（1）、直接递归的思路：记计算Ai:j，1ijn，所需最少数乘次数为mij,则原问题的最优质为m1n。由分析得知：mij可以递归的定义为： 0 i=jmij= i1因此，当n1时，T(n)n+2据此，可用数学归纳法证明T(n)2n-1=。直接递归法的计算时间随n的增长指数增长。（2）、备忘录方法的思路：备忘录方法为每个子问题建立一个记录项，初始化时，该记录项存入一个特殊的值，表示该问题尚未求解。在求解过程中，对每个待求的子问题，首先查看其相应的记录项。若记录项中存储的是初始化时存入的特殊值，则表示该问题第一次遇到，此时计算出该子问题的解，并保存在相应的记录项中，以备以后查看。若记录项中存储的不是初始化存入的特殊值，（比如初始化为-1，解答后赋值为0），则表示该问题已被计算过，其相应的记录项中存储的应该是该子问题的解答。此时，只要从记录相中取出该子问题的解答即可，而不必重新计算。备忘录方法的计算量：因为是要计算mij, 因此只要从n个变量中任意选出2个分别作为i，j，则共有种选法，即有个子问题；当i=j时有n种选法，所以总的子问题就为：+n=个。每填入一个记录项，就要花费O（n）的时间，所以备忘录方法的时间复杂度为O(n3)。（3）、动态规划方法的思路：（以6个矩阵相乘为例）mij123456102x03xx04xxx05xxxx06xxxxx0注意，在mij中，如果ij是没有意义的，因此在表格中都即为x；而且，如果i=j，则代表单个矩阵，所以mii=1.根据直接递归的方法的思路，如果要求mij,就必须要求mik和mk+1j,根据mij的矩阵，则如果要求解m12，则需要知道m11和m12；如果要求解m13，则要知道m11、m12和m11和m23;以此类推。通过此规律可以总结出要求某一个元素，就要知道其左方的所有元素的值和其下方的所有元素的值。mij123456102x03xx04xxx05xxxx06xxxxx0动态规划就是按照上图所画的形式进行求解，从左下方求到右上方。动态规划算法的计算量主要取决于程序中对行、列和加括号的位置k的三重循环。循环体内的计算量为O(1),而三重循环的总次数为O(n3)。因此该算法的计算时间上界为O(n3)。和备忘录的算法的时间复杂度一样，都比直接递归的穷举搜索法有效得多。3. 伪代码的方式描述算法：（1） 直接递归算法： int RecurMatrixChain(int i,int j)if(i=j) return 0;int u=RecurMatrixChain(i,i)+RecurMatrixChain(i+1,j)+pi-1*pi*pj;/递归，p 为维数sij=i;/记录加括号的位置for(int k=i+1;kj;k+)int t=RecurMatrixChain(i,k)+RecurMatrixChain(k+1,j)+pi-1*pk*pj;/递归if(tu) u=t; sij=k;/判断哪个值更小，选取哪个return 0;（2） 备忘录算法：int MemoizedMatrixChain(int n,int * * m,int * * s)for(int i=1;i=n;i+)for(int j=i;j0) return mij; /如果是已经解决的问题，则标记记录项mij已经有值,且大于0，避免重复计算。if(i=j) return 0;int u=LookupChain(i,i)+LookupChain(i+1,j)+pi-1*pi*pj;/递归sij=i;for(int k=i+1;kj;k+)int t=LookupChain(i,k)+LookupChain(k+1,j)+pi-1*pk*pj;/递归 if(tu) u=t; sij=k; /找最小值mij=u;return u;（3） 动态规划算法：void MatrixChain(int *p,int n,int * *m,int * *s)for(int i=1;i=n;i+) mii=0;for(int r=2;r=n;r+) for(int i=1;i=n-r+1;i+)int j=i+r-1;/具体推导由来见下图mij=mi+1j+pi-1*pi*pj;sij=i;for(int k=i+1;kj;k+) int t=mik+k+1j+pi-1*pk*pj; if(tmij)mij=t; sij=k;/sij记录加括号的位置下面的算法Traceback按算法MatrixChain计算出的断点矩阵s指示的加括方式输出计算Ai:j的最优计算次序：void Traceback(int i,int j,int * *s)if(i=j) return;Traceback(i,sij,s);/递归地对左边进行加括号 Traceback(sij+1,j,s);/递归地对右边进行加括号coutMultiply Aiisij;coutand A(sij+1),jendl;/输出最优值和最优解。4. 把算法转换成程序实现的过程及结果程序源代码：matrix.h#include using namespace std;#define NUM 100int mNUMNUM,sNUMNUM,pNUM;/m代洙?表括?最?小?数簓乘?次?数簓的?矩?阵；?s记?录?的?是?最?佳?加括?号?的?位?置?；?p表括?示?矩?阵的?维?数簓,Ai的?维?数簓为 n;/备?忘?录?方?法?int LookupChain(int i,int j)if (mij0) return mij;if (i = j)return 0;int u=LookupChain(i, i)+LookupChain(i+1,j)+pi-1*pi*pj;sij=i;for (int k=i+1; kj;k+) int t=LookupChain(i,k)+LookupChain(k+1,j)+pi-1*pk*pj; if (tu) u=t; sij=k; mij=u; return u; int MemoizedMatrixChain(int n,int * * m,int * * s)for(int i=1;i=n;i+)for(int j=i;j=n;j+) mij=0; /把?mij的?矩?阵的?上?三角?全?部?赋3值为a0。 return LookupChain(1,n);/动态?规?划?法?void MatrixChain() for(int i=1;i=n;i+)mii=0;for(int r=2;r=n;r+) for(int i=1;i=n-r+1;i+) int j = r+i-1; mij=mii+mi+1j+pi-1*pi*pj; sij=i; for(int k = i+1;kj;k+) int temp=mik+mk+1j+pi-1*pk*pj; if(tempmij) mij=temp; sij=k; /直接递蘗归法? int RecurMatrixChain(int i,int j)if(i=j) return 0;int u=RecurMatrixChain(i,i)+RecurMatrixChain(i+1,j)+pi-1*pi*pj;/递蘗归，?p 为a维?数簓sij=i;/记?录?加括?号?的?位?置?for(int k=i+1;kj;k+) int t=RecurMatrixChain(i,k)+RecurMatrixChain(k+1,j)+pi-1*pk*pj;/递蘗归if(tu) u=t; sij=k;/判D断?哪?个?值更小?，?选?取?哪?个?return u;void Traceback(int i,int j) if(i = j) /如?果?只?有瓺一?个?矩?阵，?则直接输?出? coutAi; else if(i+1 = j) /加括?号?输?出? cout(AiAj); else cout(; Traceback(i,sij); Traceback(sij+1,j); cout); MatrixMultiply.cpp#include #include matrix.husing namespace std;/int n; /定义?一?个?全?局?变?量?int main() L:int choice;coutn;cout请输入第1个矩阵行数和第1个矩阵到第n个矩阵的列数：;for(int i=0;ipi;coutendl;cout请选择矩阵连乘的算法:endl;cout1.备忘录算法endl;cout2.直接递归算法endl;cout3.动态规划算法endl;cout4.重新输入矩阵endl;cout5.退出程序endl; coutendl;coutchoice;coutendl;while(choice!=5)switch(choice)case 1: LookupChain(1,n);cout动态规划算法：endl;cout矩阵连乘的最优值为：m1nendl; cout矩阵连乘的最优解为：;Traceback(1,n);coutendl;break;case 2: RecurMatrixChain(0,n); cout动态规划算法：endl;cout矩阵连乘的最优值为：m1nendl; cout矩阵连乘的最优解为：;Traceback(1,n);coutendl;break;case 3:MatrixChain();cout动态规划算法：endl;cout矩阵连乘的最优值为：m1