第六章动态规划方法 S1动态规划算法的基本思想 动态规划方法是处理分段过程最优化问题的一类及其有效的方法。在 实际生活中,有一类问题的活动过程可以分成若干个阶段,而且在任 阶段后的行为依赖于该阶段的状态,而与该阶段之前的过程如何达 到这种状态的方式无关。这类问题的解决是多阶段的决策过程。在 50年代,贝尔曼( Richard bellman)等人提出了解决这类问题的“最 优化原理”,从而创建了最优化问题的一种新的算法设计方法一动态 规划。 最优化原理:多阶段过程的最优决策序列应当具有性质:无论过程的 初始状态和初始决策是什么,其余的决策都必须相对于初始决策 所产生的状态构成一个最优决策序列。 对于一个多阶段过程问题,上述最优决策是否存在依赖于该问题是否 有最优子结构性质:原问题的最优解包含了其子问题的最优解。而能 否采用动态规划的方法还要看该问题的子问题是否具有重叠性质。后 面将会看到问题的子结构性质和子问题重叠性质是采用动态规划算 法的两个基本要素。先看两个例子 例1.多段图问题 设G=(VE)是一个赋权有向图,其顶点集V被划分成k>2个不相 交的子集V:1≤≤k,其中,V1和Ⅴ分别只有一个顶点s(称为源)和 个顶点t(称为汇),图中所有的边(uv)的始点和终点都在相邻的两个子
第六章 动态规划方法 §1 动态规划算法的基本思想 动态规划方法是处理分段过程最优化问题的一类及其有效的方法。在 实际生活中，有一类问题的活动过程可以分成若干个阶段，而且在任 一阶段后的行为依赖于该阶段的状态，而与该阶段之前的过程如何达 到这种状态的方式无关。这类问题的解决是多阶段的决策过程。在 50 年代，贝尔曼（Richard Bellman）等人提出了解决这类问题的“最 优化原理”，从而创建了最优化问题的一种新的算法设计方法－动态 规划。 最优化原理：多阶段过程的最优决策序列应当具有性质：无论过程的 初始状态和初始决策是什么，其余的决策都必须相对于初始决策 所产生的状态构成一个最优决策序列。 对于一个多阶段过程问题，上述最优决策是否存在依赖于该问题是否 有最优子结构性质：原问题的最优解包含了其子问题的最优解。而能 否采用动态规划的方法还要看该问题的子问题是否具有重叠性质。后 面将会看到问题的子结构性质和子问题重叠性质是采用动态规划算 法的两个基本要素。先看两个例子： 例1． 多段图问题 设 G=(V,E)是一个赋权有向图，其顶点集 V 被划分成 k>2 个不相 交的子集 Vi: 1≤i≤k，其中，V1和 Vk分别只有一个顶点 s(称为源)和一 个顶点 t(称为汇)，图中所有的边(u,v)的始点和终点都在相邻的两个子
集V和V计+中:u∈V,v∈V+1。 一个5阶段的网络图 多阶段图问题:求由s到t的最小成本路径。 对于每一条由s到t的路径,可以把它看成在k-2个阶段作出的某个 决策序列的相应结果:第i步决策就是确定V*1中那个顶点在这条路 径上。今假设s,v2,V3,,vk-t,t是一条由s到t的最短路径,再假定 从源点s(初始状态)开始,已经作出了到顶点v2的决策(初始决策),则 2就是初始决策产生的状态。若将v2看成是原问题的子问题的初始 状态,解这个子问题就是找一条由v2到t的最短路径。事实上,这条 最短路径一定是v2,V3,…,Vkl,to不然,设v2,q3,…,qk-,t是一条由 v2到t的比v2,v3,…,vk-1,t更短的路径,则s,v2,q3,…,qk,t是一条 由s到t的比s,V2,V,…,vk-l,t更短的路径。与前面的假设矛盾。这 说明多段图问题具有最优子结构性质。 例2.经典0/1背包问题 有n件物品,第i件重量和价值分别是w和pi=1,2,…,n。要 将这n件物品的一部分装入容量为c的背包中,要求每件物品或整个
集 Vi和 Vi＋1中：u∈Vi，v∈Vi＋1。 V1 V2 V3 V4 V5 4 6 9 4 4 2 5 7 2 S 7 3 2 t 3 1 11 5 2 5 11 6 8 一个 5 阶段的网络图 多阶段图问题：求由 s 到 t 的最小成本路径。 对于每一条由 s 到 t 的路径，可以把它看成在 k-2 个阶段作出的某个 决策序列的相应结果：第 i 步决策就是确定 Vi+1中那个顶点在这条路 径上。今假设 s, v2, v3, … , vk-1, t 是一条由 s 到 t 的最短路径，再假定 从源点 s(初始状态)开始，已经作出了到顶点 v2 的决策(初始决策),则 v2 就是初始决策产生的状态。若将 v2 看成是原问题的子问题的初始 状态，解这个子问题就是找一条由 v2到 t 的最短路径。事实上，这条 最短路径一定是 v2, v3, … , vk-1, t。不然，设 v2, q3, … , qk-1, t 是一条由 v2到 t 的比 v2, v3, … , vk-1, t 更短的路径，则 s, v2, q3, … , qk-1, t 是一条 由 s 到 t 的比 s, v2, v3, … , vk-1, t 更短的路径。与前面的假设矛盾。这 说明多段图问题具有最优子结构性质。 例2． 经典 0/1 背包问题 有 n 件物品，第 i 件重量和价值分别是 wi和 pi, i=1, 2, …, n。要 将这 n 件物品的一部分装入容量为 c 的背包中，要求每件物品或整个 1 2 4 6 9 10 11 12 3 7 8 5
装入或不装入,不许分割出一部分装入。0/1背包问题就是要给装包 算法,使得装入背包的物品的总价值最大。这个问题归结为数学规划 问题: max∑Px ∑ 1:X:≤ 0,1},i=1,2,…,n (6.1) 0/1背包问题具有最优子结构性质。事实上,若y,y2…,yn是最优解, 则y2…y将是是0/1背包问题的子问题 max∑P 2≤i≤n st.∑w1x≤c-W,x1∈{0.1},=2,…,n (62 2≤i<n 最优解。因为,若y2…,yn是子问题(62)的最优解,且使得 ∑py>∑py (6.3) 2≤i≤n 则y1,y2…,y’n将是原问题(61)的可行解,并且使得 Py+∑Py1>∑P1y (64) 这与y,y2,…,yn是最优解相悖。 例3.矩阵连乘问题 给定n个数字矩阵A1,A2,,An,其中A1与A1是可乘的, 1=1,2,,n-1求矩阵连乘A1A2…An的加括号方法,使得所用的数乘次 数最少。 考察两个矩阵相成的情形:C=AB.如果矩阵A,B分别是pXr 和r×q矩阵,则它们的乘积C将是p×q矩阵,其(i,j)元素为 (65 i=1,…p,j=1,,q,因而AB所用的数乘次数是prq。如果有至少3个
装入或不装入，不许分割出一部分装入。0/1 背包问题就是要给装包 算法，使得装入背包的物品的总价值最大。这个问题归结为数学规划 问题： ∑ ≤i≤n i i p x 1 max s.t. w x c x i n i i n i i , {0,1}, 1,2, , 1 ∑ ≤ ∈ = L ≤ ≤ （6.1） 0/1 背包问题具有最优子结构性质。事实上，若 n y , y , , y 1 2 L 是最优解， 则 n y , , y 2 L 将是是 0/1 背包问题的子问题 ∑ ≤i≤n i i p x 2 max s.t. w x c w x i n i i n i i , {0,1}, 2, , 1 2 ∑ ≤ − ∈ = L ≤ ≤ (6.2) 最优解。因为，若 n y' , , y' 2 L 是子问题(6.2)的最优解，且使得 ∑ ≤i≤n i i p y 2 ' > ∑ ≤i≤n i i p y 2 (6.3) 则 n y , y' , , y' 1 2 L 将是原问题(6.1)的可行解，并且使得 ∑ ≤ ≤ + i n i i p y p y 2 1 1 ' > ∑ ≤i≤n i i p y 1 (6.4) 这与 n y , y , , y 1 2 L 是最优解相悖。 例3． 矩阵连乘问题 给定 n 个数字矩阵 A1，A2，…，An，其中 Ai与 Ai+1是可乘的， i=1,2,…,n-1.求矩阵连乘 A1A2⋅⋅⋅An 的加括号方法，使得所用的数乘次 数最少。 考察两个矩阵相成的情形：C=AB.如果矩阵 A，B 分别是 p×r 和 r×q 矩阵，则它们的乘积 C 将是 p×q 矩阵，其(i, j)元素为 ∑ = = r k ij ik kj c a b 1 (6.5) i=1,…,p, j=1,…,q, 因而 AB 所用的数乘次数是 prq。如果有至少 3 个
以上的矩阵连乘则涉及到乘积次序问题,即加括号方法。例如3个 矩阵连乘的加括号方法有两种:(A1A2)A3)和(A1(A2A3)。设A1,A2, A3分别是p×p1,p×p2,p2×p3矩阵,则以上两种乘法次序所用的 数乘次数分别为:popp2+pop2p3和popp3+pp2p3。如果po=10,p1=100, p2=5,p3=50,则两种乘法所用的数乘次数分别为:7500和750000可 见,由于加括号的方法不同,使得连乘所用的数乘次数有很大差别。 对于n个矩阵的连乘积,令P(n)记连乘积的完全加括号数,则有如下 递归关系 P(n)={ ∑P(k)P(mn-k)n>1 (66) k=1 由此不难算出P=C(n-1),其中C表示 Catalan数: 1(2n =92(4"n32) (67) n+1(n 也就是说,P(n)是随n指数增长的,所以,我们不能希望列举所有可 能次序的连乘积,从中找到具有最少数乘次数的连乘积算法。事实上 矩阵连乘积问题具有最优子结构性质,我们可以采用动态规划的方 法,在多项式时间内找到最优的连乘积次序。 用A[ij表示连乘积AA+1…A,分析计算Aln]的一个最优次序 设这个计算次序在矩阵Ak和Ax+1之间将矩阵连分开,1≤kn,则完 全加括号方式为(A1A2…Ak)(Ak+…A),依此次序,我们先分别计算 A[1k]和A[k+ln],然后将计算的结果相乘得到A[ln]。可见,A[ln 的一个最优序所包含的矩阵计算子链A[k]和A[k+1n]的次序也一定 是最优的。也就是说,矩阵连乘问题具有最优子结构性质
以上的矩阵连乘则涉及到乘积次序问题，即加括号方法。例如 3 个 矩阵连乘的加括号方法有两种：((A1A2)A3)和(A1(A2A3))。设 A1，A2， A3 分别是 p0×p1，p1×p2，p2×p3 矩阵，则以上两种乘法次序所用的 数乘次数分别为：p0p1p2+p0p2p3和 p0p1p3+p1p2p3。如果 p0=10, p1=100, p2=5, p3=50, 则两种乘法所用的数乘次数分别为：7500 和 750000。可 见，由于加括号的方法不同，使得连乘所用的数乘次数有很大差别。 对于 n 个矩阵的连乘积，令 P(n)记连乘积的完全加括号数，则有如下 递归关系 − > = = ∑ − = 1 1 ( ) ( ) 1 1 1 ( ) n k P k P n k n n P n (6.6) 由此不难算出 P=C(n-1),其中 C 表示 Catalan 数： (4 / ) 2 1 1 ( ) 3 / 2 n n n n C n n = Ω + = (6.7) 也就是说，P(n)是随 n 指数增长的，所以，我们不能希望列举所有可 能次序的连乘积，从中找到具有最少数乘次数的连乘积算法。事实上， 矩阵连乘积问题具有最优子结构性质，我们可以采用动态规划的方 法，在多项式时间内找到最优的连乘积次序。 用 A[i:j]表示连乘积 AiAi＋1⋅⋅⋅Aj.分析计算 A[1:n]的一个最优次序。 设这个计算次序在矩阵 Ak 和 Ak+1 之间将矩阵连分开，1≤k<n，则完 全加括号方式为((A1A2⋅⋅⋅Ak)( Ak＋1⋅⋅⋅An))，依此次序，我们先分别计算 A[1:k]和 A[k+1:n]，然后将计算的结果相乘得到 A[1:n]。可见，A[1:n] 的一个最优序所包含的矩阵计算子链A[1:k]和A[k+1:n]的次序也一定 是最优的。也就是说，矩阵连乘问题具有最优子结构性质
如上三个例子都具有最优子结构性质,这个性质决定了解决此类 问题的基本思路是:首先确定原问题的最优值和其子问题的最优值之 间的递推关系,然后自底向上递归地构造出最优解。最优子结构性质 是最优化原理得以采用的先决条件。一般说来,分阶段选择策略确定 最优解的问题往往会形成一个决策序列。 Bellman认为,利用最优化 原理以及所获得的递推关系式去求解最优决策序列,可以使枚举数量 急剧下降。这里有一个问题值得注意:最优子结构性质提示我们使用 最优化原理产生的算法是递归算法,这很可能会增加时间与空间复杂 度。例如,用递归式直接计算矩阵连乘积A[ln]的算法 RecurMatrix Chain的时间复杂度将是2(2): 计算矩阵连乘的递归算法 int RecurMatrix Chain(int 1, int, j, int p) if(i-j return O int u=Recur Matrix Chain(i, 1) +RecurMatrix Chain(i+1j +p[i-1]*p[i]*p[] SGF=i for(int k=i+l; kj; k++) int t=RecurMatrix Chain(i, k) +Recur Matrix Chain(k+1, j +p[i-1]*p[i*p[j]
如上三个例子都具有最优子结构性质，这个性质决定了解决此类 问题的基本思路是：首先确定原问题的最优值和其子问题的最优值之 间的递推关系，然后自底向上递归地构造出最优解。最优子结构性质 是最优化原理得以采用的先决条件。一般说来，分阶段选择策略确定 最优解的问题往往会形成一个决策序列。Bellman 认为，利用最优化 原理以及所获得的递推关系式去求解最优决策序列，可以使枚举数量 急剧下降。这里有一个问题值得注意：最优子结构性质提示我们使用 最优化原理产生的算法是递归算法，这很可能会增加时间与空间复杂 度。例如，用递归式直接计算矩阵连乘积 A[1:n] 的算法 RecurMatrixChain 的时间复杂度将是 (2 ) n Ω ： 计算矩阵连乘的递归算法 int RecurMatrixChain(int i, int, j, int p) { if (i==j) return 0; int u=RecurMatrixChain(i, i) +RecurMatrixChain(i+1,j) +p[i-1]*p[i]*p[j]; s[i][j]=i; for(int k=i+1; k<j; k++){ int t=RecurMatrixChain(i,k) +RecurMatrixChain(k+1,j) +p[i-1]*p[i]*p[j];