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

《动态规划法解矩阵连乘问题.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、.动态规划法解矩阵连乘问题实验内容给定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<=k

2、加括号方式为(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当i

3、阵A[i]的列数)实验实验代码#include#includeusingnamespacestd;classmatrix_chain{public:matrix_chain(constvector&c){cols=c;count=cols.size();mc.resize(count);s.resize(count);for(inti=0;i

4、]=0;s[i][j]=0;}..}}//记录每次子问题的结果voidlookup_chain(){__lookup_chain(1,count-1);min_count=mc[1][count-1];cout<<"min_multi_count="<

5、;++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;k

6、l;//输出最优计算次序__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;k

7、_lookup_chain(k+1,j)+cols[i-1]*cols[k]*cols[j];if(temp