计算机算法设计与分析课件：第四章 动态规划

1、第四章 动态规划 4.1 一般方法 一、面向的问题类：多阶段决策过程。 多阶段决策过程：活动的过程可以分为若干个阶段，而且在任一阶段后的行为都仅依赖于该阶段的过程状态，而与该阶段之前的过程如何达到这种状态的方式无关。 二、目标：获得问题最优解的决策序列，即最优决策序列。 在多阶段决策的每一阶段，都可能有多种可供选择的决策，必须从中选取一种决策。一旦各个阶段的决策选定之后，就构成了解决这一问题的一个决策序列。决策序列不同，所导致的问题的结果也不同。动态规划的目标就是要在所有容许选择的决策序列中选取一个会获得问题最优解的决策序列，即最优决策序列。 三、方法： 穷举笨。 贪心太严格。它要求每一决策步

2、上都能得到局部最优解。（有时不能仅从局部信息获得最优判定序列） 动态规划每一步上列出各种可能的局部解，然后按某些条件放弃哪些不能得到最优解的局部解。 四、依据：最优性原理 最优性原理：过程的最优决策序列具有如下性质：无论过程的初始状态和初始决策是什么，其余的决策必须相对于初始决策所产生的状态构成一个最优决策序列。 五、实现：获取各阶段间的递推关系。 利用动态规划方法解决问题的三个重要步骤： 建立解决问题的多阶段决策模型 证明满足最优性原理 获取各阶段间的递推关系 获取递推关系式可以采用向前处理或向后处理法 向前处理法：从最后阶段开始，以逐步向前递推的方式列出求前一阶段决策的递推关系式，即根据x

3、i1，xn的那些最优决策序列来列出求取xi决策值的关系式，就是动态规划的向前处理法。列出关系式后，由最后阶段开始，回溯求解这些关系式得出最优决策序列。 向后处理法：由前向后递推求解，从而得出最优决策序列。就是根据x1，xi1的那些最优决策序列列出求xi的递推关系式。 无论是使用向前处理还是向后处理法，都将所有子问题的最优解保存下来。 4.2 多段图问题一、问题描述及多段图例 p124多段图G(V, E)是一个有向图, 它具有如下特性:图中的结点被划分成 k 2个不相交的集合Vi , 1ik,其中V1和Vk分别只有一个结点 s (源点) 和 t ( 汇点)。图中所有的边均具有如下性质: 若uVi

4、 ，则v Vi+1 ,1ik,且每条边均附有成本c(u, v)。从s到t的一条路径成本是这条路径上边的成本和。多段图问题是求由s到t的最小成本路径。 2345876111091s12t97324227111118654356524V1V2V3V4V5二、对最优性原理的满足性 p124 假设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

5、的更短路径，则这条路径肯定比v2,v3,vk-1,t路径短，这与假设矛盾，因此最优性原理成立。 1s9732V123454227111118V2876654356V31110912t524V4V5三、向前处理法: 从最后阶段开始, 逐步向前递推, 根据xi+1, xn的那些最优决策序列来列出求取xi 决策值的关系式向前处理阶段间递推关系式：设P(i, j)是一条从Vi中的节点j 到汇点t 的最小成本路径, COST(i, j)表示这条路径的成本, 根据向前处理方法有公式: COST（k,1）=0 COST（i, j）= min c（j, l ）+ COST（i+1, l） 其中: lVi+1

6、, 边E, c（j, l）表示该边的成本 对于k段图, t是vk，1 , COST（k,1）=0；当i=k-1时, 有COST(k-1, j)= c(j, t)+ COST（k,1）可求得, 依次可以通过公式对所有jVk-2, 计算COST(k-2, j), 再对所有的jVk-3, 计算COST(k-3, j), 依次向前求解, 最后计算出COST(1, 1)即S点COST值。多段图向前处理计算过程COST(4, 9)=c(9,12)=4COST(4,10)=c(10,12)=2COST(4,11)=c(11,12)=51110912t524V4V5876654356V3COST(3,6)=m

7、inc(6,9)+COST(4,9) , c(6,10)+COST(4,10) =min6+4, 5+2=7COST(3,7)=minc(7,9)+COST(4,9) , c(7,10)+COST(4,10) =min4+4, 3+2=5COST(3,8)=minc(8,10)+COST(4,10) , c(8,11)+COST(4,11) =min5+2, 6+5=7COST(i, j)=min c(j, l)+ COST(i+1, l) l Vi+1 , c（j, l）表示该边的成本1s9732V123454227111118V21110912t524V4V5876654356V3COST

8、(2,2)=minc(2,6)+COST(3,6), c(2,7)+COST(3,7), c(2,8)+COST(3,8)=min4+7, 2+5, 1+7=7COST(3,6)=7COST(3,7)=5COST(3,8)=7COST(2,3)=min2+7,7+5=9COST(2,4)=min11+7=18COST(2,5)=min11+5,8+7=15COST(1,1)=minc(1,2)+COST(2,2), c(1,3)+COST(2,3), c(1,4)+COST(2,4), c(1,5)+COST(2,5)=min9+7,7+9,3+18,2+15=16在计算每个COST(i, j

9、)的同时, 记下每个状态(结点j)所做出的决策(即l 的取值),令D(i, j)= l, 则容易求出这条最小成本的路径COST(2,2)=minc(2,6)+COST(3,6), c(2,7)+COST(3,7), c(2,8)+COST(3,8) =7COST(1,1)=minc(1,2)+COST(2,2), c(1,3)+COST(2,3), c(1,4)+COST(2,4), c(1,5)+COST(2,5)=16D(1, 1)=2D(2, 2)=7D(2, 3)=6D(2, 4)=8D(2, 5)=8D(3, 6)=10D(3, 7)=10D(3, 8)=10COST(3,6)=mi

10、nc(6,9)+COST(4,9) , c(6,10)+COST(4,10)=71271012最小成本的路径为:四、向后处理及阶段间递推关系式设BP(i, j)是一条从源点s到 Vi中的结点j的最小成本路径, BCOST(i, j)表示这条路径的成本, 根据向后处理方法有公式: BCOST（1,1）= 0 BCOST（i, j）= minBCOST（i-1, l）+ c（ l , j ） 其中: lVi-1 , 边E, c（l, j）表示该边的成本向后处理的计算过程1s97322345BCOST(j)=minBCOST(l)+ c( l , j) 4227111118876BCOST(2)=c

11、(1,2)=9BCOST(3)=c(1,3)=7BCOST(4)=c(1,4)=3BCOST(5)=c(1,5)=2BCOST(6)=minBCOST(2)+c(2,6), BCOST(3)+c(3,6) = min9+4,7+2=9BCOST(7)=11 BCOST(8)=10D(2)=1D(3)=1D(4)=1D(5)=1D(6)=3D(7)=2D(8)=2D(9)=6D(10)=6D(11)=8BCOST(9)=15 BCOST(10)=14BCOST(11)=16BCOST(12)=16 D(12)=101361012最小成本的路径为:procedure FGRAPH(E,k,n,P)

12、real COST(n), int D(n-1), P(k), r, j, k, nCOSTn=0for jn-1 to 1 by -1do 寻找结点r, 满足E且使c(j,r)+COST(r)值最小 COSTj=c(j,r)+COSTr; Dj=r ; repeatP1 1; Pk nfor j 2 to k-1 do Pj=DPj-1 repeat end FGRAPH 五、 多段图的向前处理算法为了算法描述的简单, 对结点进行编号, 从V1开始 s 编为1号, 然后V2中的结点依次编为2,3,4,5号, 按此规则编下去, 最后V5的结点t 编为12号, 有了编号可以将COST, D中表示

13、段数的第一个下标省略 通过计算找到一条最小成本的路径数组p用来保存最小成本路径上结点编程实现算法时要先将多段图用邻接表表示1s9732234542271111181110912t524876654356邻接表: 邻接表是图的一种链式存储结构, 对图中的每个顶点建立一个单链表, 链表中的结点有3个域, 分别存储顶点, 边的成本和下一个结点的指针.123456789101112118412212512927334254627182677117886951049310510611k5; n 12;COST12 0;for j 11 to 1 by -1 do COSTj inc(j,r)+COSTr

14、 Dj r repeat P1 1; Pk 12;for j 2 to 4 do Pj DPj-1 repeat1234567891011120123456789101112345112COSTDPCOST(11)=5COST(10)=2COST(9)=4512241212COST(8)=7COST(7)=5COST(6)=7D(8)=10D(7)=10D(6)=10710571010COST(5)=15COST(4)=18COST(3)=9COST(2)=7 D(11)=12 D(10)=12 D(9)=12D(5)=8D(4)=8D(3)=6D(2)=71581897867D(1)=2CO

15、ST(1)=161622710算法的执行过程procedure BGRAPH(E,k,n,P)real BCOST(n); int D(n-1), P(k), r, j, k, n;BCOST10;for j 2 to n do 寻找结点r, 满足E且使BCOST(r)+c(r, j)值最小 BCOSTj= BCOSTr+c(r, j); Dj=r ; repeatP1 1; Pk nfor j k-1 to 2 do Pj=DPj+1 ;end BGRAPH*向后处理算法多段图用反邻接表来存储多段图的向后处理算法 七、多段图的应用例：资源分配 4.3 每对顶点最短路径一、问题描述二、解决方法

16、 1、以每个结点为起始点，n次调用D-PATH算法 2、多阶段决策的直接求解三、动态规划方法的步骤 1、多阶段决策过程的建立 以路径的中间结点条件作为阶段划分的依据。 体现形式为A (K) i,j:从i到j中间经过点号不大于k的结点的最短路径。（K可以看作是阶段的标志参数），递推产生矩阵序列。(状态点及状态参数的表达) 2、满足最优性原理 3、阶段间递推关系式 四、算法实现 若同时考虑路径 在3-4语句间加 if costi,j+ then pi,j i else pi,j 0 endif 第9语句改为 if Ai,jAi,k+Ak,j then Ai,j Ai,k+Ak,j pi,j pk,

17、j endif 五、时间代价 (n3) 4.4 最优二分检索树 一、问题的提出 二分检索树定义生成（种类）性质（中序） 检索检索代价平均检索效率最优二分检索树定义 二、二分检索树代价的表示形式转化 cost(T)=cost(L)+cost(R)+w(T) 从中看出问题的两点特性：树型（根）的确定取决于子树的选取，满足最优性原理子树的构成仍与原问题同类。 三、解决思路 按结点数的递增顺序来确定最优树型结构，将构造过程看成一系列决策结果，构成多阶段决策过程。 四、多阶段决策过程描述 定义状态点T(i,j)、状态集、状态参数（r(i,j）,t(i,j),c(i,j),w(i,j) 定义阶段 (j-i

18、) 阶段间递推关系: C(i, i)=0, W(i, i)=Q(i), 0in C(i,j)=minC(i, k-1)+C(k, j)+P(k)+W(i, k-1)+W(k, j) =minC(i, k-1)+C(k, j)+W(i, j) 五、算法实现 p136-137 六、例子 4.5 0/1背包问题一、问题描述背包问题中的xj限定只能取0或1值，用KNAP(l,j,X)来表示这个问题效益值背包容量若对于有n个物品，容量为M的背包，则0/1背包问题就可表示为KNAP(1,n,M) 二、问题的分析与解决 问题形式化：KNAP（l,j,X）,原问题： KNAP（1,n,M） 解决： 多阶段决策

19、：对lj作出决策序列 向后： KNAP（1,1,x）， KNAP（1,2,x）， ， KNAP（1,n,x） 向前： KNAP（1,n,x）， KNAP（2,n,x）， ， KNAP（n,n,x） 最优性原理： 假设y1,y2,yn是最优解, 若y1=0，则y2,y3,yn 必须是KNAP(2, n, M)的一个最优序列； 若y1=1, 则y2,y3,yn 必须是KNAP(2, n, M-w1)的一个最优序列； 最优性原理对0/1背包问题成立。 阶段间递推关系 对于任意的fi(X), i0 有以下公式: f0(X) =0 fi(X) = max fi-1(X) , fi-1(X-wi)+pi

20、三、实例：p137 例6.11 n=3, (w1,w2,w3)=(2,3,4) , (p1,p2,p3)=(1,2,5) , M=6递推求解过程如下: f0(X) = - ； X0时, f0(X)= 0 X0时 f1(X) = - X0 f1(X)=maxf0(X) , f0(X-2)+1=max0, - +1=0 ，0X2 f1(X)=maxf0(X) , f0(X-2)+1 =max0, 0+1=1 X2 f2(X) =- X0 f2(X)=maxf1(X) , f1(X-3)+2=max0 , -+2=0 0X2f2(X)=maxf1(X) , f1(X-3)+2=max1 , -+2=

21、1 2X3 f2(X)=maxf1(X) , f1(X-3)+2=max1 , 0+2 =2 3X5 f2(X)=maxf1(X) , f1(X-3)+2=max1 , 1+2 =3 X 5 f3(X)=- X0 f3(X)=maxf2(X), f2(X-4)+5=max0,-+5= 0 0X2 f3(X)=maxf2(X), f2(X-4)+5=max1,-+5= 1 2X3, f3(X)=maxf2(X), f2(X-4)+5=max2,-+5= 2 3X4 f3(X)=maxf2(X), f2(X-4)+5=max2 ,0+5 = 5 4X5 f3(X)=maxf2(X), f2(X-4

22、)+5=max3 ,0+5 = 5 5X6 f3(X)=maxf2(X), f2(X-4)+5=max3 ,1+5 = 6 6X7 f3(X)=maxf2(X), f2(X-4)+5=max3 ,2+5 = 7 7X9 f3(X)=maxf2(X), f2(X-4)+5=max3 ,3+5 = 8 X9 f3(X)=maxf2(X), f2(X-4)+5=max3, 1+5 = 6f2(X)=maxf1(X), f1(X-3)+2=max1, -+2=1f1(X)=maxf0(X), f0(X-2)+1=max0, 0+1=1X3=1X2=0X1=1最优决策序列为: (x1,x2,x3)=(1

23、,0,1)通过检测fi的取值情况可以确定最优决策序列四、解的图示表达图解法实例fi-1(X-wi)+pifi(X)i=0: 函数不存在f0(X)=0i=1: f0(X-2)+1f1(X)f0(X) =- X00 X0f1(X) =- X0 max0, 0+1=1 X2max0,-+1=0 0X2 1 2 3 4 5 6 2 1 1 2 3 4 5 6 2 1 1 2 3 4 5 6 2 1 n=3, (w1,w2,w3)=(2,3,4) , (p1,p2,p3)=(1,2,5) , M=6f2(X) =- X0 max1,1+2=3 X5max1,0+2=2 3X50 0X21 2X3f1(X

24、) 1 2 3 4 5 6 2 1 1 2 3 4 5 6 3 2 1i=2: f1(X-3)+2f2(X) 1 2 3 4 5 6 3 2 1- X0 max0, -+5= 0 0X2 max1, -+5= 1 2X3 max2, -+5 = 2 3X4 max2 , 0 + 5 = 5 4X5 max3 , 0 + 5 = 5 5X6 max3 , 1 + 5 = 6 6X7 max3 , 2 + 5 = 7 7X9 max3 , 3 + 5 = 8 X9 f3(X) = 1 2 3 4 5 6 7 8 9 8 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 9 8 7 6 5

25、 4 3 2 1 1 2 3 4 5 6 3 2 1f2(X)i=3:f2(X-4)+5f3(X)五、解的序偶表示 每一个fi 完全由一些序偶(Pj,Wj)组成的集合所说明, 其中Wj 是使fi 在其处产生一次阶跃的X值，Pj=fi(Wj) 第一对序偶(P0,W0)=(0,0); 如果有r 次阶跃, 就还有r 对序偶(Pj,Wj), 1jr ; 在r对序偶中, 假定WjWj+1, 则有PjPj+1 在0jr情况下, 对所有满足WjXWj+1的X, 有fi(X)=fi(Wj); 对所有满足XWr的X, 有fi(X)=fi(Wr)f2(X) 1 2 3 4 5 6 3 2 1344且3M的那些序偶

26、(P,W)除掉, 因为它们不能导出满足约束条件的可行解这样生成的Si的所有序偶是背包问题KNAP(1,i,X)在0XM各种情况下的最优解KNAP(1,n,M)的最优解fn(M)由Sn的最后一对序偶的P值给出如果已找到 Sn 的最末序偶(Pl,Wl), 那么使pixi=Pl ,wixi=Wl 的x1,xn的决策值可通过检索 Si 来确定再判断留在Sn-1的序偶(Pl,Wl)或(Pl-pn,Wl-wn)是否属于Sn-2以确定xn-1的取值。例: S1 =(0,0),(1,2) S2 =(0,0),(1,2),(2,3),(3,5) S3 =(0,0),(1,2),(2,3),(5,4),(6,6)

27、S3的最末序偶(Pl,Wl)=(6,6)若(Pl,Wl)Sn-1，则xn=0;若(Pl,Wl) Sn-1，且(Pl-pn,Wl-wn)Sn-1，则xn=1;(6,6) S2, 并且(6-p3,6-w3)=(1,2) S2 , 所以x3=1再判断留在S2的序偶(1,2), 因(1,2) S1 , 所以x2=0(1,2) S0 , (1-p1,2-w1)=(0,0)S0，所以x1=1最优解fn(M)的最优决策序列是(x1,x2,x3)=(1,0,1)例: n=3, (p1,p2,p3)=(1,2,5) ,(w1,w2,w3)=(2,3,4), M=6 S0=(0,0) S11=(1,2)，将S0

28、和S11归并, 得：S1 =(0,0),(1,2) S21=(2,3),(3,5)，S1 和S21归并得：S2 =(0,0),(1,2),(2,3),(3,5) S31=(5,4),(6,6),(7,7),(8,9)，S2 和S31归并, 根据支配规则删去(3,5), 并将WM的那些序偶除掉 得：S3 =(0,0),(1,2),(2,3),(5,4),(6,6)七、 0/1背包问题非形式化的DKP算法procedure DKP(p,w,n,M)S0 =(0,0);for i=1 to n-1 do Si1= (Pl,Wl)|(Pl-pi,Wl-wi) Si-1 and WlM Si = MER

29、GE_PURGE(Si-1,Si1) (PX,WX) = Sn-1的最末序偶(PY,WY) = (Pl+pn,Wl+wn) ; 其中Wl 是Sn-1中使得W+wnM的所有序偶中取最大值的Wlif PXPY then xn=0 /PX是Sn的最末序偶/ else xn=1 /PY是Sn的最末序偶/沿Sn-1, S1回溯确定xn-1,x1的值end DKPS1 =(0,0),(1,2) S2 =(0,0),(1,2),(2,3),(3,5)(PX,WX)=(3,5)(P3,W3) =(5,4) , Wl =2(PY,WY)=(1+5,2+4)=(6,6)(PX=3)(PY=6)所以x3=10/1背

30、包问题DKP算法的实现可用两个一维数组P和W来存放所有的序偶(Pl ,Wl)序偶集S0,S1,Sn-1互相邻接的存放各个集合用指针Fi来指示, 0in, Fi指示S中的第一个元素所在的位置S0 =(0,0) S1 =(0,0),(1,2)S2 =(0,0),(1,2),(2,3),(3,5)1234567800101230020235 PWF0F1F3F2在生成Si1的过程中, 同时将Si-1和Si1按支配规则进行归并而生成Si , 因此不需要附加空间存放Si1在Si-1中序偶是按P和W的递增次序排列的, 因此Si的序偶也按这种次序生成procedure DKNAP(p,w,n,M,m)F0=

31、1; P1=W1=0; l=h=1; F1=next=2;for i=1 to n-1 do k=l ; u=r ; r是在lrh中,使得Wr+wiM最大 for j=l to u do (pp,ww)=(Pj+pi,Wj+wi) while ( kh and WkPnext-1 ) (Pnext,Wnext)=(pp,ww); next+; while ( kh and PkPnext-1 ) do k+; /end for while kh do (Pnext),Wnext)=(Pk,Wk); next+; k+; l=h+1; h=next-1; Fi+1=next; /end forc

32、all PARTS /算法DKP的611行end DKNAP计算S1到Sn-1/要加代码才能实现/将(pi,wi)加到Si-1中的序偶上/将Si-1中的序偶并入Si中/将Si-1中剩余的序偶并入Si中/ l和h分别指向Si的首端和末端 Fi+1指向Si+1的第一个元素Si-1和Si1按支配规则进行归并, 生成Si 八、算法的时间分析 4.6 可靠性设计 一、问题描述 二、问题的形式化表达 三、问题的动态规划求解 四、用序偶法求解4.7 货郎担问题问题描述: 某售货员要到若干个村庄售货, 各村庄之间的路程是己知的, 为了提高效率, 售货员决定从所在商店出发，到每个村庄售货一次, 然后返回商店,

33、问他应选择一条什么路线才能使所走的总路程最短?设G(V,E)是一个具有边成本cij的有向图, G的一条周游路线是包含V中每个结点的一个有向环, 周游路线的成本是此路线上所有边的成本之和。货郎担问题就是求取具有最小成本的周游路线问题。1432156820129913510108假设周游路线是开始于结点1并终止于结点1的一条简单路径。每一条周游路线都是由一条边和一条由结点k到结点1的路径所组成的, 其中kV-1;这条由结点k到结点1的路径通过V-1,k的每个结点各一次最优性原理对货郎担问题成立如果这条周游路线是最优的, 则这条由k到1的路径必定是通过V-1,k中所有结点的由k到1的最短路径, 因此

34、最优性原理成立1432156820129913510108设g(i,S)是由结点i开始, 通过S中的所有结点, 在结点1终止的一条最段路径长度2kng(1,V-1)是一条最优的周游路线长度 于是可以得到: g(1,V-1)=minc1k+g(k,V-1,k)jS上式一般化可得: g(i,S)=mincij +g(j,V-j)1234101015202509103613012488901432156820129913510108g(2,)=c21=5 g(3,)=c31=6 g(4,)=c41=8g(2,3)=c23+g(3,)=9+6=15 g(2,4)=c24+g(4,)=10+8=18g(i,S)表示由结点i经过S中所有结点到结点1的最短路线长度g(3,2)=c32+g(2,)=1