文档介绍：芄动态规划的深入讨论芁芀东北育才学校李刚袈莃【关键字】动态规划、状态蚂【摘要】肂本文讨论了一种解决问题十分有效的技术——“动态规划”。它较高的解题效率一直受到很大的关注。本文首先对“动态规划”的理论基础进行了讨论。给出了一个用“动态规划”可以解决的问题的两个先决条件:“最优子结构”与“无后效性”。接着,讨论了在实际应用中的两个比较常见的问题:“动态规划”中状态的选定与存储。再通过以上问题的讨论,引出了“动态规划”的基本思维方法:“不做已经做过的工作”以及“动态规划”技术在解决问题中速度惊人的原因——“解决了查看中的冗余,达到了速度的极限”。最后,阐述了解决“动态规划”问题的一般步骤,即“思考,计划,应用”。蚇螇【正文】,特别是最近几年,“动态规划”作为一种解题工具,经常被提及。其应用范围愈来愈广,应用程度也愈来愈深。那么,“动态规划”究竟与其它的算法有什么差别?它有什么具体的应用价值呢?本文将对此进行讨论。螇我们先通过一个具体问题认识一下“动态规划”。蒄〖例1〗:图1中给出了一个地图,地图中每个顶点代表一个城市,两个城市间的连线代表道路,连线上的数值代表道路的长度。现在,我们想从城市A到达城市E,怎样走路程最短,最短路程的长度是多少?膂假设:葿Dis[X]为城市X到E的最短路线的长度;(X表示任意一个城市)袇 Map[I,J]表示I,J两个城市间的距离,若Map[I,J]=0,则两个城市不连通。袅蚀这个问题我们可以用搜索法来做,程序很容易写出来:芈羇Var羂Se:未访问的城市集合;莁羆FunctionLong(Who:当前访问城市):Integer;:求当前访问城市与城市E的最短距离。肇Begin莂IfWho=EThenSearch:=0蝿 Else聿Begin***Min:=Maxint;螃ForI取遍所有城市Do薁 If(Map[Who,I]>0)And(IInSe)Then螈 Begin芇 Se:=Se-[I];膄 J:=Map[Who,I]+Long(I);罿 Se:=Se+[I];薇 IfJ<MinThenMin:=J;莆 End;芁 Long:=Min;蚁End;莆 End;莆Begin蚂Se:=除A外所有城市的集合;腿Dis[A]:=Long(A);?我们可以看到,每次除了已经访问过的城市外,其他城市都要访问,所以时间复杂度为,这是一个“指数级”的算法,那么,还有没有更好的算法呢?袁首先,我们来观察一下这个算法。在求从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蒂ForX=阶段3的每个城市Downto阶段0的每个城市Do膀Begin蒇 Dis[X]:=Maxint;羆 ForY=阶段X的下一个阶段中的每个城市Do袃 IfDis[Y]+Map[X,Y]<Dis[X]Then羂 Dis[X]:=Dis[Y]+Map[X,Y];芆 End。羅 芄这个程序的时间复杂为,比上一个程序的复杂度要小得多。第二个算法就是“动态规划”算法。