实验三动态规划.doc

;。-:日期:(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时,jkipppjkmkimjim1],1[],[],[?????可以递归地定义m[i,j]为:??????????????jipppjkmkimjijimjki}],1[],[{min0],[1jkik的位置有j-i种可能(3)计算最优值:用动态规划算法解此问题,可依据其递归式以自底向上的方式进行计算。在计算过程中,保存已解决的子问题答案。每个子问题只计算一次,而在后面需要时只要简单查一下,从而避免大量的重复计算,最终得到多项式时间的算法publicstaticvoidMatrixChain(int[]p,int[][]m,int[][]s){intn=-1;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=i+r-1;m[i][j]=m[i+1][j]+p[i+1][i][j];s[i][j]=i;for(intk=i+1;k<j;k++){intt=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]的最佳方式在矩阵Ak和Ak+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]的最优完全加括号方式,即构造出问题的一个最优解。publicstaticvoidtraceback(int[][]s,inti,intj){if(i==j)return;traceback(s,i,s[i][j]);traceback(s,s[i][j]+1,j);("MultiplyA"+i+","+s[i][j]+"andA"+(s[i][j]+1)+","+j);}:/***下面是矩阵连乘问题的动态规划算法*假设有6个矩阵:*A1A2A3A4A5A6*30*3535*1515*55*1010*2020*25则matrixChain为*{30,35,15,5,10,20,25}结果为*((A1*(A2*A3))*((A4*A5)*A6))****@authorzhanlingxia*/4packagejuzhenliancheng;lassjuzhenliancheng{publicstaticvoidmain(String[]args){int[]p={30,35,15,5,10,20,25};//矩阵的维数存放于数组p中matrixMultiply(p);}//矩阵连乘publicstaticvoidmatrixMultiply(int[]p){intdimen=;int[][]m=newint[dimen][dimen];//定义了存放最优值数组mint[][]s=newint[dimen][dimen];//定义了记录断开位置的数组sMatrixChain(p,m,s);("最优乘法次数:"+m[1][dimen-1]);("划分规则为:");traceback(s,1,dimen-1);}/*1:首先计算出m[i][i]2:然后根据递归式按矩阵链长递增的方式以