动态规划——矩阵连乘

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

1、代码：#includeusingnamespacestd;constintMAX=100;//p用来记录矩阵的行列，main函数中有说明//m[i][j]用来记录第i个矩阵至第j个矩阵的最优解//s[][]用来记录从哪里断开的才可得到该最优解intp[MAX+1],m[MAX][MAX],s[MAX][MAX];intn;//矩阵个数voidmatrixChain(){for(inti=1;i<=n;i++)m[i][i]=0;for(intr=2;r<=n;r++)//对角线循环fo

2、r(inti=1;i<=n-r+1;i++){//行循环intj=r+i-1;//列的控制//找m[i][j]的最小值，先初始化一下，令k=im[i][j]=m[i][i]+m[i+1][j]+p[i-1]*p[i]*p[j];s[i][j]=i;//k从i+1到j-1循环找m[i][j]的最小值for(intk=i+1;k

3、在子序列i-j段中，在k位置处//断开能得到最优解s[i][j]=k;}}}}//根据s[][]记录的各个子段的最优解，将其输出voidtraceback(inti,intj){if(i==j)return;traceback(i,s[i][j]);traceback(s[i][j]+1,j);cout<<"MultiplyA"<>n;for(inti=0;i<=n;i++)c

4、in>>p[i];//测试数据可以设为六个矩阵分别为//A1[30*35],A2[35*15],A3[15*5],A4[5*10],A5[10*20],A6[20*25]//则p[0-6]={30,35,15,5,10,20,25}//输入：63035155102025matrixChain();traceback(1,n);//最终解值为m[1][n];cout<

5、00*5,5*50按此顺序计算需要的次数（（A1*A2）*A3）:10X100X5+10X5X50=7500次按此顺序计算需要的次数（A1*（A2*A3））:10X5X50+10X100X50=75000次所以问题是：如何确定运算顺序，可以使计算量达到最小化。枚举显然不可，如果枚举的话，相当于一个“完全加括号问题”，次数为卡特兰数,卡特兰数指数增长，必然不行。《建立递归关系》子问题状态的建模（很关键）：令m[i][j]表示第i个矩阵至第j个矩阵这段的最优解。显然如果i=j，则m[i][j]这段中就一个矩阵

6、，需要计算的次数为0；     如果i>j，则m[i][j]=min{m[i][k]+m[k+1][j]+p[i-1]Xp[k]Xp[j]},其中k,在i与j之间游荡，所以i<=k

7、A6））的形式，不过没有成功，待思考...