国家集训队2000论文集李刚论文

《国家集训队2000论文集李刚论文》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

2、述了解决“动态规划”问题的一般步骤，即“思考，计划，应用”O【正文】一•引论在信息学竞赛中，特别是最近几年，“动态规划”作为一种解题工具，经常被提及。其应用范围愈来愈广，应用程度也愈来愈深。那么，“动态规划”究竟与其它的算法有什么差别？它有什么具体的应用价值呢？木文将对此进行讨论。我们先通过一个具体问题认识一卜•“动态规划”。(图1)K例llh图1屮给出了一个地图，地图屮每个顶点代表一个城市，两个城市间的连线代表道路，连线上的数值代表道路的长度。现在，我们想从城市A到达城市E,怎样走路程最短，最短路程的长度是多少？假设：Dis[X]为城市X到

3、E的最短路线的氏度；（X表示任意一个城帀）Map[I,Jl表示I,J两个城市间的距离，若Map[I,J1=O,则两个城市不连通。这个问题我们可以用搜索法来做，程序很容易写出来:VarSe:未访问的城市集合；FunctionLong(Who:当前访问城市):Integer;:求当前访问城市与城市E的最短距离。BeginIfWho=EThenSearch:=0ElseBeginMin:=Maxint;ForI取遍所有城市DoIf(Map[Who,I]>0)And(IInSe)ThenBeginSe:=Se-[I];J:=Map[Who,I]+Lo

4、ng(I);Se:=Se+[I];IfJ

5、径我们求了两遍。同样可以发现，在求从Cl、C2到E的最短路径的过程屮，从D1至IJE的最短路径也被求了两遍。而在整个程序中，从D1至IJE的最短路径被求了四遍，这是多么大的一个浪费啊！如果在求解的过程屮,同时将求得的最短路径的距离“记录在案”，随时调用，那会是多么的方便啊！于是，一个新的思路诞生了，BP：由后往前依次推出每个Dis值，直到推岀Dis[A]为止。这个思路的确很好，但等等，究竟什么是“由后往前”呢？所谓“后”、“前”是我们自己为城市编的序号，当两个城市I,J的前后顺序定为I“前”J“后”吋，必须满足这个条件：或者I,J不连通，或者

6、Dis[I]+Map[I,J]MDis[J]。况,因为如果I,J连通且Dis[I]+Map[I,J]

7、，所以我们可以用阶段作为每个城市的次序，然后从阶段3倒推至阶段1,再推出Dis[A]o公式：Dis[X]=Min{Dis[Y]：Y是下一个阶段中与X相连通的城市}注:可以把E看成第4个阶段,A看成第0个阶段。程序:Dis[E]=OForX二阶段3的每个城市Downto阶段0的每个城市DoBeginDis[X]:=Maxint;ForY二阶段X的下一个阶段中的每个城市DoIfDis[Y]+Map[X,Y]

8、得多。第二个算法就是“动态规划”算法。二.动态规划的理论基础通过上面的例子，我们对“动态规划”有了一个初步认识，它所处理的问题是一个“多阶段决策问题”o我们现在对一