实验2 动态规划算法

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

实验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)),1≤i≤n}的最大不相交子集。

[算法思路]

将步骤化为多步,自底向上,先求出矩阵链长为1的最优计算次序，链长为2的最优次序，...

最优解结构：

设A[1:n]=Ai...Aj最优计算次序在Ak和A(k+1)间断开，则总计算量=A[1:k]的计算量+A[k+1:n]的计算量+A[1:k]*A[k+1:n]，则矩阵子链A[1:k]和A[k+1:n]的计算次序也必最优。

[算法步骤和原理分析]

1. 矩阵连乘，n个矩阵的连乘积，设不同的计算次序为P(n)，由于每种加括号方式都可以分解为两个子矩阵的加括号问题：（A1...Ak）（Ak+1...An）可以得到关于P(n)的递推式如下：

1 n=1

P(n)= k 1

P(n)实际为Catalan数，即P(n)=C(n-1)

2. 最长公共子序列：用c[i][j]记录序列Xi和Yj的最长公共子序列的长度。其中，Xi=｛x1，x2，...xi｝；Yj=｛y1，y2，...yj｝。

当i=0或j=0，空序列为最长公共子序列，故C[i][j]=0。

其他情况下，由最优子结构性质可建立递归关系如下：

P(k)P(n k)n 1n 1

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

C[i][j]= c[i-1][j-1]+1 i,j>0;xi=yi;

Max{c[i][j-1],c[i-1][j]} i,j>0;xi≠yi;

3. 电路布线问题：

确定将哪些连线安排在第一层上，使得该层上又尽可能多的连线。也就是说，该问题要求确定导线集Nets=｛（i,π（i）），1≤i≤n｝的最大不相交子集。

最优值size（n，n）的递归结构为：

（1）当i=1时， π（1）

Size（1，j）≥π（1）

（2）当i>1时，

Size（i-1,j） j<π(i)

Size（i，j） Max{Size(i-1,j),Size(i-1,π(i)-1)+1} j≥π(i)

[实验步骤]

//矩阵连乘类

public class Matrix {

private int MN; private int[] p; private int [][]m; private int [][]s; // public Matrix() { } //构造函数,L为矩阵的数目 public Matrix(int L) { MN=L; p=new int [MN+1]; A=new int [MN][][]; m=new int [MN+1][MN+1]; s=new int [MN+1][MN+1]; //随机生成连乘矩阵的维数[1-11] for(int i=0;i<=MN;i++) { } //随机生成各个矩阵 p[i]=(int) Math.round(Math.random()*10)+1; MN=0; p=new int [MN]; //表示矩阵链中矩阵的数目 //存放各个矩阵的维数 //用来存放Ai到Aj的最少乘次数 //用来存放Ai到Aj的最后断开位置 private int [][][]A; //存放要进行连乘的多个矩阵

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

} { } A[i]=new int [p[i]][p[i+1]]; CreatMatrix(A[i],p[i],p[i+1]); //创建矩阵a，维数为m*n private void CreatMatrix(int [][]a,int m,int n) { } //输出连乘的所有矩阵 private void printAllM() { } //输出矩阵a的每个元素 private void printM(int [][]a) { } 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.m[1][M.MN]); System.out.println(); String []s=new String[M.MN+1]; for(int i=1;i<=M.MN;i++) { for(int i=0;i<a.length ;i++) { } System.out.print(" "); for(int j=0;j<a[i].length;j++) System.out.print(String.format("%4d", a[i][j])); System.out.println(); for (int i=0;i<this.MN;i++) { } System.out.println("A"+(i+1)+": "+A[i].length printM(A[i]); for(int i=0;i<m;i++) for(int j=0;j<n;j++) a[i][j]=(int) Math.round(Math.random()*99)-50; +"*"+A[i][0].length );

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

} } M.traceback(M.s, 1, M.MN,s); for(int i=1;i<=M.MN;i++) { System.out.print(s[i]); } //作用：计算a，b矩阵的乘积，将结果保存在c中， //参数：ra为a的行数，ca为a的列数，rb为b的行数，cb为b的列数 public static void matrixMultiply(int [][]a,int [][]b,int [][]c,int { } //作用：计算矩阵连乘时，矩阵链的最少乘次数 //参数：p[0:n]表示矩阵A1,A2...An的维数。Ai为p[i-1]*p[i] // m，用来存放矩阵链的最少乘次数，m[i][j]表示A[i,j]最少乘次数 // s，用来存放矩阵链最优次序的断开位置。 public static void matrixChain(int []p, int [][]m, int [][]s) { //n为矩阵个数 int n=p.length-1; //矩阵链长度为1,不需要进行乘运算，即m[i][i]值为0 for (int i=1;i<=n;i++) m[i][i]=0; //计算矩阵链长度大于1的m值 for (int r=2;r<=n;r++) //针对长度为r的各个矩阵链A[i,j]计算最少乘次数m for(int i=1;i<=n-r+1;i++) { if(ca!=rb) throw new IllegalArgumentException("矩阵不可乘"); //i为乘积矩阵元素的行下标 for(int i=0;i<ra;i++) //j为乘积矩阵元素的列下标 for (int j=0;j<cb;j++) { } //sum初始化为a中i行第一个原素和b中j列第一个元素的乘积 int sum =a[i][0]*b[0][j]; //计算a中第i行和b中第j列对应元素乘积的和 for(int k=1;k<ca;k++) sum+=a[i][k]*b[k][j]; //将乘积的和赋值给乘积矩阵的相应元素 c[i][j]=sum; ra,int ca,int rb,int cb)

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

} } //计算初始值m[i][j]=m[i][i]+m[i+1][j]+p[i-1]*p[i]*p[j] m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j]; //记录对应的断开位置i s[i][j]=i; //断开位置k从i+1到j-1，依次计算m值 for (int k=i+1; k<j; k++) { } //计算断开位置为k的乘计算次数，保存到t int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]; //若t比所记录的最少乘计算次数少，则用t替换，并记录新的断开位置 if (t<m[i][j]) { } m[i][j]=t; s[i][j]=k; public static void traceback(int [][]s,int i,int j,String []c) { if(i==j) return; traceback(s,i,s[i][j],c); traceback(s,s[i][j]+1,j,c); c[i]="("+c[i]; c[j]=c[j]+")"; System.out.println("Multiply A"+i+","+s[i][j]+"and A"+(s[i][j]+1)+","+j);

}

｝

//最长公共子序列类

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;i<m;i++) {

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

} } int t=(int)(Math.random()*8)+65; x[i]=(char) t; for(int i=0;i<n;i++) { } int t=(int)(Math.random()*8)+65; y[i]=(char) t; private void print() { } public static void main(String []args) { } //计算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+1][n+1]; //j=0,最长公共子序列为0 for(int i=1;i<= m;i++) c[i][0]=0; //i=0,最长公共子序列为0 for(int i=1;i<= n;i++) c[0][i]=0; //i,j>0时，计算最长公共子序列的长度 Xl xl1=new Xl(10,12); int [][]b=new int [xl1.xl][xl1.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); for(int i=0;i<this.xl;i++) { } System.out.println(); for(int i=0;i<this.yl;i++) { } System.out.print(String.format("%3s", y[i])); System.out.print(String.format("%3s", x[i]));

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

} } for(int i=1;i<= m;i++) for (int j=1;j<=n;j++) { } //xi=yj,c[i][j]=c[i-1][j-1]+1 if (x[i]==y[j]) { } //xi<>yj,c[i][j]=max{c[i][j-1],c[i-1][j] else if (c[i-1][j]>=c[i][j-1]) { } else { c[i][j]=c[i][j-1]; b[i][j]=3; c[i][j]=c[i-1][j]; b[i][j]=2; c[i][j]=c[i-1][j-1]+1; b[i][j]=1; } return c[m][n]; //构造最长公共子序列 public static void lcs(int i,int j,char []x,int [][]b) { } if (i ==0 || j==0) return; if (b[i][j]== 1) { } else if (b[i][j]== 2) lcs(i-1,j,x,b); lcs(i,j-1,x,b); else lcs(i-1,j-1,x,b); System.out.print(String.format("%3s", x[i]));

//电路步线

public class WireSet {

private int n; private int m; //导线的数目 private int []c; //存放导线 private int [][]size;

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

private int []net; //存放最大公共不相交子集 //构造函数：根据num的值所表示的导线的数目，进行初始化 public WireSet(int num) { } //用来输出相关信息 public void print() { //输出上端线路编号 System.out.print("上端线路编号："); for(int i=0;i<=n;i++) { } System.out.println(); System.out.println(); //输出下端线路编号 System.out.print("下端线路编号："); for(int i=0;i<=n;i++) { System.out.print(String.format("%3d", i)); n=num; c=new int [n+1]; size=new int [n+1][n+1]; net=new int [n+1]; //对c[]进行赋初值，为1-n的任一个排列 c[1]=(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;j<i;j++) { } if (f==0){ } c[i]=t; i++; if (c[j]==t) { } f=1; break;

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

} } System.out.println(); //输出最大不相交子集的个数 System.out.print("最大不相交子集的大小为："+size[n][n]); System.out.println(); //输出最大不相交子集中的各个导线 System.out.print("上端线路编号："); for(int i=this.m-1;i>=0;i--) { } System.out.println(); System.out.print("下端线路编号："); for(int i=this.m-1;i>=0;i--) { System.out.print(String.format("%3d", c[http://www.77cn.com.cn[i]])); } System.out.print(String.format("%3d", http://www.77cn.com.cn[i])); public static void main(String []args){ } //[]c：导线上下两端对应的关系:i=c[j],上端i导线对应下端j导线 //size[][]：用来记录最大不相交子集的大小 public static void mnset(int []c,int [][]size) { int n=c.length-1; //j<c[1],i=1,最大不相交子集为空 for(int j=0;j<c[1];j++) size[1][j]=0; //j≥c[1],i=1,最大不相交子集 for(int j=c[1];j<=n;j++) { for(int j=0;j<c[i];j++) size[i][j]=size[i-1][j]; for(int j=c[i];j<=n;j++) size[1][j]=1; for(int i=2;i<n;i++) WireSet ws= new WireSet(10); //计算最优值 ws.mnset(ws.c, ws.size); //构造最优解 ws.m=ws.traceback(ws.c, ws.size, http://www.77cn.com.cn); //输出结果 ws.print();

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

} } } size[n][n]=Math.max(size[n-1][n],size[n-1][c[n]-1]+1); public static int traceback(int []c,int [][]size ,int []net) { } int n=c.length-1; int j=n; int m=0; for(int i=n;i>1;i--) if(size[i][j]!=size[i-1][j]) { } net[m++]=1; net[m++]=i; j=c[i]-1; if(j>=c[1]) return m;

[实验结果

]

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

实

本文来源：https://www.bwwdw.com/article/vk7i.html