动态规划的特点及其应用.docx

动态规划的特点及其应用
目录
（点击进入）
【关键词】
【摘要】
【正文】
§ 1动态规划的本质
§
§
§
§
§
§ 2动态规划的设计与实现
§
§
§
§ 3动态规划与一些算法的比较
§
§ §
§ 4结语 【附录：部分试题与源程序】
“花店橱窗布置问题”试题
“钉子与小球”试题
例2 “花店橱窗布置问题”方法 1的源程序
例2 “花店橱窗布置问题”方法 2的源程序
例3 “街道问题”的扩展
例4 “ mod 4最优路径问题”的源程序
例5 “钉子与小球”的源程序
例6的源程序，“ N个人的街道问题” 【参考文献】
【关键词】动态规划 阶段
【摘要】
动态规划是信息学竞赛中的常见算法，本文的主要内容就是分析它的特点。
文章的第一部分首先探究了动态规划的本质，因为动态规划的特点是由它的本质所决定的。 第二部分从动态规划的设计和实现这两个角度分析了动态规划的多样性、模式性、技巧性这三个 特点。第三部分将动态规划和递推、搜索、网络流这三个相关算法作了比较，从中探寻动态规划 的一些更深层次的特点。
文章在分析动态规划的特点的同时， 还根据这些特点分析了我们在解题中应该怎样利用这些
特点，怎样运用动态规划。这对我们的解题实践有一定的指导意义。
【正文】
动态规划是编程解题的一种重要的手段，在如今的信息学竞赛中被应用得越来越普遍。最近 几年的信息学竞赛，不分大小，几乎每次都要考察到这方面的内容。因此，如何更深入地了解动 态规划，从而更为有效地运用这个解题的有力武器，是一个值得深入研究的问题。
要掌握动态规划的应用技巧，就要了解它的各方面的特点。首要的，是要深入洞悉动态规划 的本质。
§ 1动态规划的本质
动态规划是在本世纪 50年代初，为了解决一类多阶段决策问题而诞生的。 那么，什么样的问
题被称作多阶段决策问题呢？
§
说到多阶段决策问题，人们很容易举出下面这个例子。
［例1］多段图中的最短路径问题：在下图中找出从 Ai到D的最短路径。
仔细观察这个图不难发现，它有一个特点。我们将图中的点分为四类（图中的 A、B、C D）,
那么图中所有的边都处于相邻的两类点之间，并且都从前一类点指向后一类点。这样，图中的边 就被分成了三类（A B、B C、CD）。我们需要从每一类中选出一条边来，组成从 A1到D1的一
条路径，并且这条路径是所有这样的路径中的最短者。
从上面的这个例子中，我们可以大概地了解到什么是多阶段决策问题。更精确的定义如下：
多阶段决策过程，是指这样的一类特殊的活动过程，问题可以按时间顺序分解成若干相互联
系的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决策序列 [1]。要使整个活动的总
体效果达到最优的问题，称为 多阶段决策问题。
从上述的定义中，我们可以明显地看出，这类问题有两个要素。一个是阶段，一个是决策。
§
阶段：将所给问题的过程，按时间或空间特征分解成若干相互联系的阶段，以便按次序去求 每阶段的解。常用字母 k表示阶段变量。[1]
阶段是问题的属性。多阶段决策问题中通常存在着若干个阶段，如上面的例子，就有 A、B
C、D这四个阶段。在一般情况下，阶段是和时间有关的；但是在很多问题(我的感觉，特别是信 息学问题)中，阶段和时间是无关的。从阶段的定义中，可以看出阶段的两个特点，一是“相互 联系”，二是“次序”。
阶段之间是怎样相互联系的？就是通过状态和状态转移。
状态：各阶段开始时的客观条件叫做状态。描述各阶段状态的变量称为状态变量，常用 sk表
示第k阶段的状态变量，状态变量 sk的取值集合称为状态集合，用 Q表示。⑴
状态是阶段的属性。每个阶段通常包含若干个状态，用以描述问题发展到这个阶段时所处在 的一种客观情况。 在上面的例子中，行人从出发点 Ai走过两个阶段之后， 可能出现的情况有三种， 即处于Ci、C2或C3点。那么第三个阶段就有三个状态 S3={Cl,C2,C3}。
每个阶段的状态都是由以前阶段的状态以某种方式“变化”而来，这种“变化”称为状态转
移(暂不定义)。上例中G点可以从Bi点过来，也可以从 B2点过来，从阶段2的B或B2状态走到 阶段3的C3状态就是状态转移。状态转移是导出状态的途径，也是联系各阶段的途径。
说到这里，可以提出应用动态规划的一个重要条件。那就是将各阶段