动态规划.docx
《动态规划.docx》由会员分享，可在线阅读，更多相关《动态规划.docx（36页珍藏版）》请在冰点文库上搜索。
动态规划
第一章什么叫动态规划
1.1多阶段决策过程的最优化问题
1、问题的提出
首先，例举一个典型的且很直观的多阶段决策问题:
[例]下图表示城市之间的交通路网，线段上的数字表示费用，单向通行由A->E。
求A->E的最省费用。
如图从A到E共分为4个阶段，即第一阶段从A到B，第二阶段从B到C，第三阶段从C到D，第四阶段从D到E。
除起点A和终点E外，其它各点既是上一阶段的终点又是下一阶段的起点。
例如从A到B的第一阶段中，A为起点，终点有B1，B2，B3三个，因而这时走的路线有三个选择，一是走到B1，一是走到B2，一是走到B3。
若选择B2的决策，B2就是第一阶段在我们决策之下的结果，它既是第一阶段路线的终点，又是第二阶段路线的始点。
在第二阶段，再从B2点出发，对于B2点就有一个可供选择的终点集合（C1，C2，C3）；若选择由B2走至C2为第二阶段的决策，则C2就是第二阶段的终点，同时又是第三阶段的始点。
同理递推下去，可看到各个阶段的决策不同，线路就不同。
很明显，当某阶段的起点给定时，它直接影响着后面各阶段的行进路线和整个路线的长短，而后面各阶段的路线的发展不受这点以前各阶段的影响。
故此问题的要求是：
在各个阶段选取一个恰当的决策，使由这些决策组成的一个决策序列所决定的一条路线，其总路程最短。
具体情况如下：
（1）由目标状态E向前推，可以分成四个阶段，即四个子问题。
如上图所示。
（2）策略：
每个阶段到E的最省费用为本阶段的决策路径。
（3）D1，D2是第一次输人的结点。
他们到E都只有一种费用，在D1框上面标5，D2框上面标2。
目前无法定下，那一个点将在全程最优策略的路径上。
第二阶段计算中，5，2都应分别参加计算。
（4）C1，C2，C3是第二次输入结点，他们到D1，D2各有两种费用。
此时应计算C1，C2，C3分别到E的最少费用。
C1的决策路径是min{（C1D1），（C1D2）}。
计算结果是C1+D1+E，在C1框上面标为8。
同理C2的决策路径计算结果是C2+D2+E，在C2框上面标为7。
同理C3的决策路径计算结果是C3+D2+E，在C3框上面标为12。
此时也无法定下第一，二阶段的城市那二个将在整体的最优决策路径上。
（5）第三次输入结点为B1，B2，B3，而决策输出结点可能为C1，C2，C3。
仿前计算可得Bl，B2，B3的决策路径为如下情况。
Bl:
B1C1费用12+8=20，路径:
B1+C1+D1+E
B2:
B2C1费用6+8=14，路径:
B2+C1+D1+E
B3:
B2C2费用12+7=19，路径:
B3+C2+D2+E
此时也无法定下第一，二，三阶段的城市那三个将在整体的最优决策路径上。
（6）第四次输入结点为A，决策输出结点可能为B1，B2，B3。
同理可得决策路径为
A：
AB2，费用5+14=19，路径A+B2+C1+D1+E。
此时才正式确定每个子问题的结点中，那一个结点将在最优费用的路径上。
19将结果显然这种计算方法，符合最优原理。
子问题的决策中，只对同一城市（结点）比较优劣。
而同一阶段的城市（结点）的优劣要由下一个阶段去决定。
1.2动态规划的概念
在上例的多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化问题的方法为动态规划方法。
与穷举法相比，动态规划的方法有两个明显的优点:
（1）大大减少了计算量
（2）丰富了计算结果
从上例的求解结果中，我们不仅得到由A点出发到终点E的最短路线及最短距离，而且还得到了从所有各中间点到终点的最短路线及最短距离，这对许多实际问题来讲是很有用的。
动态规划的最优化概念是在一定条件下，我到一种途径，在对各阶段的效益经过按问题具体性质所确定的运算以后，使得全过程的总效益达到最优。
应用动态规划要注意阶段的划分是关键，必须依据题意分析，寻求合理的划分阶段（子问题）方法。
而每个子问题是一个比原问题简单得多的优化问题。
而且每个子问题的求解中，均利用它的一个后部子问题的最优化结果，直到最后一个子问题所得最优解，它就是原问题的最优解。
1.3动态规划适合解决什么样的问题
准确地说，动态规划不是万能的，它只适于解决一定条件的最优策略问题。
或许，大家听到这个结论会很失望：
其实，这个结论并没有削减动态规划的光辉，因为属于上面范围内的问题极多，还有许多看似不是这个范围中的问题都可以转化成这类问题。
上面所说的“满足一定条件”主要指下面两点：
（1）状态必须满足最优化原理；
（2）状态必须满足无后效性。
动态规划的最优化原理是无论过去的状态和决策如何，对前面的决策所形成的当前状态而言，余下的诸决策必须构成最优策略。
可以通俗地理解为子问题的局部最优将导致整个问题的全局最优在上例中例题1最短路径问题中，A到E的最优路径上的任一点到终点E的路径也必然是该点到终点E的一条最优路径，满足最优化原理。
动态规划的无后效性原则某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响。
也就是说，“未来与过去无关”，当前的状态是此前历史的一个完整总结，此前的历史只能通过当前的状态去影响过程未来的演变。
具体地说，如果一个问题被划分各个阶段之后，阶段I中的状态只能由阶段I+1中的状态通过状态转移方程得来，与其他状态没有关系，特别是与未发生的状态没有关系，这就是无后效性。
第二章用动态规划法解题
2.1为什么要用动态规划法解题
首先，看下面一个问题:
【例题1】数字三角形问题。
7
38
810
2774
55265
示出了一个数字三角形宝塔。
数字三角形中的数字为不超过100的正整数。
现规定从最顶层走到最底层，每一步可沿左斜线向下或右斜线向下走。
假设三角形行数≤100，编程求解从最顶层走到最底层的一条路径，使得沿着该路径所经过的数字的总和最大，输出最大值。
输人数据：
由文件输入数据，文件第一行是三角形的行数N。
以后的N行分别是从最顶层到最底层的每一层中的数字。
如输入：
5
7
38
810
2774
45265
输出：
30
【分析】对于这一问题，很容易想到用枚举的方法（深度搜索法）去解决，即列举出所有路径并记录每一条路径所经过的数字总和。
然后寻找最大的数字总和，这一想法很直观，很容易编程实现其程序如下：
programsjx;
constmaxn=10;
var
a:
array[1..maxn,1..maxn]ofinteger;
max:
longint;
n,i,j:
integer;
fname:
string;
inputf:
text;
proceduretry（x,y,dep:
integer;sum:
longint）;
begin
if（dep=n）then
begin
ifsum>maxthen max:
=sum;
exit
end;
try（x+1,y,dep+1,sum+a[x+1,y]）;
try（x+1,y+1,dep+1,sum+a[x+1,y+1]）;
end;
begin
readln（fname）;
assign（inputf,fname）;
reset（inputf）;
readln（inputf,n）;
fori:
=1tondo
forj:
=1toido
read（inputf,a[i,j]）;
max:
=0;
try（1,1,1,a[1,1]）;
writeln（max）;
end.
但是当行数很大时，当三角形的行数等于100时，其枚举量之大是可想而知的，用枚举法肯定超时，甚至根本不能得到计算结果，必须用动态规划法来解。
2.2怎样用动态规划法解题
1.逆推法:
按三角形的行划分阶段，若行数为n，则可把问题看做一个n-1个阶段的决策问题。
先求出第n-1阶段（第n-1行上各点）到第n行的的最大和，再依次求出第n-2阶段、第n-3阶段……第1阶段（起始点）各决策点至第n行的最佳路径。
设：
f[i,j]为从第i阶段中的点j至第n行的最大的数字和；
则:
f[n,j]=a[n,j] 1<=j<=n
f[i,j]=max{a[i,j]+f[i+1,j],a[i,j]+f[i+1,j+1]} 1<=j<=i.
f[1,1]即为所求。
程序如下：
programdatasjx;
constmaxn=100;
var
fname:
string;
inputf:
text;
n,i,j:
integer;
a:
array[1..maxn,1..maxn]ofinteger;
f:
array[1..maxn,1..maxn]ofinteger;
begin
readln（fname）;
assign（inputf,fname）;
reset（inputf）;
readln（inputf,n）;
fori:
=1tondo
forj:
=1toido
read（inputf,a[i,j]）;
fori:
=1tondo
f[n,i]:
=a[n,i];
fori:
=n-1downto1do
forj:
=1toido
iff[i+1,j]>f[i+1,j+1]thenf[i,j]:
=a[i,j]+f[i+1,j]
elsef[i,j]:
=a[i,j]+f[i+1,j+1];
writeln（f[1,1]）;
end.
2.顺推法
按三角形的行划分阶段，若行数为n，则可把问题看做一个n-1个阶段的决策问题。
先求第2行各元素到起点的最大和
再依次求出第3,4，5,......,.n-1,n到起点的最大和,最后找第n行的最大值
设f[i,j]为第i行第j列上点到起点的最大和
则f[1，1]=a[1,1];
f[i，1]=a[i,1]+f[i-1,1];
f[i，j]=max{a[i,j]+f[i-1,j-1],a[i,j]+f[i-1,j]} 2<=j<=i
max（f[n,1],f[n,2],.......,f[n,n]}即为所求。
程序如下：
programdatasjx;
constmaxn=100;
var
fname:
string;
inputf:
text;
n,i,j:
integer;
a:
array[1..maxn,1..maxn]ofinteger;
f:
array[1..maxn,1..maxn]ofinteger;
maxsum:
integer;
begin
readln（fname）;
assign（inputf,fname）;
reset（inputf）;
readln（inputf,n）;
fori:
=1tondo
forj:
=1toido
read（inputf,a[i,j]）;
fillchar（f,sizeof（f）,0）;
f[1,1]:
=a[1,1];
fori:
=2tondo
begin
f[i,1]:
=a[i,1]+f[i-1,1];
forj:
=2toido
iff[i-1,j-1]>f[i-1,j]thenf[i,j]:
=a[i,j]+f[i-1,j-1]
elsef[i,j]:
=a[i,j]+f[i-1,j];
end;
maxsum:
=0;
fori:
=1tondo
iff[n,i]>maxsumthenmaxsum:
=f[n,i];
writeln（maxsum）;
end.
说明一下：
1.用动态规划解题主要思想是用空间换时间.
2.本题如果n较大，用2维数组空间可能不够,可以使用1维数组.
程序如下:
programdatasjx;
constmaxn=100;
var
fname:
string;
inputf:
text;
n,i,j:
integer;
a:
array[1..maxn,1..maxn]ofinteger;
f:
array[1..maxn]ofinteger;
maxsum:
integer;
begin
readln（fname）;
assign（inputf,fname）;
reset（inputf）;
readln（inputf,n）;
fori:
=1tondo
forj:
=1toido
read（inputf,a[i,j]）;
fillchar（f,sizeof（f）,0）;
f[1]:
=a[1,1];
fori:
=2tondo
begin
forj:
=idownto2do
iff[j-1]>f[j]thenf[j]:
=a[i,j]+f[j-1]
elsef[j]:
=a[i,j]+f[j];
f[1]:
=a[i,1]+f[1];
end;
maxsum:
=0;
fori:
=1tondo
iff[i]>maxsumthenmaxsum:
=f[i];
writeln（maxsum）;
end.
练习:
用一维数组和逆推法解本题.
2.3用动态规划法解题的一般模式
动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。
这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线（通常是求最优的活动路线）。
如图所示。
动态规划的设计都有着一定的模式，一般要经历以下几个步骤。
┌───┐┌───┐┌───┐
初始状态→│决策１│→│决策２│→…→│决策ｎ│→结束状态
└───┘└───┘└───┘
（1）划分阶段：
按照问题的时间或空间特征，把问题分为若干个阶段。
在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。
（2）确定状态和状态变量：
将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。
当然，状态的选择要满足无后效性。
（3）确定决策并写出状态转移方程：
因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。
所以如果确定了决策，状态转移方程也就可写出。
但事实上常常是反过来做，根据相邻两段各状态之间的关系来确定决策。
（4）寻找边界条件：
给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。
（5）程序设计实现：
动态规划的主要难点在于理论上的设计，一旦设计完成，实现部分就会非常简单。
根据上述动态规划设计的步骤，可得到大体解题框架如下:
1.初始化（边界条件）
2.fori:
=2ton（顺推法） 或fori:
=n-1to1（逆推法）
对i阶段的每一个决策点求局部最优
3.确定和输出结束状态的值.
第三章典型例题与习题
3.1最长不降子序列
（1）问题描述
设有由n个不相同的整数组成的数列，记为:
a
（1）、a
（2）、……、a（n）且a（i）<>a（j） （i<>j）
例如3，18，7，14，10，12，23，41，16，24。
若存在i1如上例中3，18，23，24就是一个长度为4的不下降序列，同时也有3，7，10，12，16，24长度为6的不下降序列。
程序要求，当原数列给出之后，求出最长的不下降序列。
（2）算法分析
根据动态规划的原理，由后往前进行搜索。
1·对a（n）来说，由于它是最后一个数，所以当从a（n）开始查找时，只存在长度为1的不下降序列；
2·若从a（n-1）开始查找，则存在下面的两种可能性：
①若a（n-1）②若a（n-1）>a（n）则存在长度为1的不下降序列a（n-1）或a（n）。
3·一般若从a（i）开始，此时最长不下降序列应该按下列方法求出:
在a（i+1）,a（i+2）,…,a（n）中，找出一个比a（i）大的且最长的不下降序列，作为它的后继。
4.用数组b（i）,c（i）分别记录点i到n的最长的不降子序列的长度和点i后继接点的编号
（3）程序如下:
（逆推法）
programli1;
constmaxn=100;
vara,b,c:
array[1..maxn]ofinteger;
fname:
string;
f:
text;
n,i,j,max,p:
integer;
begin
readln（fname）;
assign（f,fname）;
reset（f）;
readln（f,n）;+
fori:
=1tondo
begin
read（f,a[i]）;
b[n]:
=1;
c[n]:
=0;
end;
fori:
=n-1downto1do
begin
max:
=0;p:
=0;
forj:
=i+1tondo
if（a[i]max）then beginmax:
=b[j];p:
=jend;
ifp<>0thenbeginb[i]:
=b[p]+1;c[i]:
=pend
end;
max:
=0;p:
=0;
fori:
=1tondo
ifb[i]>maxthenbeginmax:
=b[i];p:
=iend;
writeln（'maxlong=',max）;
write（'resultis:
'）;
whilep<>0do
beginwrite（a[p]:
5）;p:
=c[p]end;
end.
3.2背包问题
背包问题有三种
1.部分背包问题
一个旅行者有一个最多能用m公斤的背包，现在有n种物品，它们的总重量分别是W1，W2，...,Wn,它们的总价值分别为C1,C2,...,Cn.求旅行者能获得最大总价值。
解决问题的方法是贪心算法:
将C1/W1,C2/W2,...Cn/Wn,从大到小排序,不停地选择价值与重量比最大的放人背包直到放满为止.
2.0/1背包
一个旅行者有一个最多能用m公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn,它们的价值分别为C1,C2,...,Cn.若每种物品只有一件求旅行者能获得最大总价值。
<1>分析说明:
显然这个题可用深度优先方法对每件物品进行枚举（选或不选用0,1控制）.
程序简单,但是当n的值很大的时候不能满足时间要求，时间复杂度为O（2n）。
按递归的思想我们可以把问题分解为子问题,使用递归函数
设f（i，x）表示前i件物品，总重量不超过x的最优价值
则f（i，x）=max（f（i－1，x-W[i]）+C[i]，f（i－1，x））
f（n，m）即为最优解，边界条件为f（0，x）＝0 ，f（i,0）=0;
动态规划方法（顺推法）程序如下:
程序如下：
programknapsack02;
constmaxm=200;maxn=30;
typear=array[1..maxn]ofinteger;
varm,n,j,i:
integer;
c,w:
ar;
f:
array[0..maxn,0..maxm]ofinteger;
functionmax（x,y:
integer）:
integer;
begin
ifx>ythenmax:
=xelsemax:
=y;
end;
begin
readln（m,n）;
fori:
=1tondo
readln（w[i],c[i]）;
fori:
=1tomdof（0,i）:
=0;
fori:
=1tondof（i,0）:
=0;
fori:
=1tondo
forj:
=1tomdo
begin
ifj>=w[i] thenf[i,j]:
=max（f[i-1,j-w[i]]+c[i],f[i-1,j]）
elsef[i,j]:
=f[i-1,j];
end;
writeln（f[n,m]）;
end.
使用二维数组存储各子问题时方便，但当maxm较大时如maxn=2000时不能定义二维数组f,怎么办,其实可以用一维数组,但是上述中j:
=1tom要改为j:
=mdownto1,为什么?
请大家自己解决。
3.完全背包问题
一个旅行者有一个最多能用m公斤的背包，现在有n种物品，每件的重量分别是W1，W2，...,Wn,
每件的价值分别为C1,C2,...,Cn.若的每种物品的件数足够多.
求旅行者能获得的最大总价值。
本问题的数学模型如下：
设f（x）表示重量不超过x公斤的最大价值，
则f（x）=max{f（x-w[i]）+c[i]} 当x>=w[i]1<=i<=n
程序如下:
（顺推法）
programknapsack04;
constmaxm=2000;maxn=30;
typear=array[0..maxn]ofinteger;
varm,n,j,i,t:
integer;
c,w:
ar;
f:
array[0..maxm]ofinteger;
begin
readln（m,n）;
fori:
=1tondo
readln（w[i],c[i]）;
f（0）:
=0;
fori:
=1tomdo
forj:
=1tondo
begin
ifi>=w[j] thent:
=f[i-w[j]]+c[j];
ift>f[i]thenf[i]:
=t
end;
writeln（f[m]）;
end.
3.3最短路径
问题描述：
如图：
求v1到v10的最短路径长度及最短路径。
图的邻接矩阵如下：
0251-1-1-1-1-1-1
-10-1-11214-1-1-1-1
-1-10-16104-1-1-1
-1-1-10131211-1-1-1
-1-1-1-10-1-139-1
-1-1-1-1-10-165-1
-1-1-1-1-1-10
升级会员 