矩阵相乘的算法设计.docx

数据结构与算法设计 课程实验报告课 题 矩阵相乘的算法设计专业班级 网工专业1405班 学 号姓 名 陈晓露 指导教师 陶跃进 目录1、 问题描述2、 问题分析1、 分析最优解的结构2、 建立递归关系3、 递归实现的复杂性4、 算法迭代实现3、 结果输出4、 实验总结一、问题描述给定n个矩阵A1，A2，. ，An，其中这n个矩阵是可相乘的，i1，2，.，n-1。算出这n个矩阵的相乘积A1A2 。An。补充：如果两个矩阵A和B是可相乘的，那么A的列数要和B的行数是相同的，否则，这两个矩阵是不可相乘的。它们的相乘结果矩阵C的行数是A的行数，而列数是B的列数。设A1,A2,An为矩阵序列，Ai为Pi-1Pi阶矩阵，i = 1,2,n. 确定乘法顺序使得元素相乘的总次数最少.输入：向量P = 实例：P = A1: 10 100, A2: 100 5, A3: 5 50乘法次序：(A1 A2)A3: 10 100 5 + 10 5 50 = 7500A1(A2 A3): 10 100 50 + 100 5 50 = 75000搜索空间的规模先将矩阵链加括号分为两部分，即P=A1*A2*.*An=（A1*A2.*Ak）*（Ak+1*.An），则有f(n)=f(1)*f(n-1)+f(2)*f(n-2)+.+f(n-1)*f(1)种方法。动态规划算法输入P=，Ai.j 表示乘积 AiAi+1Aj 的结果，其最后一次相乘是：mi,j 表示得到Ai.j的最少的相乘次数。递推方程：为了确定加括号的次序，设计表si,j,记录求得最优时最一位置。二、问题分析由于矩阵乘法满足结合律，故连乘积的计算可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序已完全确定，也就是说该连乘积已完全加括号，则我们可以通过反复调用两个矩阵相乘的标准算法计算出矩阵连乘积。1.分析最优解的结构为了方便起见，我们将矩阵连乘AiAi+1 。Aj记为Ai:j。经分析，计算A1:n的一个最优次序所包含的计算矩阵子链A1:k和Ak:n的次序也是最优的。因此，矩阵连乘计算次序问题的最优解包含着子问题的最优解。2.建立递归关系用矩阵mnn来存放Ai:j相乘的计算次数，用pn+1用来存放矩阵的行数和列数。constintN=5;intmNN;/mij存储Ai到Aj的最小乘法次数intsNN;/sij存储Ai到Aj之间加括号的位置intRecurMatrixChain(intP,inti,intj)mij=100000;sij=i;if(i=j)mij=0;elsefor(intk=i;kj;k+)intq=RecurMatrixChain(P,i,k)+RecurMatrixChain(P,k+1,j)+Pi*Pk+1*Pj+1;if(qmij)mij=q;sij=k;returnmij;intmain()intPN+1=30,35,15,5,10,20;for(inti=0;iN;i+)mii=0;m0N-1=RecurMatrixChain(P,0,N-1);return0;3.递归实现的复杂性复杂性满足递推关系：可见递归实现的复杂性虽然较一般算法有改进，但还是较高。分析原因，主要是子问题重复程度高。如下图所示：1.4表示计算Ai.j中i=1,j=4的子问题，其子问题包括A1.1，而A1.2，A1.3中都包括子问题A1.1，所以很多子问题被重复计算了多次。于是，我们想到用自底向上的迭代实现。4.算法迭代实现迭代实现主要思想是子问题由小到大，每个子问题只计算一次，并且把结果保存起来，后来用到这个子问题时，直接代入。voidMatrixChain(intP,intn)intr,i,j,k,t;for(i=0;iN;i+)for(j=0;jN;j+)mij=0;/r为当前计算的链长（子问题规模）for(r=2;r=n;r+)/n-r+1为最后一个r链的前边界for(i=0;in-r+1;i+)/计算前边界为r，链长为r的链的后边界j=i+r-1;/将链ij划分为A(i)*(A(i+1).A(j)mij=mi+1j+Pi*Pi+1*Pj+1;/记录分割位置sij=i;for(k=i+1;kj-1;k+)/将链ij划分为(A(i).A(k)*(A(k+1).A(j)t=mik+mk+1j+Pi*Pi+1*Pj+1;if(tmij)mij=t;sij=k;intmain()intPN+1=30,35,15,5,10,20;MatrixChain(P,N);三、结果输出再写一个打印结果，以及打印优化函数备忘录m和标记函数的s的函数：voidPrintMatrixChain(intsN,inti,intj)if(i=j)coutAi+1;elsecout(;PrintMatrixChain(s,i,sij);PrintMatrixChain(s,sij+1,j);cout);voidPrintMS(intmN,intsN,intN)for(intr=0;rN;r+)for(inti=0;iN-r;i+)intj=i+r;coutmi+1,j+1=mijt;coutendl;for(intr=1;r5;r+)for(inti=0;iN-r;i+)intj=i+r;coutsi+1,j+1=sij+1t;coutendl;*一个简单的测试实例用一个N=5，P=的简单实例，运行上述代码：4、