acm动态规划总结竞赛资源-CSDN文库

共17个文件

htm：9个

doc：4个

txt：4个

动态规划

需积分: 9 53 浏览量 2009-04-06 16:18:29 上传评论 1 收藏 293KB RAR 举报

资源推荐

资源详情

资源评论

收起资源包目录

DP.rar （17个子文件）

动态规划DP

动态规划的状态表示(三).htm 7KB

轮船问题点评.htm 7KB

动态规划题库.txt 9KB

动态规划2.htm 5KB

把握本质，灵活运用——动态规划的深入探讨.doc 260KB

动态规划的特点及其应用.doc 255KB

动态规划描述.txt 2KB

动态规划的状态表示(一).htm 11KB

动态规划的表示法.txt 15KB

旅行问题题解.txt 3KB

动态规划1.htm 6KB

动态规划的深入讨论.doc 263KB

动态规划的状态表示(二).htm 10KB

剪枝优化—动态规划在剪枝中的运用.htm 35KB

递推运用及优化—比较递推与动态规划的区别.htm 13KB

动态规划在信息学奥林匹克竞赛中的应用.htm 10KB

动态规划.doc 148KB

动态规划的深入讨论

东北育才学校李刚

【关键字】动态规划、状态

【摘要】

本文讨论了一种解决问题十分有效的技术——“动态规划”。

它较高的解题效率一直受到很大的关注。本文首先对“动态规划”

的理论基础进行了讨论。给出了一个用“动态规划”可以解决的问

题的两个先决条件：“最优子结构”与“无后效性”。接着，讨论了

在实际应用中的两个比较常见的问题：“动态规划”中状态的选定

与存储。再通过以上问题的讨论，引出了“动态规划”的基本思维

方法：“不做已经做过的工作”以及“动态规划”技术在解决问题中

速度惊人的原因——“解决了查看中的冗余，达到了速度的极限”。

最后，阐述了解决“动态规划”问题的一般步骤，即“思考，计划，

应用”。

【正文】

一．引论

在信息学竞赛中，特别是最近几年，“动态规划”作为一种解题工具，经常

被提及。其应用范围愈来愈广，应用程度也愈来愈深。那么，“动态规划”究竟

与其它的算法有什么差别？它有什么具体的应用价值呢？本文将对此进行讨论。

我们先通过一个具体问题认识一下“动态规划”。

〖例 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;

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 相连通的城市 }

注：可以把

看成第

个阶段，

看成第

个阶段。

程序：

Dis[E]=0

For X=阶段 3 的每个城市 Downto 阶段 0 的每个城市 Do

Begin

Dis[X]:=Maxint;

For Y=阶段 X 的下一个阶段中的每个城市 Do

If Dis[Y]+Map[X,Y]<Dis[X] Then

Dis[X]:=Dis[Y]+Map[X,Y];

End。

这个程序的时间复杂为，比上一个程序的复杂度要小得多。

第二个算法就是“动态规划”算法。

二．动态规划的理论基础

通过上面的例子，我们对“动态规划”有了一个初步认识，它所处理的问题

是一个“多阶段决策问题”。我们现在对一些概念进行具体定义：

状态（State）：它表示事物的性质，是描述“动态规划”中的“单元”的量。

如例 1 中的城市 A，B1，D2，E 都为单个的状态。

阶段（Stage）：阶段是一些性质相近，可以同时处理的状态集合。通常，

一个问题可以由处理的先后次序划分为几个阶段。如例 1 中的问题由三个阶段

组成，其中阶段 1 包含状态 B1，B2。实际上，阶段只是标识那些处理方法相同、

处理顺序无关的状态。一个阶段既可以包含多个状态，也可以只包含一个状态

其关系很类似分子与原子的关系。

状态转移方程：是前一个阶段的状态转移到后一个的状态的演变规律，是

关于两个相邻阶段状态的方程，是“动态规划”的中心。

决策（Decision）：每个阶段做出的某种选择性的行动。它是我们程序所

需要完成的选择。

动态规划所处理的问题是一个“多阶段决策问题”，一般由初始状态开始，

通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，

同时确定了完成整个过程的一条活动路线（通常是求最优的活动路线）。如图

3 所示。

总体上来说，一个“动态规划”算法应该包含上面提到的几种基本关系与属

性。

那么，什么样的“决策问题”才可以划分阶段，来用“动态规划”求解呢？

我们说一个“决策问题”只有具有以下性质时，才可以考虑划分阶段，用“动态

规划”算法：

一：最优子结构

即一个问题的最优解只取决于其子问题的最优解，也就是说，非最优解对

问题的求解没有影响。在例 1 中，如果我们想求 Dis[B1]的最小值，我们只需要

知道 C1，C2，C3 的最小值，而不用考虑其他的路径，因为其他的非最优路径

肯定对 Dis[B1]的结果没有影响。我们再来看一个问题：

〖例 2〗有 4 个点，分别是 A、B、C、D，如图 4 所示，相邻两点用两条连线

C2k,C2k-1(1≤k≤3)表示两条通行的道路。连线上方的数字表示道路的长度。

我们定义从 A 到 D 的所有路径中，长度除以 4 所得余数最小的路径为最优路径。

求一条最优路径。

在这个题目中，我们如果还按照刚才的方法来求解就会发生错误。例如，按

照例 1 的思维，A 最优取值可以由 B 的最优取值来确定，而 B 的最优取值为

0，所以 A 的最优值为 2，而实际上，路径 C1—C3—C5 可得最优值为 0，所

以，B 的最优路径并不是 A 最优路径的子路径，也就是说，A 的最优取值不是

由 B 的最优取值决定的，其不具有最优子结构。

由此可见，并不是所有的“决策问题”都可以用“动态规划”来解决。所以，只

有当一个问题呈现出最优子结构时，“动态规划”才可能是一个合适的侯选方法。

二：无后效性

即一个问题被划分阶段后，阶段 I 中的状态只能由阶段 I+1 中的状态通过

状态转移方程得来，与其他状态没有关系，特别是与未发生的状态没有关系，

这就是无后效性。实际上，如果我们把这个问题中的状态定义成图中的顶点，

两个状态之间的转移定义为边，转移过程中的权值增量定义为边的权值，则这

个问题实际上就是在一个“有向无环加权图”中寻找两个顶点路径的问题。因为

无后效性，所以没有环路（否则，无论如何划分阶段，都可以出现后效性）。

即这个图可以进行“拓扑排序”，那么，我们至少可以以他们拓扑排序的顺序划

分阶段。

我们来看一个具体例子：

〖例 3〗：欧几里德货郎担问题是对平面给定的 n 个点确定一条连结各点的、

闭合的游历路线问题。图 5(a)给出了七个点问题的解。Bitonic 旅行路线问题

评论收藏

内容反馈

wswyb001

粉丝: 8
资源: 74

acm动态规划总结竞赛

NOI&&NOIP;近几年竞赛真题

45道动态规划题目分析.ppt

国际大学生程序设计竞赛例题解．三：图论、动态规划算法、综合题专集

acm动态规划总结

acm竞赛穷举法总结

acm动态规划

acm递归算法总结竞赛

2016年ACM常用算法总结

acm竞赛分治算法总结

最小生成树总结acm竞赛

ACM大牛总结的线段树专辑,超经典的-1

acm之动态规划 经典题分析

acm动态规划50题

acm 杭电课件之动态规划

acm竞赛贪心算法总结

acm动态规划经典题

acm竞赛回溯算法总结

kuangbin的ACM模板（新）_ACM模板_ACM算法总结_

ACM学习总结

C++ STL库函数总结（纯手打，主要偏向ACM竞赛方面使用）

STL总结，acm竞赛可以看一下

acm资料（动态规划）

动态规划的漂亮打印 acm

动态规划 华科 acm

acm课件3 动态规划

acm 动态规划 超级经典

ACM竞赛主流算法总结

acm常用算法总结

最新资源

acm之动态规划经典题分析

动态规划华科 acm

acm 动态规划超级经典