矩阵相乘的算法设计

数据结构与算法设计课程实验报告课题矩阵相乘的算法设计专业班级网工专业1405班学号14144501352姓名陈晓露指导教师陶跃进目录一、问题描述二、问题分析1、分析最优解的结构2、建立递归关系3、递归实现的复杂性4、算法迭代实现三、结果输出四、实验总结一、问题描述给定n个矩阵｛A1，A2，...，An｝，其中这n个矩阵是可相乘的，i＝1，2，...，n-1。算出这n个矩阵的相乘积A1A2。。。An。补充：如果两个矩阵A和B是可相乘的，那么A的列数要和B的行数是相同的，否则，这两个矩阵是不可相乘的。它们的相乘结果矩阵C的行数是A的行数，而列数是B的列数。设A1,A2,…,An为矩阵序列，Ai为Pi-1×Pi阶矩阵，i=1,2,…,n.确定乘法顺序使得元素相乘的总次数最少.输入：向量P=P0,P1,…,Pn实例：P=10,100,5,50A1:10×100,A2:100×5,A3:5×50乘法次序：(A1A2)A3:10×100×5+10×5×50=7500A1(A2A3):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=P0,P1,…,Pn，Ai..j表示乘积AiAi+1…Aj的结果，其最后一次相乘是：m[i,j]表示得到Ai..j的最少的相乘次数。递推方程：为了确定加括号的次序，设计表s[i,j],记录求得最优时最一位置。二、问题分析由于矩阵乘法满足结合律，故连乘积的计算可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序已完全确定，也就是说该连乘积已完全加括号，则我们可以通过反复调用两个矩阵相乘的标准算法计算出矩阵连乘积。1.分析最优解的结构为了方便起见，我们将矩阵连乘AiAi+1。。。Aj记为A[i:j]。经分析，计算A[1:n]的一个最优次序所包含的计算矩阵子链A[1:k]和A[k:n]的次序也是最优的。因此，矩阵连乘计算次序问题的最优解包含着子问题的最优解。2.建立递归关系用矩阵m[n][n]来存放A[i:j]相乘的计算次数，用p[n+1]用来存放矩阵的行数和列数。constintN=5;intm[N][N];//m[i][j]存储Ai到Aj的最小乘法次数ints[N][N];//s[i][j]存储Ai到Aj之间加括号的位置intRecurMatrixChain(intP[],inti,intj){m[i][j]=100000;s[i][j]=i;if(i==j)m[i][j]=0;else{for(intk=i;kj;k++){intq=RecurMatrixChain(P,i,k)+RecurMatrixChain(P,k+1,j)+P[i]*P[k+1]*P[j+1];if(qm[i][j]){m[i][j]=q;s[i][j]=k;}}}returnm[i][j];}intmain(){intP[N+1]={30,35,15,5,10,20};for(inti=0;iN;i++)m[i][i]=0;m[0][N-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++)m[i][j]=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))m[i][j]=m[i+1][j]+P[i]*P[i+1]*P[j+1];//记录分割位置s[i][j]=i;for(k=i+1;kj-1;k++){//将链ij划分为(A(i)...A(k))*((A(k+1)...A(j))t=m[i][k]+m[k+1][j]+P[i]*P[i+1]*P[j+1];if(tm[i][j]){m[i][j]=t;s[i][j]=k;}}}}}intmain(){intP[N+1]={30,35,15,5,10,20};MatrixChain(P,N);}三、结果输出再写一个打印结果，以及打印优化函数备忘录m和标记函数的s的函数：voidPrintMatrixChain(ints[][N],inti,intj){if(i==j){coutAi+1;}else{cout(;PrintMatrixChain(s,i,s[i][j]);PrintMatrixChain(s,s[i][j]+1,j);cout);}}voidPrintMS(intm[][N],ints[][N],intN){for(intr=0;rN;r++){for(inti=0;iN-r;i++){intj=i+r;coutm[i+1,j+1]=m[i][j]\t;}coutendl;}for(intr=1;r5;r++){for(inti=0;iN-r;i++){intj=i+r;couts[i+1,j+1]=s[i][j]+1\t;}coutendl;}}*一个简单的测试实例用一个N=5，P=30,35,15,5,10,20的简单实例，运行上述代码：四、实验总结对于此次算法设计：翻阅了大量的资料，通过和同学老师的讨论设计了这次算法，用学过的c++语言写成。一个比较简单的例子做起来超乎想象的复杂，但是这个课程设计帮助我更好地理解了所学知识，让我在以后的生活当中能够更好地从多个方面分析问题。