动态规划的特点及其应用.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状态就是状态转移。状态转移是导出状态的途径,也是联系各阶段的途径。
说到这里,可以提出应用动态规划的一个重要条件。那就是将各阶段按照一定的次序排列好之后,对于某个给定的阶段状态,它以前各阶段的状态无法直接影响它未来的发展,而只能通过当前的这个状态。换句话说,每个状态都是“过去历史的一个完整总结[1]”。这就是无后效性。对这个性质,下文还将会有解释。
§
上面的阶段与状态只是多阶段决策问题的一个方面的要素,下面是另一个方面的要素——决策。
决策:当各段的状态取定以后,就可以做出不同的决定,从而确定下一阶段的状态,这种决定称为决策。表示决策的变量,称为决策变量,常用uk(sk)表示第k阶段当状态为sk时的决策变量。在实际问题中,决策变量的取值往往限制在一定范围内