动态规划.docx

动态规划.docx

《动态规划.docx》由会员分享，可在线阅读，更多相关《动态规划.docx（19页珍藏版）》请在冰点文库上搜索。

动态规划

实验目的：

掌握动态规划算法的基本原理和应用以及软件实现。

实验准备：

1．在开始本实验之前，请回顾教科书的相关内容；

2．需要一台准备安装WindowsXPProfessional操作系统和VC++软件的计算机。

实验内容及要求

内容：

完成动态规划常见题目的程序

要求：

1，保证程序可以正常的运行

2，结果正确，程序稳定

实验过程：

2.1问题分析

动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。

动态规划算法通常用于求解具有某种最优性质的问题。

在这类问题中，可能会有许多可行解。

每一个解都对应于一个值，我们希望找到具有最优值的解。

动态规划算法与分治法类似。

其基本思想：

是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。

若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。

如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。

我们可以用一个表来记录所有已解的子问题的答案。

不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。

动态规划的基本模型有：

（1）确定问题的决策对象。

（2）对决策过程划分阶段。

（3）对各阶段确定状态变量。

（4）根据状态变量确定费用函数和目标函数。

（5）建立各阶段状态变量的转移过程，确定状态转移方程。

使用条件是：

1、最优化原理；2、无后效性3、子问题的重叠性。

针对动态规划问题，可以通过下列几个实例进行了解。

1、矩阵连乘问题

给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1,2,…,n-1。

如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。

建立相应的递归关系,如下：

设计算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

。

这里

的维数为

，可以递归地定义m[i,j]为：

其中k的位置有j-i种可能。

相应的实验代码如下：

#include

#include

usingnamespacestd;

constintMAX=100;

intp[MAX+1],m[MAX][MAX],s[MAX][MAX];

intn;//矩阵个数

voidMatrixChain（）

{

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]*p[i]*p[j];

s[i][j]=i;

for（intk=i+1;k

{

intt=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];

if（t

}

}

}

voidTraceback（inti,intj）

{

if（i==j）return;

Traceback（i,s[i][j]）;

Traceback（s[i][j]+1,j）;

cout<<"MultiplyA"<

cout<<"andA"<<（s[i][j]+1）<<","<

}

intmain（）

{intj;

cin>>n;

for（inti=0;i<=n;i++）cin>>p[i];

MatrixChain（）;

Traceback（1,n）;

for（i=1;i<7;i++）

{for（j=1;j<7;j++）

{cout<

}cout<

cout<<"*****************************************************"<

for（i=1;i<7;i++）

{for（j=1;j<7;j++）

{cout<

}cout<

//最终解值为m[1][n];

cout<

return0;

}

从得到的程序与结果上分析：

输入的是6个矩阵，各个矩阵的维数分别为30*35、35*15、15*5、5*10、10*20、20*25，计算出得次序如上图，该算法的空间复杂度是o（n^2）。

2、最长公共子序列

最长公共子序列，其定义是，一个序列S，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则S称为已知序列的最长公共子序列。

而最长公共子串（要求连续）和最长公共子序列是不同的。

动态规划的一个计算两个序列的最长公共子序列的方法如下：

以两个序列X、Y为例子：

设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk}，则

1.若xm=yn，则zk=xm=yn，且zk-1是xm-1和yn-1的最长公共子序列;

2.若xm≠yn且zk≠xm，则Z是xm-1和Y的最长公共子序列;

3.若xm≠yn且zk≠yn，则Z是X和yn-1的最长公共子序列。

由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。

用c[i][j]记录序列和的最长公共子序列的长度。

由最优子结构性质可建立递归关系如下：

程序如下：

#include

usingnamespacestd;

constk=1000;

voidzuichang（intm,intn,int**c,char*x,char*y,int**b）

{

inti,j;

for（i=0;i

c[i][0]=0;

for（j=0;j

c[0][j]=0;

for（i=1;i<=m;i++）

{

for（j=1;j<=n;j++）

{

if（x[i]==y[j]）{c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}

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;}

}

}

}

voidLCS（inti,intj,char*x,int**b）

{

if（i==0||j==0）return;

if（b[i][j]==1）{LCS（i-1,j-1,x,b）;cout<

elseif（b[i][j]==2）LCS（i-1,j,x,b）;

elseLCS（i,j-1,x,b）;

}

intmain（）

{

intm,n,i,j;

//int**c;

//int**b;

//b=newint*[n];b[i]=newint[m];

cout<<"请输入x[m]中m得取值：

";

cin>>m;

cout<<"请输入y[n]中n得取值：

";

cin>>n;

char*x=newchar[m];

char*y=newchar[n];

int**c;

int**b;

c=newint*[k+1];

for（i=0;i<=k;i++）

{

c[i]=newint[k+1];

//memset（（*m）+i,0,n*sizeof（int））;//全部初始化为0

}

b=newint*[k+1];

for（i=0;i<=k;i++）

{

b[i]=newint[k+1];

//memset（（*s）+i,0,n*sizeof（int））;//全部初始化为0

}

for（i=1;i<=m;i++）

cin>>x[i];

for（j=1;j<=n;j++）

cin>>y[j];

zuichang（m,n,c,x,y,b）;

for（i=1;i<=m;i++）{

for（j=1;j<=n;j++）

cout<

cout<

}

LCS（m,n,x,b）;

cout<

cout<

return0;

}

从得到的实验程序与结果截图分析，两个公共的子序列不是连续的，与最长子串是有差别的。

两个序列的的子序列不止一个，但是最大的只有一个。

从算法上分析，该算法的空间、时间复杂度均为O（n^2），经过优化后，空间复杂度可为O（n）。

为了和上面的实验相比较，可以了解一下最长字段和的算法，求解是就是一段连续字段之和。

3、最长字段和

在一段序列中，找到使得和最大的字段，其中，找到的字段是连续的一段，可以用一般的算法求解，但是时间复杂度较高，所以可以通过动态规划减少时间复杂度.实验程序如下：

#include

usingnamespacestd;

intsummax（intn,int*a）

{

intsum=0;

intb=0;

for（inti=1;i<=n;i++）

{

if（b>0）b=b+a[i];

elseb=a[i];

if（b>sum）sum=b;

}

returnsum;

}

intmain（）

{

intn,i,sum=0;

cin>>n;

int*a=newint[n];

for（i=0;i

cin>>a[i];

summax（n,a）;

cout<

return0;

}

从得到的结果与实验程序分析，盖算法的时间复杂度比较底，但是没有找到起始元素与结束元素的坐标，所以该实验还有点改进。

4、凸多边形最优三角剖分

用多边形顶点的逆时针序列来表示一个凸多边形，即P={v0,v1,…,vn-1}表示具有n条边v0v1，v1v2，…,vn-1vn的一个凸多边形，其中，约定v0=vn。

若vi与vj是多边形上不相邻的两个顶点，则线段vivj称为多边形的一条弦。

弦将多边形分割成凸的两个子多边形{vi,vi+1,…,vj}和{vj,vj+1,…,vi}。

多边形的三角剖分是一个将多边形分割成互不相交的三角形的弦的集合T。

用多边形顶点的逆时针序列表示凸多边形，即P={v0,v1,…,vn-1}表示具有n条边的凸多边形。

若vi与vj是多边形上不相邻的2个顶点，则线段vivj称为多边形的一条弦。

弦将多边形分割成2个多边形{vi,vi+1,…,vj}和{vj,vj+1,…vi}。

多边形的三角剖分是将多边形分割成互不相交的三角形的弦的集合T。

给定凸多边形P，以及定义在由多边形的边和弦组成的三角形上的权函数w。

要求确定该凸多边形的三角剖分，使得即该三角剖分中诸三角形上权之和为最小。

凸多边形的三角剖分可用语法树来表示，例如：

令P={v0,v1,…,v6}，则树根v0v6是三角形v0v3v6的一条边，该三角形将原多边形分为3个部分：

三角形v0v3v6，凸多边形{v0,v1,…,v3}和凸多边形{v3,v4,…,v6}。

三角形v0v3v6的另外两条边，即弦v3v6和v0v3为根的两个儿子。

以它们为根的子树分别表示凸多边形{v0,v1,…,v3}和凸多边形{v3,v4,…,v6}的三角剖分。

定义t[i][j]，1≤i

为方便起见，设退化的多边形{vi-1,vi}具有权值0。

据此定义，要计算的凸（n+1）边形P的最优权值为t[1][n]。

因此可以将t[i][j]递归地定义为：

实验程序如下：

#include

#include

#include

usingnamespacestd;

structd

{

intx;

inty;

};

doublew（d*a,inti,intk,intj）//三角形三边之和

{

doublesum,sum1,sum2,sum3;

sum1=sqrt（（a[i].x-a[k].x）*（a[i].x-a[k].x）+（a[i].y-a[k].y）*（a[i].y-a[k].y））;

sum2=sqrt（（a[k].x-a[j].x）*（a[k].x-a[j].x）+（a[j].y-a[k].y）*（a[j].y-a[k].y））;

sum3=sqrt（（a[i].x-a[j].x）*（a[i].x-a[j].x）+（a[i].y-a[j].y）*（a[i].y-a[j].y））;

sum=sum1+sum2+sum3;

returnsum;

}

voidmwt（intn,double**t,int**s,d*a）//t[i][j]i,到j的最优值；

{

for（inti=0;i<=n;i++）t[i][i]=0;

for（i=2;i<=n;i++）

for（intr=1;r<=n-i+1;r++）

{

intj=i+r-1;

t[r][j]=t[r+1][j]+w（a,r-1,r,j）;

s[r][j]=r;

for（intk=r+1;k

{

doubleu=t[r][k]+t[k+1][j]+w（a,r-1,k,j）;

if（u

{

t[r][j]=u;

s[r][j]=k;

}

}

}

}

intmain（）

{

intn;

cout<<"请输入多边形顶点的个数n:

";

cin>>n;

d*a=newd[n];

cout<<"请输入多边形顶点的坐标:

";

for（inti=0;i

cin>>a[i].x>>a[i].y;

double**t=newdouble*[n];

int**s=newint*[n];

for（i=0;i

{

t[i]=newdouble[n];

s[i]=newint[n];

}

mwt（n-1,t,s,a）;

for（i=0;i

{

for（intj=0;j

cout<

cout<

}

return0;

}

从实验中可以分析出，凸多边形的最优三角剖分是一个几何问题，但通过分析，它本质上于矩阵连乘积的最优计算次序问题极为相似，从而可以将问题进行转化，用动态规划算法有效的解决这个问题。

5、多边形游戏

多边形游戏是一个单人玩的游戏，开始时有一个由n个顶点构成的多边形。

每个顶点被赋予一个整数值，每条边被赋予一个运算符“+”或“*”。

所有边依次用整数从1到n编号。

游戏第1步，将一条边删除。

随后n-1步按以下方式操作：

1.选择一条边E以及由E连接着的2个顶点V1和V2；2.用一个新的顶点取代边E以及由E连接着的2个顶点V1和V2。

将由顶点V1和V2的整数值通过边E上的运算得到的结果赋予新顶点。

最后，所有边都被删除，游戏结束。

游戏的得分就是所剩顶点上的整数值，对于给定的多边形，计算最高得分。

解决该问题的算法总体思想是采用动态规划策略：

（1）找出最优解的性质，并刻画其结构特征;

（2）递归地定义最优值;（3）以自底向上的方式计算出最优值;（4）根据计算最优值时得到的信息，构造最优解。

解决该问题的用动态规划的最优子结构，设所给的多边形的顶点和边的顺时针序列为op[1],v[1],op[2],v[2],op[3],…,op[n],v[n] 其中，op[i]表示第i条边所对应的运算符，v[i]表示第i个顶点上的数值，i=1~n。

设m[i,j,0]是链p（i,j）合并的最小值，而m[i,j,1]是最大值。

若最优合并在op[i+s]处将p（i,j）分为两个长度小于j的子链的最大值和最小值均已计算出。

即：

   a=m[i,s,0] b=m[i,s,1]  c=m[i,s,0] d=m[i,s,1];由于最优断开位置s有1<=s<=j-1的j-1中情况。

 初始边界值为：

m[i,1,0]=v[i]   1<=i<=n;m[i,1,1]=v[i]   1<=i<=n。

（1） 当op[i+s]=’+’时，m[i,j,0]=a+cm[i,j,1]=b+d

（2） 当op[i+s]=’*’时， m[i,j,0]=min{ac,ad,bc,bd}m[i,j,1]=max{ac,ad,bc,bd}

实验程序如下：

#include

#include

usingnamespacestd;

intm[1000][1000][2];

voidme（intn,inti,intj,intk,char*p,int&minf,int&maxf）

{inte[5];

inta=m[j][k][0],b=m[j][k][1],r=（j+k-1）%n+1,c=m[r][i-k][0],d=m[r][i-k][1];

if（p[r-1]=='+'）

{minf=a+c;maxf=b+d;}

else{

e[1]=a*c;e[2]=a*d;e[3]=b*c;e[4]=b*d;

minf=e[1];maxf=e[1];

for（intr=2;r<5;r++）

{

if（minf>e[r]）minf=e[r];

if（maxf

}

}

}

intmw（intn,char*p,intminf,intmaxf）

{

for（inti=2;i<=n;i++）//i个数

for（intj=1;j<=n;j++）//j起始点

for（intk=1;k

{

me（n,i,j,k,p,minf,maxf）;

if（m[j][i][0]>minf）m[j][i][0]=minf;

if（m[j][i][1]

}

inttemp=m[1][n][1];

for（i=2;i<=n;i++）

if（temp

returntemp;

}

intmain（）

{

inti,n,minf,maxf;

cout<<"请输入多边形顶点的个数n:

";

cin>>n;

char*p=newchar[n+1];

cout<<"请输入多边形顶点的权值m:

";

for（i=1;i<=n;i++）

{

cin>>m[i][1][0];

m[i][1][1]=m[i][1][0];

}

cout<<"请依次输入多边形边上的运算符p:

";

for（i=1;i<=n;i++）

cin>>p[i];

p[0]=p[n];

cout<

return0;

}

6、0-1背包问题

0-1背包是在M件物品取出若干件放在空间为W的背包里，每件物品的体积为W1，W2……Wn，与之相对应的价值为P1,P2……Pn求出获得最大价值的方案,在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包，不能将物品i装入背包多次，也不能直撞入部分物品i。

设所给的背包的子问题的最优解为m（i,j），即m（i,j）时背包为j，可选物品为i,i+1,...n时0-1背包问题的最优质。

由0-1背包问题的最有子结构性质，建立相应的递归式如下：

根据以上原理，编写的程序如下：

#include

usingnamespacestd;

#include

#defineMax100

intm[Max][Max];

intx[Max];

intw[Max];

intv[Max];

intmin（inta,intb）

{

returna

a:

b;

}

intmax（inta,intb）

{

returna>b?

a:

b;

}

voidOTbag（intc,intn）//m是二维数组，用来存储取值的背包号与该背包号的容量

{

intjMax=min（w[n]-1,c）;//初始化可以装的最大背包容量；

for（intj=0;j

for（j=w[n];j<=c;j++）m[n][j]=v[n];//

for（inti=n-1;i>1;i--）//如果背包剩余容量大于可以装的背包的容量大小

{

jMax=min（w[i]-1,c）;

for（j=0;j<=jMax;j++）m[i][j]=m[i+1][j];

for（intj=w[i];j<=c;j++）m[i][j]=max（m[i+1][j],m[i+1][j-w[i]]+v[i]）;

}

m[1][c]=m[2][c];

if（c>=w[1]）m[1][c]=max（m[1][c],m[2][c-w[1]]+v[1]）;

}

voidTraceback（intc,intn）

{

for（inti=1;i

if（m[i][c]==m[i+1][c]）x[i]=0;

else

{

x[i]=1;

c-=w[i];

}

x[n]=（m[n][c]）?

1:

0;

}

voidmain（）

{

intn,i,c;

cout<

cin>>n;

cout<

cin>>c;

cout<

for（i=0;i

{

cin>>v[i];

cin>>w[i];