您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 管理学资料 > 动态规划算法分析与设计实验报告(矩阵连乘)
西南大学荣昌校区信息管理系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.根据计算最优值时得到的信息,构造最优解。
本文标题:动态规划算法分析与设计实验报告(矩阵连乘)
链接地址:https://www.777doc.com/doc-5427611 .html