对信息学竞赛中动态规划问题的认识与思考.doc

【关键字】动态规划、状态 【摘要】本文讨论了-?种解决问题十分有效的技术一动态规划。它较高的 解题效率一直受到很大的关注。本文首先对动态规划的理论基础进行了讨论。 给出了一个用动态规划可以解决的问题的两个先决条件：“最优子结构”与 “无后效性”。接着，讨论了在实际应用中的两个比较常见的问题：动态规划 中状态的选定与存储。再通过以上问题的讨论，引出了动态规划的基本思维方 法：“不做已经做过的工作”以及“动态规划”技术在解决问题中速度惊人的 原因一解决了查看中的兀余，达到了速度的极限。最后，阐述了解决动态规划 问题的一般步骤，即思考，计划，应用。 【正文】 一 ?引论 在信息学竞赛中，特别是最近儿年，“动态规划”作为一种解题工具，经 常被提及。其应用范围愈来愈广，应用程度也愈来愈深。那么，“动态规划” 究竟与其它的算法有什么差别？它有什么具体的应用价值呢？本文将对此进行 讨论。 我们先通过一个具体问题认识一下“动态规划”。 （图1） K例1U：图1中给出了一个地图，地图中每个顶点代表一个城市，两个城市 间的连线代表道路，连线上的数值代表道路的长度。现在，我们想从城市A到 达城市E,怎样走路程最短，最短路程的长度是多少？ 假设: Dis[X]为城市X到E的最短路线的长度；（X表示任意一个城市） Map[I,Jl表示I, J两个城市间的距离，若Map[I, J]=0,则两个城市不 连通。 这个问题我们可以用有哪些信誉好的足球投注网站法来做，程序很容易写岀来: Var Se:未访问的城市集合; 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 JMin Then Min:=J; End; Long:=Min; End; End; Begin Se:二除A外所有城市的集合； Dis[A]:=Long(A); End. 这个程序的效率如何呢？我们可以看到，每次除了已经访问过的城市外, 其他城市都要访问，所以时间复杂度为O(N!),这是一个“指数级”的算法, 那么，还有没有更好的算法呢？ 首先，我们来观察一下这个算法。在求从B1到E的最短路径的时候，先 求岀从C2到E的最短路径；而在求从B2到E的最短路径的时候，乂求了一遍 从C2到E的最短路径。也就是说，从C2到E的最短路径我们求了两遍。同样 可以发现，在求从Cl、C2到E的最短路径的过程中，从D1到E的最短路径也 被求了两遍。而在整个程序中，从D1到E的最短路径被求了四遍，这是多么 大的一个浪费啊！如果在求解的过程中,同时将求得的最短路径的距离“记录 在案”，随时调用，那会是多么的方便啊! 于是，一个新的思路诞生了，即：由后往前依次推出每个Dis值，直到推 出Dis[A]为止。这个思路的确很好，但等等，究竟什么是“由后往前”呢？ 所谓“后”、“前”是我们自己为城市编的序号，当两个城市I, J的前 后顺序定为I “前” J “后”时，必须满足这个条件： 或者 I, J 不连通，或者 Dis[I]+Map[I,J]^Dis[J]o 因为如果I, J连通且Dis[I]+Map[I,J]Dis[J],则说明Dis[J]存在更优的情 况，可J位于I后，就不可能推出此情况，会影响最后的解。那么，我们如何划 分先后次序呢? （图2） 如图2所示。我用不同颜色给城市分阶段，可以用阶段表示每个城市的次 序，因为阶段的划分有如下性质： 1：阶段I的取值只与阶段1+1有关，阶段I的取值只对阶段1?1的取值产 生影响; 2：每个阶段的顺序是确定的，不可以调换任两个阶段顺序; 通过这两个性质，可以推岀阶段作为“前”、“后”顺序满足刚才提出的 条件，所以我们可以用阶段作为每个城市的次序，然后从阶段3倒推至阶段 1,再推出Dis[A]。 公式：Dis[X]=Min{ Dis[Y]： Y是下一个阶段中与X相连通的城市}注:可以把E看成第4个阶段,A看成第0个阶段。 程序: Dis[E]=O For X二阶段3的 每个城市Downto阶段0的每个城市Do Begin Dis[X]:=Maxint; For Y二阶段X的下一个阶段中的每个城市Do If Dis[Y]+Map[X,Y]Dis[X] ThenDis[X]:=Dis[Y]+Map[X,Y]; Endo 这个程序的时间复杂为0(2),比上一个程序的复杂度0(N!)要小得多。第 二个算法就是“动态规划”算法。 二.动态规划的理论基础 通过上面的例子，我们对“动态规划”有了一个初步认识，它所处理的问 题是