矩阵连乘实验报告.docx

南京信息工程大学 实验（实习）报告院 计算机与软件学院 专业 软件工程 年级 2013 班次3 姓名 魏开阳 学号 20131344105 一、 实验内容矩阵连乘问题，给定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘的，i=1,2,3,n-1。考察这n个矩阵的连乘A1,A2,An。二、 主要思想由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已经完全加括号，则可依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归的定义为：(1) 单个矩阵是完全加括号的；(2) 矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=(BC)。运用动态规划法解矩阵连乘积的最优计算次序问题。按以下几个步骤进行1、 分析最优解的结构设计求解具体问题的动态规划算法的第1步是刻画该问题的最优解的结构特征。为方便起见，将矩阵连乘积简记为Ai:j。考察计算A1:n的最优计算次序。设这个计算次序矩阵在Ak和Ak+1之间将矩阵链断开，,则其相应的完全加括号方式为(A1Ak)(Ak+1An)。依此次序，先计算A1:k和Ak+1:n,然后将计算结果相乘得到A1:n。2、 建立递归关系设计动态规划算法的第二步是递归定义最优值。对于矩阵连乘积的最优计算次序问题，设计算Ai:j，所需的最少数乘次数为mij，原问题的最优值为m1n。当i=j时，Ai:j=Ai为单一矩阵，无需计算，因此mii=0，i=1,2,n。当ij时，可利用最优子结构性质来计算mij。mij=mik+mk+1j+pi-1pkpj。由于在计算时并不知道断开点k的位置，所以k还未定。3、 计算最优值根据计算mij的递归式，容易写一个递归算法计算m1n。动态规划法解决此问题，可依据递归式以自底向上的方式进行计算，在计算过程中保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法matrixChain。(见实验代码部分)4、 构造最优解算法matrixChain只计算出最优值，并没有给出最优解。但是matrixChain已经记录了构造最优解所需的全部信息。Sij中的数表明，计算矩阵链Ai:j的最佳方式应在矩阵Ak和Ak+1之间断开，最优加括号方式为(Ai:k)(Ak+1:j)。依次构造最优解。(算法见实验代码部分)一、 实验代码#include#define N 100void matrixChain(int p,int mN+1N+1,int sN+1N+1)/*用mij二维数组来存储Ai*.Aj的最少数乘次数，用sij来存储使Ai.Aj获得最少数乘次数对应的断开位置k，需要注意的是此处的N+1非常关键，虽然只用到的行列下标只从1到N，但是下标0对应的元素默认也属于该数组，所以数组的长度就应该为N+1*/int n=N; 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+mk+1j+pi-1*pk*pj;if(tmij)mij=t;sij=k;void traceback(int i,int j,int sN+1) if(i=j)printf(A%d,i);elseprintf();traceback(i,sij,s);traceback(sij+1,j,s);printf();void main()int n; int q2*N;int pN+1,flag=1;int mN+1N+1; int sN+1N+1;printf(输入矩阵的个数(注：小于100)：);scanf(%d,&n);for(int i=0;i=2*n-1;i+) if(i%2=0)printf(n);printf(*输入A%d的行:,(i/2)+1);elseprintf( *列:);scanf(%d,&qi);for(i=1;i=2*n-2;i+)/矩阵连乘条件的检验if(i%2!=0&qi!=qi+1)flag=0;break;for(int j=1;j=n-1;j+)pj=q2*j;if(flag!=0)p0=q0;pn=q2*n-1;matrixChain(p,m,s);printf(式子如下:n);traceback(1,n,s);printf(n);printf(最少数乘次数为%dn,m1n);elseprintf(这%d个矩阵不能连乘!n,n);二、 实验结果三、 结果验证对实验结果进行验证，4个矩阵分别是A135*15，A215*5，A35*10，A410*20。依递归式有：M14=min=7125 且k=3。计算结果正确，证明所编写的程序可正确算出最优解。四、 实验心得通过本次实验，我较为透彻的理解了动态规划算法的几个基本步骤。完成实验后，我认为建立递归关系是很关键的一步，同时也是整个动态规划算法的精髓。掌握了递归的思想，就可以完成很多不必要的重复计算。具体到矩阵连乘问题，关键是解决断开点k的位置和最少数乘次数。总体来说，这次实验不仅让我基本掌握递