实验三动态规划.doc

1 算法分析与设计实验报告学号姓名班级上课地点教师上课时间实验三动态规划 理解动态规划算法的主要设计思想和基本步骤; 掌握用动态规划策略解决实际问题。 Eclipse Window XP 0-1 背包问题 : 日期: 成绩 2 实验报告细表 1. 矩阵连乘问题 算法设计思想(1) 分析最优解:计算 A[i:j] 的最优次序所包含的计算矩阵子链 A[i:k] 和A[k+1:j] 的次序也是最优的(2) 建立递归关系:设计算 A[i:j] ,1≤i≤j≤n ,所需要的最少数乘次数m[i,j] ,则原问题的最优值为 m[1,n] 当i=j 时, A[i:j]=Ai ,因此, m[i,i]=0 ,i=1,2, …,n 当i<j 时, jkipppjkmkimjim 1],1[],[],[ ?????可以递归地定义 m[i,j] 为: ??????????????jipppjkmkim jijim jki}],1[],[{ min 0],[ 1 jkik的位置有 j-i 种可能(3 )计算最优值:用动态规划算法解此问题,可依据其递归式以自底向上的方式进行计算。在计算过程中,保存已解决的子问题答案。每个子问题只计算一次,而在后面需要时只要简单查一下,从而避免大量的重复计算,最终得到多项式时间的算法 public static void MatrixChain(int []p,int [][]m,int [][]s) { int n=-1; for(int i=1;i<=n;i++)m[i][i]=0; for(int r=2;r<=n;r++) for(int i=1;i<=n-r+1;i++) { int j=i+r-1; m[i][j]=m[i+1][j]+p[i+1][i][j]; s[i][j]=i; for(int k=i+1;k<j;k++) { int t=m[i][k]+m[k+1][j]+p[i-1][k][j]; if(t<m[i][j]){ m[i][j]=t; s[i][j]=k; }} 3 }}(4)构造最优解:算法 matrixChain 记录了构造最优解所需的全部信息。 s[i][j]=k 表明计算矩阵链 A[i:j] 的最佳方式在矩阵 A k和 A k+1之间断开,即最优的加括号方式为(A[i:k])(A[k+1:j]) 。因此,从 s[1][n] 记录的信息可知计算 A[1:n] 的最优加括号方式为(A[1:s[1][n]])(A[s[1][n]+1:n]) 。而 A[1:s[1][n]] 的最优加括号方式为(A[1:s[1][s[1][n]]])(A[s[1][s[1][n]]+1:s[1][s[1][n]]]) 。同理可以确定 A[s[1][n]+1:n] 的最优加括号方式在 s[s[1][n]+1][n] 处断开。照此递推下去,最终可以得到 A[1:n] 的最优完全加括号方式, 即构造出问题的一个最优解。 public static void traceback(int [][]s,int i,int j) { if(i==j)return; traceback(s,i,s[i][j]); traceback(s,s[i][j]+1,j); ("Multiply A"+i+","+s[i][j]+"and A"+(s[i][j]+1)+","+j); } 程序源码矩阵连乘代码: /** * 下面是矩阵连乘问题的动态规划算法* 假设有 6 个矩阵: * A1 A2 A3 A4 A5 A6 * 30*35 35*15 15*5 5*10 10*20 20*25 则 matrixChain 为* {30, 35, 15, 5, 10, 20, 25} 结果为* ((A1 * (A2 * A3)) * ((A4 * A5) * A6) ) * ***@author zhanlingxia */ 4 package juzhenliancheng; public class juzhenliancheng { public static void main(String[] args) { int []p = {30, 35, 15, 5, 10, 20, 25}; // 矩阵的维数存放于数组 p中 matrixMultiply (p); } // 矩阵连乘 public static void matrixMultiply( int [] p) { int dimen = p. length ; int