动态规划的深入讨论论文.docx

动态规划的深入讨论

【关键字】动态规划、状态
【摘要】
本文讨论了一种解决问题十分有效的技术——“动态规划”。它较高的解题效率一直受到很大的关注。本文首先对“动态规划”的理论基础进行了讨论。给出了一个用“动态规划”可以解决的问题的两个先决条件:“最优子结构”与“无后效性”。接着,讨论了在实际应用中的两个比较常见的问题:“动态规划”中状态的选定与存储。再通过以上问题的讨论,引出了“动态规划”的基本思维方法:“不做已经做过的工作”以及“动态规划”技术在解决问题中速度惊人的原因——“解决了查看中的冗余,达到了速度的极限”。最后,阐述了解决“动态规划”问题的一般步骤,即“思考,计划,应用”。
【正文】

在信息学竞赛中,特别是最近几年,“动态规划”作为一种解题工具,经常被提及。其应用范围愈来愈广,应用程度也愈来愈深。那么,“动态规划”究竟与其它的算法有什么差别?它有什么具体的应用价值呢?本文将对此进行讨论。
我们先通过一个具体问题认识一下“动态规划”。
〖例1〗:图1中给出了一个地图,地图中每个顶点代表一个城市,两个城市间的连线代表道路,连线上的数值代表道路的长度。现在,我们想从城市A到达城市E,怎样走路程最短,最短路程的长度是多少?
假设:
Dis[X]为城市X到E的最短路线的长度;(X表示任意一个城市)
Map[I,J]表示I,J两个城市间的距离,若Map[I,J]=0,则两个城市不连通。
这个问题我们可以用搜索法来做,程序很容易写出来:
Var
Se:未访问的城市集合;

Function Long(Who:当前访问城市):Integer; :求当前访问城市与城市E的最短距离。
Begin
If Who=E Then Search:=0
Else
Begin
Min:=Maxint;
For I取遍所有城市 Do
If (Map[Who,I]>0) And (I In Se) Then
Begin
Se:=Se-[I];
J:=Map[Who,I]+Long(I);
Se:=Se+[I];
If J<Min Then Min:=J;
End;
Long:=Min;
End;
End;
Begin
Se:=除A外所有城市的集合;
Dis[A]:=Long(A);
End.
这个程序的效率如何呢?我们可以看到,每次除了已经访问过的城市外,其他城市都要访问,所以时间复杂度为,这是一个“指数级”的算法,那么,还有没有更好的算法呢?
首先,我们来观察一下这个算法。在求从B1到E的最短路径的时候,先求出从C2到E的最短路径;而在求从B2到E的最短路径的时候,又求了一遍从C2到E的最短路径。也就是说,从C2到E的最短路径我们求了两遍。同样可以发现,在求从C1、C2到E的最短路径的过程中,从D1到E的最短路径也被求了两遍。而在整个程序中,从D1到E的最短路径被求了四遍,这是多么大的一个浪费啊!如果在求解的过程中,同时将求得的最短路径的距离“记录在案”,随时调用,那会是多么的方便啊!
于是,一个新的思路诞生了,即:由后往前依次推出每个Dis值,直到推出Dis[A]为止。这个思路的确很好,但等等,究竟什么是“由后往前”呢?
所谓“后”、“前”是我们自己为城市编的序号,当两个城市I,J的前后顺序定为I“前”J“后”时,必须满足这个条件:
或者I,J不连通,或者Dis[I]+Map[I,J]≥Dis[J]。
因为如果I,J连通且Dis[I]+Map[I,J]<Dis[J],则说明Dis[J]存在更优的情况,可J位于I后,就不可能推出此情况,会影响最后的解。那么,我们如何划分先后次序呢?
如图2所示。我用不同颜色给城市分阶段,可以用阶段表示每个城市的次序,因为阶段的划分有如下性质:
1:阶段I的取值只与阶段I+1有关,阶段I的取值只对阶段I-1的取值产生影响;
2:每个阶段的顺序是确定的,不可以调换任两个阶段顺序;
通过这两个性质,可以推出阶段作为“前”、“后”顺序满足刚才提出的条件,所以我们可以用阶段作为每个城市的次序,然后从阶段3倒推至阶段1,再推出Dis[A]。
公式:Dis[X]=Min{ Dis[Y]:Y是下一个阶段中与X相连通的城市}
注:可以把E看成第4个阶段,A看成第0个阶段。
程序:

Dis[E]=0
For X=阶段3的每个城市Downto 阶段0的每个城市 Do
Begin
Dis[X]:=Maxint;
For Y=阶段X的下一个阶段中的每个城市 Do
If Dis[Y]+Map[X,Y]<Dis[