《动态规划基本原理》由会员分享，可在线阅读，更多相关《动态规划基本原理（10页珍藏版）》请在金锄头文库上搜索。
1、动态规划基本原理近年来，涉及动态规划的各种竞赛题越来越多，每一年的 NOI 几乎都至少有一道题目需要用动态规划的方法来解决；而竞赛对选手运用动态规划知识的要求也越来越高，已经不再停留于简单的递推和建模上了。要了解动态规划的概念，首先要知道什么是多阶段决策问题。一、多阶段决策问题如果一类活动过程可以分为若干个互相联系的阶段，在每一个阶段都需作出决策(采取措施)，一个阶段的决策确定以后，常常影响到下一个阶段的决策，从而就完全确定了一个过程的活动路线，则称它为多阶段决策问题。各个阶段的决策构成一个决策序列，称为一个策略。每一个阶段都有若干个决策可供选择，因而就有许多策略供我们选取，对应于一个策略可以
2、确定活动的效果，这个效果可以用数量来确定。策略不同，效果也不同，多阶段决策问题，就是要在可以选择的那些策略中间，选取一个最优策略，使在预定的标准下达到最好的效果.让我们先来看下面的例子：如图所示的是一个带权有向的多段图，要求从 A 到 D 的最短路径的长度(下面简称最短距离)。我们可以搜索，枚举图中的每条路径，但当图的规模大起来时，搜索的效率显然不可能尽人意。让我们来试用动态规划的思路分析这道题：从图中可以看到，A 点要到达 D 点必然要经过 B1 和 B2 中的一个，所以 A 到 D 的最短距离必然等于 B1 到 D 的最短距离加上5，或是 B2 到 D 的最短距离加上 2。同样的，B1 到
3、 D 的最短距离必然等于 C1 到 D 的最短距离加上 3 或是 C2 到 D 的最短距离加上 2，。我们设 Gi为点 i 到点 D 的距离，显然 GC1=4，GC2=3，GC3=5，根据上面的分图 4-1 带权有向多段图析，有：GB1=minGC1+3，GC2+2=5，GB2=minGC2+7，GC3+4=9，再就有 GA=minGB1+5，GB2+2=10，所以 A 到 D 的最短距离是 10，最短路径是 AB1C2D。二、动态规划的术语1阶段把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于求解，过程不同，阶段数就可能不同描述阶段的变量称为阶段变量。在多数情况下，阶段变量是离散的
4、，用 k 表示。此外，也有阶段变量是连续的情形。如果过程可以在任何时刻作出决策，且在任意两个不同的时刻之间允许有无穷多个决策时，阶段变量就是连续的。在前面的例子中，第一个阶段就是点 A，而第二个阶段就是点 A 到点 B，第三个阶段是点 B 到点 C，而第四个阶段是点 C 到点 D。2状态状态表示每个阶段开始面临的自然状况或客观条件，它不以人们的主观意志为转移，也称为不可控因素。在上面的例子中状态就是某阶段的出发位置，它既是该阶段某路的起点，同时又是前一阶段某支路的终点。在前面的例子中，第一个阶段有一个状态即 A，而第二个阶段有两个状态 B1 和 B2，第三个阶段是三个状态 C1，C2 和 C3
5、，而第四个阶段又是一个状态 D。过程的状态通常可以用一个或”一组数”来描述，称为状态变量。一般，状态是离散的，但有时为了方便也将状态取成连续的。当然，在现实生活中，由于变量形式的限制，所有的状态都是离散的，但从分析的观点，有时将状态作为连续的处理将会有很大的好处。此外，状态可以有多个分量(多维情形)，因而用向量来代表；而且在每个阶段的状态维数可以不同。当过程按所有可能不同的方式发展时，过程各段的状态变量将在某一确定的范围内取值。状态变量取值的集合称为状态集合。3无后效性我们要求状态具有下面的性质：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所有各阶段都确定时
6、，整个过程也就确定了。换句话说，过程的每一次实现可以用一个状态序列表示，在前面的例子中每阶段的状态是该线路的始点，确定了这些点的序列，整个线路也就完全确定。从某一阶段以后的线路开始，当这段的始点给定时，不受以前线路（所通过的点）的影响。状态的这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展，这个性质称为无后效性。4决策一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择（行动）称为决策。在最优控制中，也称为控制。在许多问题中，决策可以自然而然地表示为一个数或一组数。不同的决策对应着不同的数值。描述决策的变量称决策变量，因状态满足无后效性，故在每个阶段选择决策时只需考虑
7、当前的状态而无须考虑过程的历史。决策变量的范围称为允许决策集合。5策略由每个阶段的决策组成的序列称为策略。对于每一个实际的多阶段决策过程，可供选取的策略有一定的范围限制，这个范围称为允许策略集合。允许策略集合中达到最优效果的策略称为最优策略。给定 k 阶段状态变量 x(k)的值后，如果这一阶段的决策变量一经确定，第 k+1 阶段的状态变量 x(k+1)也就完全确定，即 x(k+1)的值随 x(k)和第 k 阶段的决策 u(k)的值变化而变化，那么可以把这一关系看成(x(k)，u(k)与 x(k+1)确定的对应关系，用 x(k+1)=Tk(x(k),u(k)表示。这是从 k 阶段到 k+1 阶段
8、的状态转移规律，称为状态转移方程。6最优性原理作为整个过程的最优策略，它满足：相对前面决策所形成的状态而言，余下的子策略必然构成“最优子策略” 。最优性原理实际上是要求问题的最优策略的子策略也是最优。让我们通过对前面的例子再分析来具体说明这一点：从 A 到 D，我们知道，最短路径是 AB1C2D，这些点的选择构成了这个例子的最优策略，根据最优性原理，这个策略的每个子策略应是最优：AB1C2 是 A 到 C2 的最短路径，B1C2D 也是 B1 到 D 的最短路径事实正是如此，因此我们认为这个例子满足最优性原理的要求。线性动归阶段性动归树形动归多维空间动归二、例题：一般类试题（简单）例一 数塔问
9、题图示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路径，使该路径所经过的数字的总和最大。 每一步可沿左斜线向下或右斜线向下走； 1三角形行数100； 三角形中的数字为整数 0，1，99； 分析：如果采用贪心的方法，从起点 7 出发，选择 78175 这条路径得到的和是25，显然不是最优解，73875 得到的和是 30。所以不能用贪心的方法；如果用枚举搜索的方法，则当三角形的行数 n 过大时，时间上不可行。从顶点出发时到底向左走还是向右走并不取决于左右哪边的数字大，而取决于：左下和右下哪边累加下来的数字最大，只有左右两道路径上的最大值求出来了才能作出决策。同样的道理下一层的走向又要
10、取决于再下一层上的最大值是否已经求出才能决策。这样一层一层推下去，直到倒数第二层时就非常明了。如数字 2，只要选择它下面较大值的结点5 前进就可以了。所以实际求解时，可从底层开始往上推，层层递进，最后得到最大值。数据结构：用 fi,j表示在 i、j 这个位置能取得的最大值，ai,j表示当前位置的值。则: fi,j=maxfi+1,j，fi+1,j+1 +ai,j以上的方法就是使用的动态规划的思想，动态规划严格来说并不是一种算法，它既可以用递推的方式实现，也可以用递归的方式实现，当问题比较简单，容易找出递推关系和递推边界的时候，就可以用递推的方式去实现，而有的时候用递归的方式则比较容易写出递归关
11、系式。动态规划是一种记忆化搜索，将中间计算的结果保存在数组之中，避免之后的重复运算，提高了效率，这也是动态规划与递归递推的不同之处所在。 例二 最长不下降子序列设有一个正整数的序列：b1, b2, bn, 对于下标 i1b(n)则存在长度为 1 的不下降序列 b(n-1)或 b(n)。设 F(i)为前 i 个数中的最大不下降序列，则 F(i)为之前所有节点中最大的一个+1,即：F(1)、F(2)、F(3)F(i-3)、F(i-2)、F(i-1)中最大的一个加上 1。注意：并不是 F(i-1)+1。F(I) = MaxF(j)+1 | j I 且 bj = bi(其中 in，j=i+1,i+2,
12、，n)，边界是 F(1)=1;例三：buy low,buy lower例四：最短路径如图所示是城市道路示意图，每条边上的数字为该段街道的长度。求从 A 点到 B 点的最短路径长度（只能往上和往右走）分析：此题和数塔问题很类似，可以划分为一个多阶段决策的问题来解决。按照动态规划自顶向下分析，自底向上计算的思路。设 wi,j表示该位置到 A 点的最短路径，LXi,j表示点（i-1,j）到点(i,j)垂直方向上的距离，LYi,j表示点（i,j-1）到点(i,j)水平方向上的距离，则不难推出方程：wi,j=min(wi-1,j+LXi,j),wi,j-1+LYi,j)w0,0=0 /递归或递推边界例五
13、：0/1 背包问题问题描述：有 n 件物品 x1, x2, , xn , 每件物品有一个价值和一个重量，分别记为： v1,v2, vn w1,w2, wn 其中所有的 wi 均为整数。 现有一个背包，其最大载重量为 m，要求从这 n 件物品中任取若干件（这些物品每样只有一件，要么被装入要么被留下）。问背包中装入哪些物品可使得所装物品的价值和最大？ （我们只需要求出最大价值，不需要求出具体拿的是哪些物品）例如，m=23, n = 5, vi : 19 24 33 45 50 wi : 5 6 8 11 12 最大价值为：95分析：如果想用贪心，先求出平均价值，然后从高到低的方法来取，如果有一个背
14、包的容量为 10，共有 3 个物品，体积分别是 3、3、5，价值分别是 6、6、9，那么你的方法取到的是前两个物品，总价值是 12，但明显最大值是后两个物品组成的 15。因此贪心的方法不能得到正确结果。换一个更简单的方式来思考：每个物品只有 2 种选择，要么放入，要么不放入。（1）放入：问题转换为在背包载重为 m-wi 的情况下，在其它 n-1 件物品中挑选，求得价值和最大。等把这个子问题求出后，再加上 vi 的价值就是整个问题的最优解了。 （2） 没放入：那么就当 xi 根本不存在，直接解物品数量为 n-1，背包载重为 m 的子问题。子问题的最优解就是问题的最优解。定义函数 f(i,j)为在
15、 1i 件物品中选若干件装入限重为 j 的背包中的最大价值和， 那么根据上面关于第 i 件物品是否装入了背包的情况分析，我们得出关系式： (1)当第 I 件物品要装入背包时，f(i,j) := (i-1 件物品，限重为 j-wi的最优解)+ vi, 即： f(i,j) := f(i-1, j-wi) + vi 当然，第 i 件物品要装入是有条件限制的：第 i 件物品重量小于等于背包限重，即 wi = j （2）当第 i 件物品不装入背包时，f(i,j) :=i-1 件物品，限重为 m 的最优解，即： f(i,j) := f(i-1, j) 求得装入或者不装入第 i 件物品的限重为 J 的背包的
16、最大价值，只需要比较这两种情况下谁的价值更大，更大者为当前问题的最优解。f(i,j)=max f(i-1, j-wi) + vi , f(i-1, j) 该方程递归结束的边界条件是：当 j=0 时，f(i,0)=0。在按自底向上的动态规划方式求解问题时，其实主要就是做一件事： 按问题规模从小到大地求解问题，把每阶段求得的问题的最优解保存在表格（数组）中，以便在下一阶段求解更大的问题时，可以直接查表引用子问题的最优解。 （类似于递推）阶段的分析： 将 n 件物品放入背包，故可以把阶段划分为 n 个。把在前 I 件物品中选取物品放入背包作为第 I 个阶段。状态的分析：在第 i 个阶段有多少个状态呢?因为包的容量为 m，故在每个 i 阶段都有 m
