文档介绍：动态规划基本原理
近年来,涉及动态规划的各种竞赛题越来越多,每一年的NOI几乎都至少有一道题目需要用动态规划的方法来解决;而竞赛对选手运用动态规划知识的要求也越来越高,已经不再停留于简单的递推和建模上了。
要了解动态规划的概念,首先要知道什么是多阶段决策问题。
一、多阶段决策问题
如果一类活动过程可以分为若干个互相联系的阶段,在每一个阶段都需作出决策(采取措施),一个阶段的决策确定以后,常常影响到下一个阶段的决策,从而就完全确定了一个过程的活动路线,则称它为多阶段决策问题。
各个阶段的决策构成一个决策序列,称为一个策略。每一个阶段都有若干个决策可供选择,因而就有许多策略供我们选取,对应于一个策略可以确定活动的效果,这个效果可以用数量来确定。策略不同,效果也不同,多阶段决策问题,就是要在可以选择的那些策略中间,选取一个最优策略,使在预定的标准下达到最好的效果.
图4-1 带权有向多段图
让我们先来看下面的例子:如图所示的是一个带权有向的多段图,要求从A到D的最短
路径的长度(下面简称最短距离)。
我们可以搜索,枚举图中的每条路径,但当图的规模大起来时,搜索的效率显然不可能尽人意。让我们来试用动态规划的思路分析这道题:从图中可以看到,A点要到达D点必然要经过B1和B2中的一个,所以A到D的最短距离必然等于B1到D的最短距离加上5,或是B2到D的最短距离加上2。同样的,B1到D的最短距离必然等于C1到D的最短距离加上3或是C2到D的最短距离加上2,……。
我们设G[i]为点i到点D的距离,显然G[C1]=4,G[C2]=3,G[C3]=5,根据上面的分析,有:
G[B1]=min{G[C1]+3,G[C2]+2}=5,
G[B2]=min{G[C2]+7,G[C3]+4}=9,
再就有G[A]=min{G[B1]+5,G[B2]+2}=10,
所以A到D的最短距离是10,最短路径是AàB1àC2àD。
二、动态规划的术语
把所给求解问题的过程恰当地分成若干个相互联系的阶段,以便于求解,过程不同,。在多数情况下,阶段变量是离散的,用k表示。此外,也有阶段变量是连续的情形。如果过程可以在任何时刻作出决策,且在任意两个不同的时刻之间允许有无穷多个决策时,阶段变量就是连续的。
在前面的例子中,第一个阶段就是点A,而第二个阶段就是点A到点B,第三个阶段是点B到点C,而第四个阶段是点C到点D。
状态表示每个阶段开始面临的自然状况或客观条件,它不以人们的主观意志为转移,也称为不可控因素。在上面的例子中状态就是某阶段的出发位置,它既是该阶段某路的起点,同时又是前一阶段某支路的终点。
在前面的例子中,第一个阶段有一个状态即A,而第二个阶段有两个状态B1和B2,第三个阶段是三个状态C1,C2和C3,而第四个阶段又是一个状态D。
过程的状态通常可以用一个或”一组数”来描述,称为状态变量。一般,状态是离散的,但有时为了方便也将状态取成连续的。当然,在现实生活中,由于变量形式的限制,所有的状态都是离散的,但从分析的观点,有时将状态作为连续的处理将会有很大的好处。此外,状态可以有多个分量(多维情形),因而用向量来代表;而且在每个阶段的状态维数可以不同。
当过程按所有可能不同的