实验2 动态规划算法Word格式文档下载.docx
《实验2 动态规划算法Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《实验2 动态规划算法Word格式文档下载.docx（17页珍藏版）》请在冰点文库上搜索。
当i=0或j=0，空序列为最长公共子序列，故C[i][j]=0。
其他情况下，由最优子结构性质可建立递归关系如下：
0i=0,j=0;
C[i][j]=c[i-1][j-1]+1i,j>
0;
xi=yi;
Max{c[i][j-1],c[i-1][j]}i,j>
xi≠yi;
3.电路布线问题：
确定将哪些连线安排在第一层上，使得该层上又尽可能多的连线。
也就是说，该问题要求确定导线集Nets=｛（i,
π（i）），1≤i≤n｝的最大不相交子集。
最优值size（n，n）的递归结构为：
（1）当i=1时，
0j<
π
（1）
Size（1，j）=
1j≥π
（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）
[实验步骤]
//矩阵连乘类
publicclassMatrix{
privateintMN;
//表示矩阵链中矩阵的数目
privateint[]p;
//存放各个矩阵的维数
privateint[][][]A;
//存放要进行连乘的多个矩阵
privateint[][]m;
//用来存放Ai到Aj的最少乘次数
privateint[][]s;
//用来存放Ai到Aj的最后断开位置
//
publicMatrix（）
{
MN=0;
p=newint[MN];
}
//构造函数,L为矩阵的数目
publicMatrix（intL）
MN=L;
p=newint[MN+1];
A=newint[MN][][];
m=newint[MN+1][MN+1];
s=newint[MN+1][MN+1];
//随机生成连乘矩阵的维数[1-11]
for（inti=0;
i<
=MN;
i++）
{
p[i]=（int）Math.round（Math.random（）*10）+1;
}
//随机生成各个矩阵
MN;
A[i]=newint[p[i]][p[i+1]];
CreatMatrix（A[i],p[i],p[i+1]）;
//创建矩阵a，维数为m*n
privatevoidCreatMatrix（int[][]a,intm,intn）
m;
for（intj=0;
j<
n;
j++）
a[i][j]=（int）Math.round（Math.random（）*99）-50;
//输出连乘的所有矩阵
privatevoidprintAllM（）
for（inti=0;
this.MN;
System.out.println（"
A"
+（i+1）+"
:
"
+A[i].length+"
*"
+A[i][0].length）;
printM（A[i]）;
//输出矩阵a的每个元素
privatevoidprintM（int[][]a）
a.length;
System.out.print（"
）;
a[i].length;
System.out.print（String.format（"
%4d"
a[i][j]））;
System.out.println（）;
publicstaticvoidmain（String[]args）
MatrixM=newMatrix（7）;
M.printAllM（）;
M.matrixChain（M.p,M.m,M.s）;
System.out.print（"
矩阵链所需的最少乘次数为：
"
+M.m[1][M.MN]）;
System.out.println（）;
String[]s=newString[M.MN+1];
for（inti=1;
=M.MN;
s[i]="
+i;
M.traceback（M.s,1,M.MN,s）;
System.out.print（s[i]）;
}
//作用：
计算a，b矩阵的乘积，将结果保存在c中，
//参数：
ra为a的行数，ca为a的列数，rb为b的行数，cb为b的列数
publicstaticvoidmatrixMultiply（int[][]a,int[][]b,int[][]c,intra,intca,intrb,intcb）
if（ca!
=rb）
thrownewIllegalArgumentException（"
矩阵不可乘"
//i为乘积矩阵元素的行下标
ra;
//j为乘积矩阵元素的列下标
for（intj=0;
cb;
{
//sum初始化为a中i行第一个原素和b中j列第一个元素的乘积
intsum=a[i][0]*b[0][j];
//计算a中第i行和b中第j列对应元素乘积的和
for（intk=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，用来存放矩阵链最优次序的断开位置。
publicstaticvoidmatrixChain（int[]p,int[][]m,int[][]s）
//n为矩阵个数
intn=p.length-1;
//矩阵链长度为1,不需要进行乘运算，即m[i][i]值为0
for（inti=1;
=n;
i++）m[i][i]=0;
//计算矩阵链长度大于1的m值
for（intr=2;
r<
r++）
//针对长度为r的各个矩阵链A[i,j]计算最少乘次数m
for（inti=1;
=n-r+1;
i++）
intj=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（intk=i+1;
k<
j;
k++）
{
//计算断开位置为k的乘计算次数，保存到t
intt=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;
}
}
publicstaticvoidtraceback（int[][]s,inti,intj,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（"
MultiplyA"
+i+"
"
+s[i][j]+"
andA"
+（s[i][j]+1）+"
+j）;
｝
//最长公共子序列类
publicclassXl{
privatechar[]x;
privatechar[]y;
privateintxl;
privateintyl;
publicXl（intm,intn）
xl=m;
yl=n;
x=newchar[xl];
y=newchar[yl];
intt=（int）（Math.random（）*8）+65;
x[i]=（char）t;
y[i]=（char）t;
privatevoidprint（）
this.xl;
System.out.print（String.format（"
%3s"
x[i]））;
this.yl;
y[i]））;
publicstaticvoidmain（String[]args）
Xlxl1=newXl（10,12）;
int[][]b=newint[xl1.xl][xl1.yl];
intlcsl=lcsLength（xl1.x,xl1.y,b）;
xl1.print（）;
最长公共子序列的长度为：
+lcsl）;
xl1.lcs（xl1.xl-1,xl1.yl-1,xl1.x,b）;
//计算x和y最长公共子序列的长度，b用来记录标记
//最优值存放在c[][]中
publicstaticintlcsLength（char[]x,char[]y,int[][]b）
intm=x.length-1;
intn=y.length-1;
int[][]c=newint[m+1][n+1];
//j=0,最长公共子序列为0
=m;
i++）c[i][0]=0;
//i=0,最长公共子序列为0
=n;
i++）c[0][i]=0;
//i,j>
0时，计算最长公共子序列的长度
for（intj=1;
//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]
elseif（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;
}
returnc[m][n];
//构造最长公共子序列
publicstaticvoidlcs（inti,intj,char[]x,int[][]b）
if（i==0||j==0）return;
if（b[i][j]==1）
lcs（i-1,j-1,x,b）;
elseif（b[i][j]==2）
lcs（i-1,j,x,b）;
else
lcs（i,j-1,x,b）;
}
//电路步线
publicclassWireSet{
privateintn;
//导线的数目
privateintm;
privateint[]c;
//存放导线
privateint[][]size;
privateint[]net;
//存放最大公共不相交子集
//构造函数：
根据num的值所表示的导线的数目，进行初始化
publicWireSet（intnum）
n=num;
c=newint[n+1];
size=newint[n+1][n+1];
net=newint[n+1];
//对c[]进行赋初值，为1-n的任一个排列
c[1]=（int）（Math.random（）*（n）+1）;
inti=2;
while（i<
=n）
intf=0;
intt=（int）（Math.random（）*（n）+1）;
for（intj=1;
i;
if（c[j]==t）
f=1;
break;
if（f==0）{
c[i]=t;
i++;
//用来输出相关信息
publicvoidprint（）
//输出上端线路编号
上端线路编号：
%3d"
i））;
//输出下端线路编号
下端线路编号：
c[i]））;
//输出最大不相交子集的个数
最大不相交子集的大小为：
+size[n][n]）;
//输出最大不相交子集中的各个导线
for（inti=this.m-1;
i>
=0;
i--）
[i]））;
c[[i]]））;
}
publicstaticvoidmain（String[]args）{
WireSetws=newWireSet（10）;
//计算最优值
ws.mnset（ws.c,ws.size）;
//构造最优解
ws.m=ws.traceback（ws.c,ws.size,）;
//输出结果
ws.print（）;
//[]c：
导线上下两端对应的关系:
i=c[j],上端i导线对应下端j导线
//size[][]：
用来记录最大不相交子集的大小
publicstaticvoidmnset（int[]c,int[][]size）
intn=c.length-1;
//j<
c[1],i=1,最大不相交子集为空
for（intj=0;
c[1];
size[1][j]=0;
//j≥c[1],i=1,最大不相交子集
for（intj=c[1];
size[1][j]=1;
for（inti=2;
c[i];
size[i][j]=size[i-1][j];
for（intj=c[i];
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）;
publicstaticinttraceback（int[]c,int[][]size,int[]net）
intj=n;
intm=0;
for（inti=n;
1;
if（size[i][j]!
=size[i-1][j]）
net[m++]=i;
j=c[i]-1;
if（j>
=c[1]）
net[m++]=1;
returnm;
[实验结果]
升级会员 