矩阵连乘最佳加括号方式-动态规划算法WORD

1、文档可能无法思考全面，请浏览后下载! 矩阵连乘最佳加括号方式动态规划算法一、问题描述 给定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘的，i=1,2,n-1。要算出这n个矩阵的连乘积A1A2An。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为： （1）单个矩阵是完全加括号的；（2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，

2、即A=(BC)。 例如，矩阵连乘积A1A2A3A4有5种不同的完全加括号的方式：（A1（A2（A3A4），（A1（A2A3）A4），（A1A2）（A3A4），（A1（A2A3）A4），（A1A2）A3）A4）。每一种完全加括号的方式对应于一个矩阵连乘积的计算次序，这决定着作乘积所需要的计算量。若A是一个pq矩阵，B是一个qr矩阵，则计算其乘积C=AB的标准算法中，需要进行pqr次数乘。 为了说明在计算矩阵连乘积时，加括号方式对整个计算量的影响，先考察3个矩阵A1,A2,A3连乘的情况。设这三个矩阵的维数分别为10100，1005，550。加括号的方式只有两种：（A1A2）A3），（A1（A2A

3、3），第一种方式需要的数乘次数为101005105507500，第二种方式需要的数乘次数为100550101005075000。第二种加括号方式的计算量时第一种方式计算量的10倍。由此可见，在计算矩阵连乘积时，加括号方式，即计算次序对计算量有很大的影响。于是，自然提出矩阵连乘积的最优计算次序问题，即对于给定的相继n个矩阵A1,A2,An（其中矩阵Ai的维数为pi-1pi，i1,2,n），如何确定计算矩阵连乘积A1A2An的计算次序（完全加括号方式），使得依此次序计算矩阵连乘积需要的数乘次数最少。 穷举搜索法的计算量太大，它不是一个有效的算法，本实验采用动态规划算法解矩阵连乘积的最优计算次序问题

4、。二、算法思路6 / 8 动态规划算法的基本思想是将待求解问题分成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，动态规划法经分解得到的子问题往往不是相互独立的，前一子问题的解为后一子问题的解提供有用的信息，可以用一个表来记录所有已解决的子问题的答案，不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。 本实验的算法思路是： 1、计算最优值算法MatrixChain()：建立两张表（即程序中的*m和*s，利用二维指针存放），一张表存储矩阵相乘的最小运算量，主对角线上的值为0，依次求2个矩阵、3个矩阵、直到n个矩阵相乘的最小运算量，其中每次矩阵相乘的

5、最小运算量都在上一次矩阵相乘的最小运算量的基础上求得，最后一次求得的值即为n个矩阵相乘的最小运算量；另一张表存储最优断开位置。 2、输出矩阵结合方式算法Traceback()：矩阵结合即是给矩阵加括号，打印出矩阵结合方式，由递归过程Traceback()完成。分三种情况： （1）只有一个矩阵，则只需打印出A1； （2）有两个矩阵，则需打印出（A1A2）； （3）对于矩阵数目大于2，则应该调用递归过程Traceback()两次，构造出最优加括号方式。 三、实验源程序 建立一个矩阵的类Matrix。 Matrix.h代码#ifndefMATRIX_H#defineMATRIX_HclassMatr

6、ixpublic:Matrix();/构造函数Matrix();/析构函数boolRun();/运行接口函数private:intW;/记录矩阵的个数int*m;/存放最优值，即最小运算量int*s;/断开位置int*p;/存放boolInput();/处理输入boolMatrixChain();/计算最优值算法voidTraceback(inti,intj,int*s);/输出矩阵加括号的方式;#endifMatrix.cpp代码#defineN50#include#include#includeMatrix.h/构造函数，作变量初始化工作，为指针分配内存空间Matrix:Matrix()W

7、=0;m=newint*N;s=newint*N;for(inti=0;iN;i+)mi=newintN;si=newintN;p=newintN;/析构函数，释放内存Matrix:Matrix()for(inti=0;iN;i+)deletemi;deletesi;deletem;deletes;deletep;/处理键盘输入boolMatrix:Input()intw;coutw;W=w;cout输入矩阵A1维数p0p1;for(inti=2;i=W;i+)intm=pi-1;cout输入矩阵Aipi-1pi;if(pi-1!=m)coutendl维数不对，矩阵不可乘！endl;exit(

8、1);/coutendl;if(p!=NULL)returntrue;elsereturnfalse;/计算最优值算法boolMatrix:MatrixChain()if(NULL=p)returnfalse;for(inti=1;i=W;i+)mii=0;for(intr=2;r=W;r+)for(inti=1;i=W-r+1;i+)intj=i+r-1;mij=mi+1j+pi-1*pi*pj;sij=i;for(intk=i+1;kj;k+)intt=mik+mk+1j+pi-1*pk*pj;if(tmij)mij=t;sij=k;returntrue;/输出矩阵结合方式，加括号voidMatrix:Traceback(inti,intj,int*s)if(i=j)coutAi;elseif(i+1=j)cout(AiAj);elsecout(;Traceback(i,sij,s);Traceback(sij+1,j,s);cout);boolMatrix:Run()if(Matrix:Input()if(Matrix:MatrixChain()Matrix:Traceback(