动态规划算法分析与设计实验报告(矩阵连乘)

西南大学荣昌校区信息管理系1算法分析与设计实验报告实验题目：动态规划算法的设计与实现1、实验目的通过本实验，掌握动态规划算法的设计的基本思想，进一步提高学生的编程能力。2、实验内容：给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1，2…，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。3、源程序#includeiostreamusingnamespacestd;#defineN100intn,q;intm[N][N],s[N][N],p[N+1];voidmatrixChain(){//动态规划计算最优值算法for(inti=1;i=n;i++){m[i][i]=0;}for(intr=2;r=n;r++){//对角线循环for(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;kj;k++){inttemp=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];if(tempm[i][j]){m[i][j]=temp;//s[][]用来记录在子序列i-j段中，在k位置处断开能得到最优解s[i][j]=k;}}}}}intRecur(inti,intj)//直接递归计算最优值{if(i==j){return0;}intu=Recur(i,i)+Recur(i+1,j)+p[i-1]*p[i]*p[j];//递归s[i][j]=i;for(intk=i+1;kj;k++){intt=Recur(i,k)+Recur(k+1,j)+p[i-1]*p[k]*p[j];//从k处断开，分别求得每次的数乘次数西南大学荣昌校区信息管理系2if(tu)//返回t,k中较小的值，并记录断点处k{u=t;s[i][j]=k;}}returnu;}intLook(inti,intj)//备忘录计算最优值{if(m[i][j]0){returnm[i][j];}if(i==j)return0;intu=Look(i,i)+Look(i+1,j)+p[i-1]*p[i]*p[j];s[i][j]=i;for(intk=i+1;kj;k++){intt=Look(i,k)+Look(k+1,j)+p[i-1]*p[k]*p[j];//递归if(tu){u=t;//从k处断开，分别求得每次的数乘次数s[i][j]=k;//返回t,k中较小的值，并记录断点处k}}m[i][j]=u;returnu;}voidTraceback(inti,intj){//输出矩阵结合方式，加括号输出if(i==j)//只有一个矩阵，直接输出{coutAi;}elseif(i+1==j)//两个矩阵，加括号输出{cout(AiAj);}else{cout(;Traceback(i,s[i][j]);//递归，从最得到最优解的地方s[i][j]处断开Traceback(s[i][j]+1,j);cout);}}voidmain(){cout输入矩阵个数：n=;cinn;cout输入第一个矩阵行数和第一个到第n个矩阵的列数：;for(inti=0;i=n;i++){cinp[i];}coutendl;cout请选择解决矩阵连乘问题的方法：endl;cout1.动态规划算法endl;cout2.直接递归算法endl;cout3.备忘录算法endl;cout0.退出...endl;coutendl;cout请选择算法：;cinq;coutendl;while(q!=0){switch(q){case1:matrixChain();cout动态规划算法解决矩阵连乘问题：endl;cout最优计算次序为：;Traceback(1,n);coutendl;cout矩阵连乘的最优数乘次数为：m[1][n]endl;//最终解值为m[1][n]break;case2:Recur(0,n);cout直接递归算法解决矩阵连乘问题：endl;西南大学荣昌校区信息管理系3cout最优计算次序为：;Traceback(1,n);coutendl;cout矩阵连乘的最优数乘次数为：m[1][n]endl;//最终解值为m[1][n]break;case3:Look(1,n);cout备忘录算法解决矩阵连乘问题：endl;cout最优计算次序为：;Traceback(1,n);coutendl;cout矩阵连乘的最优数乘次数为：m[1][n]endl;//最终解值为m[1][n]break;case0:q=0;break;}coutendl;cout请选择解决矩阵连乘问题的方法：endl;cout1.动态规划算法endl;cout2.直接递归算法endl;cout3.备忘录算法endl;cout0.退出...endl;cout请选择算法：;cinq;coutendl;}coutendl;}4、运行结果（截图）5、结论动态规划算法设计通常有四个步骤：1.找出最优解的性质，并刻画其结构特征。2.递归的定义最优解3.自底向上的方式计算出最优值。4.根据计算最优值时得到的信息，构造最优解。