动态规划法解矩阵连乘问题

动态规划法解矩阵连乘问题实验内容给定n个矩阵{A1,A2,….An}，其中Ai与Ai+1是可乘的，i=1,2,3。。。，n-1。我们要计算这n个矩阵的连乘积。由于矩阵乘法满足结合性，故计算矩阵连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则我们可依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。解题思路将矩阵连乘积A(i)A(i+1)…A(j)简记为A[i:j]，这里i=j。考察计算A[i:j]的最优计算次序。设这个计算次序在矩阵A(k)和A(k+1)之间将矩阵链断开，i=kj,则其相应完全加括号方式为(A(i)A(i+1)…A(k))*(A(k+1)A(k+2)…A(j))。特征：计算A[i:j]的最优次序所包含的计算矩阵子链A[i:k]和A[k+1:j]的次序也是最优的。矩阵连乘计算次序问题的最优解包含着其子问题的最优解。设计算A[i:j]，1=i=j=n，所需要的最少数乘次数m[i,j]，则原问题的最优值为m[1,n]当i=j时，A[i:j]=Ai，因此，m[i,i]=0，i=1,2,…,n当ij时，m[i,j]=m[i,k]+m[k+1,j]+p(i-1)p(k)p(j)这里A(i)的维数为p(i-1)*(i)(注：p(i-1)为矩阵A(i)的行数，p(i)为矩阵A[i]的列数)实验实验代码#includeiostream#includevectorusingnamespacestd;classmatrix_chain{public:matrix_chain(constvectorint&c){cols=c;count=cols.size();mc.resize(count);s.resize(count);for(inti=0;icount;++i){mc[i].resize(count);s[i].resize(count);}for(i=0;icount;++i){for(intj=0;jcount;++j){mc[i][j]=0;s[i][j]=0;}}}//记录每次子问题的结果voidlookup_chain(){__lookup_chain(1,count-1);min_count=mc[1][count-1];coutmin_multi_count=min_countendl;//输出最优计算次序__trackback(1,count-1);}//使用普通方法进行计算voidcalculate(){intn=count-1;//矩阵的个数//r表示每次宽度//i,j表示从从矩阵i到矩阵j//k表示切割位置for(intr=2;r=n;++r){for(inti=1;i=n-r+1;++i){intj=i+r-1;//从矩阵i到矩阵j连乘，从i的位置切割，前半部分为0mc[i][j]=mc[i+1][j]+cols[i-1]*cols[i]*cols[j];s[i][j]=i;for(intk=i+1;kj;++k){inttemp=mc[i][k]+mc[k+1][j]+cols[i-1]*cols[k]*cols[j];if(tempmc[i][j]){mc[i][j]=temp;s[i][j]=k;}}//fork}//fori}//forrmin_count=mc[1][n];coutmin_multi_count=min_countendl;//输出最优计算次序__trackback(1,n);}private:int__lookup_chain(inti,intj){//该最优解已求出，直接返回if(mc[i][j]0){returnmc[i][j];}if(i==j){return0;//不需要计算，直接返回}//下面两行计算从i到j按照顺序计算的情况intu=__lookup_chain(i,i)+__lookup_chain(i+1,j)+cols[i-1]*cols[i]*cols[j];s[i][j]=i;for(intk=i+1;kj;++k){inttemp=__lookup_chain(i,k)+__lookup_chain(k+1,j)+cols[i-1]*cols[k]*cols[j];if(tempu){u=temp;s[i][j]=k;}}mc[i][j]=u;returnu;}void__trackback(inti,intj){if(i==j){return;}__trackback(i,s[i][j]);__trackback(s[i][j]+1,j);couti,s[i][j]s[i][j]+1,jendl;}private:vectorintcols;//列数intcount;//矩阵个数+1vectorvectorintmc;//从第i个矩阵乘到第j个矩阵最小数乘次数vectorvectorints;//最小数乘的切分位置intmin_count;//最小数乘次数};intmain(){//初始化constintMATRIX_COUNT=6;vectorintc(MATRIX_COUNT+1);c[0]=30;c[1]=35;c[2]=15;c[3]=5;c[4]=10;c[5]=20;c[6]=25;matrix_chainmc(c);//mc.calculate();mc.lookup_chain();return0;}实验结果实验验证连乘矩阵假如为：计算过程为：从m可知最小连乘次数为m[1][6]=15125从s可知计算顺序为((A1(A2A3))((A4A5))A6))实验总结在这次实验中懂得了动态规划法运用方法和解题思路的重要性，在这个程序中如何建立动态规划的过程建立递归过程保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法。