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

1、动态规划法解矩阵连乘问题动态规划法解矩阵连乘问题实验内容给定n个矩阵A1,A2,其中Ai与Ai+1是可乘的，i=1,2,3n-1。我们要计算这n个矩阵的连乘积。由于矩阵乘法满足结合性，故计算矩阵连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则我们可依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。解题思路将矩阵连乘积A(i)A(i+1)-A(j)简记为Ai:j,这里i<=j。考察计算Ai:j的最优计算次序。设这个计算次序在矩阵A(k)和A(k+1)之间将矩阵链断开，i<=k<j,则其

2、相应完全加括号方式为(A(i)A(i+1)-A(k)*(A(k+1)A(k+2)-A(j)。特征:计算Ai:j的最优次序所包含的计算矩阵子链Ai:k和Ak+1:j的次序也是最优的。矩阵连乘计算次序问题的最优解包含着其子问题的最优解。设计算Ai:j，1<=i<=j<=n，所需要的最少数乘次数mi,j，则原问题的最优值为m1,n当i=j时，Ai:j=Ai,因此，mi,i=0,i=1,2,n当i<j时，mi,j=mi,k+mk+1,j+p(i-1)p(k)p(j)这里A(i)的维数为p(i-1)*(i)(注:p(i-1)为矩阵A(i)的行数，p(i)为矩阵Ai的列数)实验实验

3、代码#include<iostream>#include<vector>usingnamespacestd;classmatrix_chainpublic:matrix_chain(constvector<int>&c)cols=c;count=cols.size();mc.resize(count);s.resize(count);for(inti=0;i<count;+i)mci.resize(count);si.resize(count);for(i=0;i<count;+i)for(intj=0;j<count;+j)mci

4、j=0;sij=0;/记录每次子问题的结果voidlookup_chain()_lookup_chain(1,count-1);min_count=mc1count-1;cout<<"min_multi_count="<<min_count<<endl;/输出最优计算次序_trackback(1,count-1);/使用普通方法进行计算voidcalculate()intn=count-1;/矩阵的个数/r表示每次宽度/i,j表示从从矩阵i到矩阵j/k表示切割位置for(intr=2;r<=n;+r)for(inti=1;i<

5、=n-r+1;+i)intj=i+r-1;/从矩阵i到矩阵j连乘，从i的位置切割，前半部分为0mcij=mci+1j+colsi-1*colsi*colsj;sij=i;for(intk=i+1;k<j;+k)inttemp=mcik+mck+1j+colsi-1*colsk*colsj;if(temp<mcij)mcij=temp;sij=k;/fork/fori/forrmin_count=mc1n;cout<<"min_multi_count="<<min_count<<endl;/输出最优计算次序_trackback(

6、1,n);private:int_lookup_chain(inti,intj)/该最优解已求出，直接返回if(mcij>0)returnmcij;if(i=j)return0;/不需要计算，直接返回/下面两行计算从i到j按照顺序计算的情况intu=_lookup_chain(i,i)+_lookup_chain(i+1,j)+colsi-1*colsi*colsj;sij=i;for(intk=i+1;k<j;+k)inttemp=_lookup_chain(i,k)+_lookup_chain(k+1,j)+colsi-1*colsk*colsj;if(temp<u)u=

7、temp;sij=k;mcij=u;returnu;void_trackback(inti,intj)if(i=j)return;_trackback(i,sij);_trackback(sij+1,j);cout<<i<<","<<sij<<""<<sij+1<<","<<j<<endl;private:vector<int>cols;/列数intcount;/矩阵个数+1vector<vector<int>

8、>mc;/从第i个矩阵乘到第j个矩阵最小数乘次数vector<vector<int>>s;/最小数乘的切分位置intmin_count;/最小数乘次数;intmain()/初始化constintMATRIX_COUNT=6;vector<int>c(MATRIX_COUNT+1);c0=30;c1=35；c2=15;c3=5;c4=10;c5=20;c6=25;matrix_chainmc(c);/mc.calculate();mc.lookup_chain();return0;实验结果hij«i_mai111wiIl.J1JX彳AJFVk：11iLHI111-：VE.IllI：!£.HIIUK实验验证连乘矩阵假如为A1A2A3A4A5A630x3535>151555Z010x2020.25从m可知最小连乘次数为m16=15125从s可知计算顺序为(A1(