实验02-动态规划算法.doc

实验02动态规划算法实验目的1. 掌握动态规划算法的基本方法2. 掌握动态规划算法中最优子结构的分析3. 掌握递归求解最优值的方法4. 掌握最优解的构造.预习要求1. 认真阅读算法设计教材,了解动态规划原理;2. 设计用动态规划算法求解矩阵连乘、最长公共子序列以及电路布线的java程序.实验题1. 给定n个矩阵A1, A2, ,An，其中，Ai与Ai+1是可乘的，计算这n个矩阵的连乘积。从中找出一种乘次数最少的计算次序。2. 给定2个序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最长公共子序列。3. 在一块电路板的上、下2端分别有n个接线柱。根据电路设计，要求用导线(i,(i)将上端接线柱与下端接线柱相连，确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线。该问题要求确定导线集Nets=(i,(i),1in的最大不相交子集。 实验步骤1. 设计并实现算法并准备测试用例,修改并调试程序,直至正确为止;2. 应用设计的算法和程序求解问题;3. 将程序整理成功能模块存盘备用. 实验报告要求1. 阐述实验目的和实验内容;2. 阐述求解问题的算法原理;3. 提交实验程序的功能模块;4. 记录最终测试数据和测试结果。参考1./矩阵连乘类public class Matrix private int MN;/表示矩阵链中矩阵的数目private int p;/存放各个矩阵的维数private int A;/存放要进行连乘的多个矩阵private int m;/用来存放Ai到Aj的最少乘次数private int s;/用来存放Ai到Aj的最后断开位置/public Matrix()MN=0;p=new int MN;/构造函数,L为矩阵的数目public Matrix(int L)MN=L;p=new int MN+1;A=new int MN;m=new int MN+1MN+1;s=new int MN+1MN+1;/随机生成连乘矩阵的维数1-11for(int i=0;i=MN;i+)pi=(int) Math.round(Math.random()*10)+1;/随机生成各个矩阵for(int i=0;iMN;i+)Ai=new int pipi+1;CreatMatrix(Ai,pi,pi+1);/创建矩阵a，维数为m*nprivate void CreatMatrix(int a,int m,int n)for(int i=0;im;i+)for(int j=0;jn;j+)aij=(int) Math.round(Math.random()*99)-50;/输出连乘的所有矩阵private void printAllM()for (int i=0;ithis.MN;i+)System.out.println(A+(i+1)+: +Ai.length +*+Ai0.length );printM(Ai);/输出矩阵a的每个元素private void printM(int a)for(int i=0;ia.length ;i+)System.out.print( );for(int j=0;jai.length;j+)System.out.print(String.format(%4d, aij);System.out.println();public static void main(String args)Matrix M=new Matrix(7);M.printAllM();M.matrixChain(M.p,M.m,M.s);System.out.print(矩阵链所需的最少乘次数为：+M.m1M.MN);System.out.println();String s=new StringM.MN+1;for(int i=1;i=M.MN;i+)si=A+i;M.traceback(M.s, 1, M.MN,s);for(int i=1;i=M.MN;i+)System.out.print(si);/作用：计算a，b矩阵的乘积，将结果保存在c中，/参数：ra为a的行数，ca为a的列数，rb为b的行数，cb为b的列数public static void matrixMultiply(int a,int b,int c,int ra,int ca,int rb,int cb)if(ca!=rb)throw new IllegalArgumentException(矩阵不可乘);/i为乘积矩阵元素的行下标for(int i=0;ira;i+)/j为乘积矩阵元素的列下标for (int j=0;jcb;j+)/sum初始化为a中i行第一个原素和b中j列第一个元素的乘积int sum =ai0*b0j;/计算a中第i行和b中第j列对应元素乘积的和for(int k=1;kca;k+)sum+=aik*bkj;/将乘积的和赋值给乘积矩阵的相应元素cij=sum;/作用：计算矩阵连乘时，矩阵链的最少乘次数/参数：p0:n表示矩阵A1,A2.An的维数。Ai为pi-1*pi/ m，用来存放矩阵链的最少乘次数，mij表示Ai,j最少乘次数/ s，用来存放矩阵链最优次序的断开位置。public static void matrixChain(int p, int m, int s)/n为矩阵个数int n=p.length-1;/矩阵链长度为1,不需要进行乘运算，即mii值为0for (int i=1;i=n;i+) mii=0;/计算矩阵链长度大于1的m值for (int r=2;r=n;r+)/针对长度为r的各个矩阵链Ai,j计算最少乘次数mfor(int i=1;i=n-r+1;i+) int j=i+r-1;/计算初始值mij=mii+mi+1j+pi-1*pi*pjmij=mi+1j+pi-1*pi*pj;/记录对应的断开位置isij=i;/断开位置k从i+1到j-1，依次计算m值for (int k=i+1; kj; k+)/计算断开位置为k的乘计算次数，保存到tint t=mik+mk+1j+pi-1*pk*pj;/若t比所记录的最少乘计算次数少，则用t替换，并记录新的断开位置if (tmij) mij=t;sij=k;public static void traceback(int s,int i,int j,String c)if(i=j) return;traceback(s,i,sij,c);traceback(s,sij+1,j,c);ci=(+ci;cj=cj+);System.out.println(Multiply A+i+,+sij+and A+(sij+1)+,+j);2./最长公共子序列类public class Xl private char x;private char y;private int xl;private int yl;public Xl(int m,int n)xl=m;yl=n;x=new char xl;y=new char yl;for(int i=0;im;i+)int t=(int)(Math.random()*8)+65;xi=(char) t;for(int i=0;in;i+)int t=(int)(Math.random()*8)+65;yi=(char) t;private void print()for(int i=0;ithis.xl;i+)System.out.print(String.format(%3s, xi);System.out.println();for(int i=0;ithis.yl;i+)System.out.print(String.format(%3s, yi);public static void main(String args)Xl xl1=new Xl(10,12);int b=new int xl1.xlxl1.yl;int lcsl=lcsLength(xl1.x,xl1.y,b);xl1.print();System.out.println();System.out.print(最长公共子序列的长度为：+lcsl);System.out.println();xl1.lcs(xl1.xl-1,xl1.yl-1,xl1.x, b);/计算x和y最长公共子序列的长度，b用来记录标记/最优值存放在c中public static int lcsLength(char x,char y,int b)int m=x.length-1;int n=y.length-1;int c=new int m+1n+1;/j=0,最长公共子序列为0for(int i=1;i= m;i+) ci0=0;/i=0,最长公共子序列为0for(int i=1;i0时，计算最长公共子序列的长度for(int i=1;i= m;i+) for (int j=1;j=n;j+)/xi=yj,cij=ci-1j-1+1if (xi=yj) cij=ci-1j-1+1;bij=1;/xiyj,cij=maxcij-1,ci-1jelse if (ci-1j=cij-1) cij=ci-1j;bij=2;else cij=cij-1;bij=3; return cmn;/构造最长公共子序列public static void lcs(int i,int j,char x,int b)if (i =0 | j=0) return;if (bij= 1)lcs(i-1,j-1,x,b);System.out.print(String.format(%3s, xi);else if (bij= 2) lcs(i-1,j,x,b);else lcs(i,j-1,x,b);33333333333333333333333333333333333333333333333333333333333333333./电路步线public class WireSet private int n;/导线的数目private int m;private int c;/存放导线private int size;private int net;/存放最大公共不相交子集/构造函数：根据num的值所表示的导线的数目，进行初始化public WireSet(int num)n=num;c=new int n+1;size=new int n+1n+1;net=new int n+1;/对c进行赋初值，为1-n的任一个排列c1=(int)(Math.random()*(n)+1);int i=2;while(i=n)int f=0;int t=(int)(Math.random()*(n)+1);for(int j=1;ji;j+)if (cj=t) f=1;break;if (f=0)ci=t;i+;/用来输出相关信息public void print()/输出上端线路编号System.out.print(上端线路编号：);for(int i=0;i=n;i+)System.out.print(String.format(%3d, i);System.out.println();System.out.println();/输出下端线路编号System.out.print(下端线路编号：);for(int i=0;i=0;i-)System.out.print(String.format(%3d, i);System.out.println();System.out.print(下端线路编号：);for(int i=this.m-1;i=0;i-)System.out.print(String.format(%3d, i);public static void main(String args)WireSet ws= new WireSet(10);/计算最优值ws.mnset(ws.c, ws.size);/构造最优解ws.m=ws.traceback(ws.c, ws.size, );/输出结果ws.print();/c：导线上下两端对应的关系:i=cj,上端i导线对应下端j导线/size：用来记录最大不相交子集的大小public st