算法合集之《动态规划的特点及其应用》.doc

IOI2000集训队论文动态规划的特点及其应用张辰
第页共NUMPAGES30页
动态规划的特点及其应用
安徽张辰

目录
(点击进入)HYPERLINK\l"keywords"【关键词】
HYPERLINK\l"summary"【摘要】
HYPERLINK\l"text"【正文】
HYPERLINK\l"chapter1"§1动态规划的本质
HYPERLINK\l"chapter11"§1.1多阶段决策问题
HYPERLINK\l"chapter12"§1.2阶段与状态
HYPERLINK\l"chapter13"§1.3决策和策略
HYPERLINK\l"chapter14"§1.4最优化原理与无后效性
HYPERLINK\l"chapter15"§1.5最优指标函数和规划方程
HYPERLINK\l"chapter2"§2动态规划的设计与实现
HYPERLINK\l"chapter21"§2.1动态规划的多样性
HYPERLINK\l"chapter22"§2.2动态规划的模式性
HYPERLINK\l"chapter23"§2.3动态规划的技巧性
HYPERLINK\l"chapter3"§3动态规划与一些算法的比较
HYPERLINK\l"chapter31"§3.1动态规划与递推
HYPERLINK\l"chapter32"§3.2动态规划与搜索
HYPERLINK\l"chapter33"§3.3动态规划与网络流
HYPERLINK\l"chapter4"§4结语
HYPERLINK\l"appendix"【附录：部分试题与源程序】
HYPERLINK\l"appendix1"1.“花店橱窗布置问题”试题
HYPERLINK\l"appendix2"2.“钉子与小球”试题
HYPERLINK\l"appendix3"3.例2“花店橱窗布置问题”方法1的源程序
HYPERLINK\l"appendix4"4.例2“花店橱窗布置问题”方法2的源程序
HYPERLINK\l"appendix5"5.例3“街道问题”的扩展
HYPERLINK\l"appendix6"6.例4“mod4最优路径问题”的源程序
HYPERLINK\l"appendix7"7.例5“钉子与小球”的源程序
HYPERLINK\l"appendix8"8.例6的源程序,“N个人的街道问题”
HYPERLINK\l"bibliography"【参考文献】【关键词】动态规划阶段
【摘要】
动态规划是信息学竞赛中的常见算法，本文的主要内容就是分析它的特点。
文章的第一部分首先探究了动态规划的本质，因为动态规划的特点是由它的本质所决定的。第二部分从动态规划的设计和实现这两个角度分析了动态规划的多样性、模式性、技巧性这三个特点。第三部分将动态规划和递推、搜索、网络流这三个相关算法作了比较，从中探寻动态规划的一些更深层次的特点。
文章在分析动态规划的特点的同时，还根据这些特点分析了我们在解题中应该怎样利用这些特点，怎样运用动态规划。这对我们的解题实践有一定的指导意义
【正文】
动态规划是编程解题的一种重要的手段，在如今的信息学竞赛中被应用得越来越普遍。最近几年的信息学竞赛，不分大小，几乎每次都要考察到这方面的内容。因此，如何更深入地了解动态规划，从而更为有效地运用这个解题的有力武器，是一个值得深入研究的问题。
要掌握动态规划的应用技巧，就要了解它的各方面的特点。首要的，是要深入洞悉动态规划的本质。
§1动态规划的本质
动态规划是在本世纪50年代初，为了解决一类多阶段决策问题而诞生的。那么，什么样的问题被称作多阶段决策问题呢？
§1.1多阶段决策问题
说到多阶段决策问题，人们很容易举出下面这个例子。
7
4
38
6
7
5
46

5
6

A1
B1
B2
C1
C2
C3
D1
多段图中的最短路径问题：在下图中找出从A1到D1的最短路径。
仔细观察这个图不难发现，它有一个特点。我们将图中的点分为四类（图中的A、B、C、D），那么图中所有的边都处于相邻的两类点之间，并且都从前一类点指向后一类点。这样，图中的边就被分成了三类（AB、BC、CD）。我们需要从每一类中选出一条边来，组成从A1到D1的一条路径，并且这条路径是所有这样的路径中的最短者。
从上面的这个例子中，我们可以大概地了解到什么是多阶段决策问题。更精确的定义如下：
多阶段决策过程，是指这样的一类特殊的活动过程，问题可以按时间顺序分解成若干相互联系的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决策序列HYPERL