实验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)),1≤i≤n}的最大不相交子集。
[实验步骤]
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+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;
}
//随机生成各个矩阵
for(int i=0;i<MN;i++)
{
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)
{
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
a[i][j]=(int) Math.round(Math.random()*99)-50;
}
//输出连乘的所有矩阵
private void printAllM()
{
for (int i=0;i<this.MN;i++)
{
System.out.println("A"+(i+1)+": "+A[i].length +"*"+A[i][0].length );
printM(A[i]);
}
}
//输出矩阵a的每个元素
private void printM(int [][]a)
{
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();
}
}
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++)
{
s[i]="A"+i;
}
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 ra,int ca,int rb,int cb)
{
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;
}
}
//作用：计算矩阵连乘时，矩阵链的最少乘次数
//参数：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++)
{
int j=i+r-1;
//计算初始值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);
}

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;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()
{
for(int i=0;i<this.xl;i++)
{
System.out.print(String.format("%3s", x[i]));
}
System.out.println();
for(int i=0;i<this.yl;i++)
{
System.out.print(String.format("%3s", y[i]));
}
}
public static void main(String []args)
{
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);
}
//计算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时，计算最长公共子序列的长度
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])
{
c[i][j]=c[i-1][j-1]+1;
b[i][j]=1;
}
//xi<>yj,c[i][j]=max{c[i][j-1],c[i-1][j]
else if (c[i-1][j]>=c[i][j-1])
{
c[i][j]=c[i-1][j];
b[i][j]=2;
}
else
{
c[i][j]=c[i][j-1];
b[i][j]=3;
}
}
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)
{
lcs(i-1,j-1,x,b);
System.out.print(String.format("%3s", x[i]));
}
else if (b[i][j]== 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+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 (c[j]==t)
{
f=1;
break;
}
}
if (f==0){
c[i]=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<=n;i++)
{
System.out.print(String.format("%3d", c[i]));
}
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.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", c[[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=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++)
size[1][j]=1;
for(int i=2;i<n;i++)
{
for(int j=0;j<c[i];j++)
size[i][j]=size[i-1][j];
for(int j=c[i];j<=n;j++)
size[i][j]=Math.max(size[i-1][j],size[i-1][c[i]-1]+1);
}
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++]=i;
j=c[i]-1;
}
if(j>=c[1])
net[m++]=1;
return m;
}
}