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

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

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)和

2、A(k+1)之间将矩阵链断开，i<=k

3、-1)p(k)p(j)这里A(i)的维数为p(i-1)*(i)(注：p(i-1)为矩阵A(i)的行数，p(i)为矩阵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、resize(count);s[i].resize(count);}for(i=0;i

5、行计算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;k

6、1]*cols[k]*cols[j];if(temp0){returnmc[i][j];}if(i==j){return0

7、;//不需要计算，直接返回}//下面两行计算从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

8、__trackback(inti,intj){if(i==j){return;}__trackback(i,s[i][j]);__trackback(s[i][j]+1,j);cout<