欢迎来到天天文库
浏览记录
ID:41498576
大小:58.00 KB
页数:3页
时间:2019-08-26
《动态规划——矩阵连乘》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库。
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;k3、在子序列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++)c4、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<=k7、A6))的形式,不过没有成功,待思考...
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<=k7、A6))的形式,不过没有成功,待思考...
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<=k7、A6))的形式,不过没有成功,待思考...
7、A6))的形式,不过没有成功,待思考...
此文档下载收益归作者所有