矩阵连乘问题

宁波工程学院电信学院计算机教研室实验报告一、实验目的：通过上级实验，要求掌握动态规划算法的问题描述，算法设计思想，程序设计和算法复杂性分析等。二、实验环境：VC6.0三、实验内容：1、用分治法算法解决最接近点对问题(1)问题的描述给定n个矩阵，其中iA和是可乘的，i=1,2,…,n-1。考察这n个矩阵的连乘积。由于矩阵乘法具有结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说连乘积已完全加括号，则可依次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘可递归地定义为：（1）单个矩阵是完全加括号的；（2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘B和C的乘积并加括号，即A=（BC）。矩阵A和B可乘的条件是矩阵A的列数等于矩阵B的行数。若A是一个p×q的矩阵，B是一个q×r的矩阵，那么C=A×B就是一个p×r矩阵。它的计算是三重循环的，计算量是pqr。如果加括号后矩阵的量是不同的，所以我们的问题就是要讨论如何给连乘的矩阵加括号才能使矩阵的计算量最少。穷举搜索法：对于n个矩阵的连乘积，设有不同的计算次序P(n)。由于可以先在第k个和第k+1个矩阵之间将原矩阵序列分为两个矩阵子序列，k=1,2,...,n-1；然后分别对这两个矩阵子序列完全加括号；最后对所得的结果加括号，得到原矩阵序列的一种完全加括号方式。解递归方程可得，P(n)=C(n-1),而C(n)是一个指数增长的函数。因此穷举搜索法不是一个有效的算法。以下将用三种方法来解决矩阵连乘问题的最优加括号方式以及最优解。(2)算法设计思想由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。1.分析最优解的结构设计求解具体问题的动态规划算法的第一步是刻画该问题的最优解的结构特征。我们将矩阵连乘积AiAi+1....Aj简记为A[i:j]。考察计算A[1:n]的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，1=kn，则其相应的完全加括号形式为((A1...Ak)(Ak+1...An))。以此次序，总的计算量为A[1:k]的计算量加上A[k+1:n]的计算量，再加上A[1:k]和A[k+1:n]相称的计算量。这个问题的关键特征是：计算A[1:n]的最优次序所包含的计算矩阵子链a[1:k]和A[k+1:n]的次序也是最优的。因此，矩阵连乘积计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可以用动态规划算法求解的显著特征。2.建立递归关系设计动态规划算法的第二步就是递归地定义最优值。对于矩阵连乘积的最有计算次序问题，设计算A[i:j],1=i=j=n，所需的最少数乘次数为m[i][j]，则原问题的最优值为m[1][n]。当i=j时，A[i;j]=Ai，为单一矩阵，无需计算，因此m[i][i]=0。当ij时，可以利用最优子结构的性质来计算m[i][j]。事实上，若计算A[i:j]的最优次序在Ak和Ak+1之间断开，i=kj，则m[i][j]=m[i][k]+m[k+1][j]+Pi-1*Pk*Pj。其中Pi表示第i个矩阵的列数，也是第i-1个矩阵的行数，P0表示第一个矩阵的行数。由于在计算时并不知道断开点k的位置，所以k还未定。不过k的位置只有j-i个可能。从而m[i][j]可以递归地定义为当i=jm[i][j]=0当ijm[i][j]=min{m[i][k]+m[k+1][j]+Pi-1*Pk*Pj}m[i][j]给出了最优值，即计算A[i:j]所需的最少数乘次数。同时还确定了计算A[i:j]的最优次序中的断开位置k，也就是说，对于这个k有m[i][j]=m[i[k]+m[k+1][j]+Pi-1*Pk*Pj若将对应于m[i][j]的断开位置k记为s[i][j]，在计算最优值m[i][j]后，可以递归地有s[i][j]构造出相应的最优解。3.计算最优值根据计算m[i][j]的递归式，容易写一个递归算法计算m[1][n]。但是简单地递归将好费指数计算时间。在递归计算时，许多子问题被重复计算多次。这也是该问题可以用动态规划算法求解的又一显著特征。用动态规划算法解决此问题，可依据其递归是以自底向上的方式进行计算。在计算的过程中，保存以解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算。(3)程序设计（程序清单及说明）#includeiostreamusingnamespacestd;constintL=7;intMatrixChain(intn,int**m,int**s,int*p);voidTraceback(inti,intj,int**s);//最优解intmain(){//矩阵：M1[8,30]M2[30,53]M3[53,55]M4[55,60]M5[60,30]M6[30,40]//上述矩阵的最数字intp[L]={8,30,53,55,60,30,40};int**s=newint*[L];int**m=newint*[L];for(inti=0;iL;i++){s[i]=newint[L];m[i]=newint[L];}cout矩阵的最少计算次数为：MatrixChain(6,m,s,p)endl;cout矩阵最优计算次序为：endl;Traceback(1,6,s);return0;}intMatrixChain(intn,int**m,int**s,int*p){for(inti=1;i=n;i++){m[i][i]=0;}for(intr=2;r=n;r++)//r为当前计算的链长（子问题规模）{for(inti=1;i=n-r+1;i++)//n-r+1为最后一个r链的前边界{intj=i+r-1;//计算前边界为r，链长为r的链的后边界m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];//将链ij划分为A(i)*(A[i+1:j])s[i][j]=i;for(intk=i+1;kj;k++){//将链ij划分为(A[i:k])*(A[k+1:j])intt=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];if(tm[i][j]){m[i][j]=t;s[i][j]=k;}}}}returnm[1][L-1];}voidTraceback(inti,intj,int**s){if(i==j)return;Traceback(i,s[i][j],s);//左侧加括号Traceback(s[i][j]+1,j,s);//右侧加括号coutMultiplyMi,s[i][j];coutandM(s[i][j]+1),jendl;}(4)数据输入和输出结果（运行结果截屏显示）(5)算法复杂性分析算法matrixChina的主要计算量取决于算法中对r，i和k的三重循环，循环体内的计算量为O（1），而3重循环的总次数为O（n3）。一次该算法的时间上界为O（n3）。所占空间为O（n3）。