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

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