算法分析与设计动态规划ppt课件.ppt

第四章 动态规划,2,第四章 动态规划,什么是动态规划多段图最优二分检索树0/1背包问题可靠性设计货郎担问题,3,在实际生活中，有这么一类问题，它们的活动过程可以分为若干个阶段，而且在任一阶段后的行为都依赖于i 阶段的过程状态，而与i 阶段之前的过程是如何达到这种状态的方式无关，这样的过程就构成了一个多阶段决策过程。根据这类问题的多阶段决策的特性，提出了解决这类问题的“最优性原理”，从而创建了最优化问题的一种新的算法设计方法动态规划。,4.1 一般方法,4,在多阶段决策过程的每一个阶段，都可能有多种选择的决策，但必须从中选取一种决策。一旦各种阶段的决策选定之后，就构成了解决这一问题的一个决策序列。决策序列不同，导致的问题结果也不同。动态规划的目标就是要在所有容许选择的决策序列中选取一个会获得问题最优解的决策序列，即最优决策序列。,什么是动态规划,5,最优性原理,最优性原理(Principle of Optimality)过程的最优决策序列具有如下性质：无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。利用动态规划求解问题的前提 1)证明问题满足最优性原理 如果对所求解问题证明满足最优性原理，则说明用动态规划方法有可能解决该问题 2)获得问题状态的递推关系式 获得各阶段间的递推关系式是解决问题的关键。,6,多段图问题,多段图问题,7,多段图问题,多段图G(V,E)是个有向图。它具有如下特性：图中的结点被划分成k 2个不相交的集合Vi,1ik,其中V1和Vk分别只有一个结点s(源点)和 t(汇点)。图中所有的边均具有如下性质：若uVi，则v Vi+1,1ik,且每条边均附有成本c(u,v)。从s到t的一条路径成本是这条路径上边的成本和。多段图问题(multistage graph problem)是求由s到t的最小成本路径。,8,多段图问题,最优性原理对多段图成立假设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路径短，这与假设矛盾，因此最优性原理成立,9,0/1背包问题,背包问题中的xj限定只能取0或1值，用KNAP(1,j,X)来表示这个问题,效益值,背包容量,则0/1背包问题就是KNAP(1,n,M),10,最优化决策序列的表示,设S0是问题的初始状态。假定要作n次决策xi,1inX1=r1,1,r1,2,r1,pj是x1的可能决策值的集合，而S1,1是在选取决策值r1,j1以后所产生的状态，1j1p1又设F1,j1是相应于状态S1,j1的最优决策序列则相应于S0的最优决策序列就是r1,j1 F1,j1|1j1p1中最优的序列，记作,如果已作了k-1次决策，1k-1n。设x1,xk-1的最优决策值是r1,.,rk-1，他们所产生的状态为S1,Sk-1,11,最优化决策序列的表示,又设Xk=rk,1,rk,2,rk,pk是xk的可能值的集合。Sk,jk是选取rk,jk决策之后所产生的状态,1jkpkFk,jk 是相应于Sk,jk的最优决策序列。因此，相应于Sk-1的最优决策序列是,于是相应于S0的最优决策序列为：r1,rk-1,rk,Fk,12,向前处理法(forward approach),从最后阶段开始，以逐步向前递推的方式列出求前一阶段决策值的递推关系式，即根据xi+1,xn的那些最优决策序列来列出求取xi决策值的关系式，这就是动态规划的向前处理法向后处理方法(backward approach)就是根据x1,xi-1的那些最优决策序列列出求xi的递推关系式。多段图的向前处理和向后处理0/1背包问题的向前处理和向后处理,13,4.2 多段图,多段图向前处理的算法设P(i,j)是一条从Vi中的节点j 到汇点t 的最小成本路径，COST(i,j)表示这条路径的成本，根据向前处理方法有公式4.5：,14,因为，若 E成立,有COST(k-1,j)=c(j,t),若 E不成立，则有COST(k-1,j)=，所以可以通过如下步骤解式公式（4.5），并求出COST(1,s)。首先对于所有jVk-2，计算COST(k-2,j)，然后对所有的jVk-3，计算计算COST(k-3,j)等等，最后计算出计算COST(1,s),多段图的向前处理算法,15,例子中5段图的实现计算步骤：COST(4,9)=4COST(4,10)=2COST(4,11)=5COST(3,6)=min6+COST(4,9),5+COST(4,10)=7COST(3,7)=min4+COST(4,9),3+COST(4,10)=5COST(3,8)=min5+COST(4,10),6+COST(4,11)=7,多段图的向前处理算法,16,COST(2,2)=min4+COST(3,6),2+COST(3,7),1+COST(3,8)=7COST(2,3)=9COST(2,4)=18COST(2,5)=15COST(1,1)=min9+COST(2,2),7+COST(2,3),3+COST(2,4),2+COST(2,5)=16,多段图的向前处理算法,17,例子中5段图的实现计算步骤：在计算每一个COST(i,j)的同时，记下每个状态(结点j)所做出的决策，设为D(i,j)，则可容易地求出这条最小成本路径。D(3,6)=10D(3,7)=10D(3,8)=10D(2,2)=7D(2,3)=6D(2,4)=8D(2,5)=8D(1,1)=2 设这条最小成本路径是sl,v2,v3,vk-1,t=12。则可得知：v2D(1,1)2，v3=D(2,D(1,1)=7 和v4D(3,D(2,D(1,1)D(3,7)10,多段图的向前处理算法,18,多段图的向前处理算法,procedure FGRAP(E,k,n,P)real COST(n),integer D(n-1),P(k),r,j,k,nCOST(n)0for jn-1 to 1 by 1 do 设r是一个这样的结点,E且使c(j,r)+COST(r)取小值COST(j)c(j,r)+COST(r)D(j)rrepeatP(1)1;P(k)nfor j2 to k-1 doP(j)D(P(j-1)repeatEnd FGRAPH,计算出COST(j)的值，并找出一条最小成本路径,找出最小成本路径上的第j个结点,19,多段图的向后处理算法,向后处理方法(backward approach)就是根据x1,xi-1的那些最优决策序列列出求xi的递推关系式。,20,多段图的向后处理算法,设BP(i,j)是一条由源点s到Vi中结点j的最小成本路径，BCOST(i,j)表示BP(i,j)的成本，由向后处理方法得到公式4.6：,即由源点s到Vi中结点j的最小成本，等于由源点s到Vi-1中任一结点l 的最小成本加上Vi-1中结点l 到Vi中结点j的边长,所得的所有和中最小的那个值。,21,因为，若 E成立,BCOST(2,j)=c(1,j),若 E不成立，则有BCOST(2,j)=，所以可以通过如下步骤解式公式（4.6），首先对i3计算BCOST，然后对 i4 计算BCOST等，最后计算出BCOST(k，t)。BCOST(2，2)=9；BCOST(2，3)=7；BCOST(2，4)=3；BCOST(2，5)=2；,多段图的向后处理算法,22,1,2,3,4,5,8,7,6,11,10,9,12,s,t,9,7,3,2,4,2,2,7,1,11,11,8,6,5,4,3,5,6,5,2,4,BCOST(3,6)=minBCOST(2,2)+4,BCOST(2,3)+2=9BCOST(3,7)=minBCOST(2,2)+2,BCOST(2,3)+7,BCOST(2,5)+11=11BCOST(3,8)=minBCOST(2,2)+1,BCOST(2,4)+11,BCOST(2,5)+8=10,1,6,3,2,7,2,8,23,1,2,3,4,5,8,7,6,11,10,9,12,s,t,9,7,3,2,4,2,2,7,1,11,11,8,6,5,4,3,5,6,5,2,4,1,6,3,2,7,2,8,BCOST(4,9)=minBCOST(3,6)+6,BCOST(3,7)+4=15BCOST(4,10)=minBCOST(3,6)+5,BCOST(3,7)+3,BCOST(3,8)+5=14BCOST(4,11)=16,9,10,11,24,1,2,3,4,5,8,7,6,11,10,9,12,s,t,9,7,3,2,4,2,2,7,1,11,11,8,6,5,4,3,5,6,5,2,4,1,6,3,2,7,2,8,9,10,11,BCOST(5,12)=minBCOST(4,9)+4,BCOST(4,10)+2,BCOST(4,11)+5=16,12,25,多段图的向后处理算法,在计算每一个BCOST(i,j)的同时，记下每个状态(结点j)所做出的决策(即,使BCOST(i-1,j)+c(l,j)取最小值的 l 值),设为D(i,j)，则可容易地求出这条最小成本路径。,26,对于实例中的最小成本路径如下所示：D(3,6)=3;D(3,7)=2;D(3,8)=2;D(4,9)=6;D(4,10)=6;D(4,11)=8;D(5,12)=10,27,多段图的向后处理算法,Line procedure BGRAP(E,k,n,P)real BCOST(n),integer D(n-1),P(k),r,j,k,nBCOST(1)0for j2 to n do 设r是一个这样的结点，E且使BCOST(r)+c(r,j)取小值BCOST(j)BCOST(r)+c(r,j)D(j)rrepeatP(1)1;P(k)nfor jk-1 to 2 by-1 doP(j)D(P(j+1)repeatEnd BGRAPH,计算出BCOST(j)的值，并找出一条最小成本路径,找出最小成本路径上的第j个结点,28,4.3 每对结点之间的最短路径,复习（略）,29,4.4 最优二分检索树,问题的描述1）二分检索树定义 二分检索树是一棵二元树，它或者为空，或者其每个结点含有一个可以比较大小的数据元素，且有：的左子树的所有元素比根结点中的元素小；的右子树的所有元素比根结点中的元素大；的左子树和右子树也是二分检索树。注：二分检索树要求树中所有结点的元素值互异,30,二分检索树,对于一个给定的标识符集合，可能有若干棵不同的二分检索树:,不同形态的二分检索树对标识符的检索性能是不同的。,31,二分检索树,检索一棵二分检索树算法procedure SEARCH(T,X,i)i=Twhile i0 do case:XIDENT(i):i=RCHILD(i)endcaserepeatend REARCH,32,最优二分检索树问题,设给定的标识符集合是a1,a2,an，并假定a1a2 an。设，P(i)是对ai检索的概率，Q(i)是正被检索的标识符X恰好满足：ai Xai+1，0in（设a0=-,an+1=+)时的概率，即一种不成功检索情况下的概率。则 表示所有成功检索的概率 表示所有不成功检索的概率 考虑所有可能的成功和不成功检索情况，共2n+1种可能的情况，有,33,二分检索树,二分检索树（如右图所示）内结点：代表成功检索情况，刚好有n个。外结点：代表不成功检索情况，刚好有n1个。,34,二分检索树的预期成本,预期成本：算法对于所有可能的成功检索情况和不成功检索情况，平均所要做的比较次数。根据期望值计算方法，平均检索成本每种情况出现的概率该情况下所需的比较次数 平均检索成本的构成：成功检索成分不成功检索成分 成功检索：在l级内结点终止的成功检索，需要做l次比较运算（基于二分检索树结构）。该级上的任意结点ai的成本检索的成本分担额为：P(i)*level(ai)；其中，level(ai)=结点ai 的级数=l,35,二分检索树的预期成本,不成功检索：不成功检索的等价类：每种不成功检索情况定义了一个等价类，共有n+1个等价类Ei(0in)。其中，E0=X|Xa0 Ei=X|aiXai+1(1in)En=X|Xan 若Ei处于l级，则算法需作l-1次迭代。则，l级上的外部结点的不成功检索的成本分担额为：Q(i)*(level(Ei)-1)则预期总的成本公式表示如下：,36,最优二分检索树,最优二分检索树问题：求一棵使得预期成本最小的二分检索树例4.9 标识符集合（a1,a2,a3）=（do,if,stop）。可能的二分检索树如下所示。成 功 检 索：3种 不成功情况：4种,37,最优二分检索树,38,最优二分检索树,1)等概率：P(i)=Q(i)=1/7 cost(a)=15/7 cost(b)=13/7 最优 cost(c)=15/7 cost(d)=15/7 cost(e)=15/7 2）不等概率：P(1)=0.5 P(2)=0.1 P(3)=0.05 Q(0)=0.15 Q(1)=0.1 Q(2)=0.05 Q(3)=0.05 cost(a)=2.65 cost(b)=1.9 cost(c)=1.5 最优 cost(d)=2.15 cost(e)=1.6,39,多阶段决策过程,把构造二分检索树的过程看成一系列决策的结果。决策的策略：决策树根，如果a1,a2,an存在一棵二分检索树，ak是该树的根，则内结点a1,a2,ak-1和外部结点E0,E1,Ek-1将位于根ak的左子树中，而其余的结点将位于右子树中。,40,定义,含义：左、右子树的预期成本左、右子树的根处于第一级 左、右子树中所有结点的级数相对于子树的根测定，而相对于原树的根少1,41,定义,记：则，原二分检索树的预期成本可表示为：COST(T)=P(k)+COST(L)+COST(R)+W(0,k-1)+W(k,n)最优二分检索树：COST(T)有最小值最优性原理成立 若T最优二分检索树，则COST(L)和COST(R)将分别是包含a1,a2,ak-1和E0,E1,Ek-1、及ak1,ak+2,an和Ek,Ek+1,En的最优二分检索(子)树。记由ai+1,ai+2,aj和Ei,Ei+!,Ej构成的二分检索树的成本为C(i,j)，则对于最优二分检索树T有，COST(L)=C(0,k-1)COST(R)=C(k,n),42,定义,则，对任何C(i,j)有，向前递推过程：首先计算所有j-i=1的C(i,j)然后依次计算j-i=2,3,n的C(i,j)。C(0,n)=最优二分检索树的成本。初始值 C(i,i)=0 W(i,i)=Q(i)，0in,43,用动态归划求最优二分检索树,首先计算所有使得j-i=1的C(i,j)接着计算所有使得j-i=2的C(i,j).如果在这一计算期间，记下每棵Tij树的根R(i,j),那么最优二分检索树就可以由这些R(i,j)构造出来。,44,用动态归划求最优二分检索树,例4.10 设n=4,且(a1,a2,a3,a4)=(do,if,read,while)。设P(1:4)=(3,3,1,1)，Q(0:4)=(2,3,1,1,1)(概率值“扩大”了16倍)初始：W(i,i)=Q(i)C(i,i)=0 R(i,i)=0且有，W(i,j)=P(j)+Q(j)+W(i,j-1)j-i=1阶段的计算：W(0,1)=P(1)+Q(1)+W(0,0)=8 C(0,1)=W(0,1)+minC(0,0)+C(1,1)=8 R(0,1)=1 W(1,2)=P(2)+Q(2)+W(1,1)=7 C(1,2)=W(1,2)+minC(1,1)+C(2,2)=7 R(1,2)=2 W(2,3)=P(3)+Q(3)+W(2,2)=3 C(2,3)=W(2,3)+minC(2,2)+C(3,3)=3 R(2,3)=3 W(3,4)=P(4)+Q(4)+W(3,3)=3 C(3,4)=W(3,4)+minC(3,3)+C(4,4)=3 R(3,4)=4,例4.10(P135),45,用动态归划求最优二分检索树,W,C,R计算结果则，C(0,4)=32二分检索树：T04=2=T01(左子树），T24(右子树）T01=1=T00(左子树），T11(右子树）T24=3=T22(左子树），T34(右子树）,j,i,46,用动态归划求最优二分检索树,树的形态,47,算法描述,procedure OBST(P,Q,n)/给定n个标识符a1a2an。已知成功检索的概率P(i),不成功检索概率Q(i),0in。算法对于标识符ai+1,aj计算最优二分检索树Tij的成本C(i,j)、根 R(i,j)、权W(i,j)/real P(1:n),Q(0:n),C(0:n,0:n),W(0:n,0:n);integer R(0:n,0:n)for i0 to n-1 do(W(i,i),R(i,i),C(i,i)(Q(i),0,0)/置初值/(W(i,i+1),R(i,i+1),C(i,i+1)(Q(i)+Q(i+1)+P(i+1),i+1,Q(i)+Q(i+1)+P(i+1)repeat/含有一个结点的最优树/(W(n,n),R(n,n),C(n,n)(Q(n),0,0)for m2 to n do/找有m个结点的最优树/for i0 to n-m do ji+m W(i,j)W(i,j-1)+P(j)+Q(j)k区间R(i,j-1),R(i+1,j)中使C(i,l-1)+C(l,j)取最小值的l值/Knuth结论/C(i,j)W(i,j)+C(i,k-1)+C(k,j)R(i,j)k repeat repeat end OBST,48,计算时间,当j-i=m时，有n-m+1个C(i,j)要计算 C(i,j)的计算：(m)每个C(i,j)要求找出m个量中的最小值。则，n-m+1个C(i,j)的计算时间：(nm-m2)对所有可能的m，总计算时间为：,49,4.5 0/1背包问题,问题描述,背包问题中的xj限定只能取0或1值，用KNAP(1,j,X)来表示这个问题,效益值,背包容量,则0/1背包问题就是KNAP(1,n,M),50,0/1背包问题最优化原理证明,若y1,y2,yn是最优解，则y2,y3,yn将是是0/1 背包问题的子问题,的最优解。因为，若y2,y3,yn 是子问题的最优解，且使得,51,0/1背包问题最优化原理证明,则y1,y2,y3,yn 将是原问题的可行解，并且使得,这与假设y1,y2,yn是最优解相矛盾。因此，0/1 背包问题具有最优子结构性质得以证明，可以用动态规划的方法求最优解。,52,0/1背包问题-解决方法,根据问题描述，可通过作出变量x1,x2,xn的一个决策序列来得到它的解。假定决策x的次序为x1,x2,xn则在对x1作出决策后，问题处于下列两种状态：X1=0,背包的剩余容量为M，没有产生任何效益X1=1,背包剩余容量为M-w1，效益值增加了p1显然，剩下来对x2,xn的决策相对于决策了x1后所产生的问题状态应该是最优的，否则，x1,x2,xn就不可能是最优的决策序列。,53,0/1背包问题解决方法,设fj(X)是KNAP(1,j,X)最优解的值则fn(M)(KNAP(1,n,M)可表示为：fn(M)=max fn-1(M),fn-1(M-wn)+pn 则对于任意的fi(X)(KNAP(1,i,X)可表示公式4.14为：fi(X)=max fi-1(X),fi-1(X-wi)+pi 为了能由前向后递推而最后求解出fn(M),须从f0(X)开始对于所有的X0，有f0(X)=0；当X0时，有f0(X)=-根据递推关系式，马上可求出0Xw1和Xw1情况下的f1(X)的值,54,0/1背包问题实例,例：n=3,(w1,w2,w3)=(2,3,4),(p1,p2,p3)=(1,2,5),M=6。利用公式4.14递推求解如下：当X0时,f0(X)=-;当X 0时,有f0(X)=0当X0时,f1(X)=-当0X2时,f1(X)=maxf0(X),f0(X-2)+1=max0,-+1=0当X2时,f1(X)=maxf0(X),f0(X-2)+1=max0,0+1=1,55,0/1背包问题实例,当X0 时,f2(X)=-当0X2时,f2(X)=maxf1(X),f1(X-3)+2=max 0,-+2=0当2X3 时,f2(X)=maxf1(X),f1(X-3)+2=max 1,-+2=1当3X5 时,f2(X)=maxf1(X),f1(X-3)+2=max 1,0+2=2当 5X 时,f2(X)=maxf1(X),f1(X-3)+2=max 1,1+2=3,例：n=3,(w1,w2,w3)=(2,3,4),(p1,p2,p3)=(1,2,5),M=6。,56,0/1背包问题实例,当X0 时,f3(X)=-当0X2 时,f3(X)=maxf2(X),f2(X-4)+5=max0,-+5=0当2X3 时,f3(X)=maxf2(X),f2(X-4)+5=max1,-+5=1当3X4 时,f3(X)=maxf2(X),f2(X-4)+5=max2,-+5=2当4X5 时,f3(X)=maxf2(X),f2(X-4)+5=max2,0+5=5当5X6 时,f3(X)=maxf2(X),f2(X-4)+5=max3,0+5=5当6X7 时,f3(X)=maxf2(X),f2(X-4)+5=max3,1+5=6当7X9 时,f3(X)=maxf2(X),f2(X-4)+5=max3,2+5=7当9X 时,f3(X)=maxf2(X),f2(X-4)+5=max3,3+5=8,例：n=3,(w1,w2,w3)=(2,3,4),(p1,p2,p3)=(1,2,5),M=6。,57,0/1背包问题实例,58,0/1背包问题算法,procedure DynamicKnapsack(p,w,n,M,f)/二维数组f(1:n,1:M)的定义与fj(X)相同for i 0 to M do f(0,i)0;repeatfor i 0 to n do f(i,0)0;repeatfor i 1 to n do for j 1 to M do if w(i)j then f(i,j)=maxf(i-1,j-w(i)+p(i),f(i-1,j);else f(i,j)=f(i-1,j)end if repeat repeat 输出f(n,M);end DynamicKnapsack,59,0/1背包问题实例,可通过检测fi的取值情况可以确定获得最优解的最优决策序列f3(M)=6是在X3=1的情况下取得的，因此X3=1f3(M)-p3=1，f2(X)和f1(X)都可取1，则x2=0f0不能取值1，故x1=1于是最优决策序列为(x1,x2,x3)=(1,0,1)也可通过图解法得到fi-1(X-wi)+pi的图像可由fi-1(X)在x轴上右移wi个单位，然后上移pi个单位得到fi(X)的图像由fi-1(X)和fi-1(X-wi)+pi 的函数曲线按X相同时取最大值的规则归并而成,60,0/1背包问题实例图解法,fi-1(X-wi)+pi,fi(X),i=0:函数不存在,f0(X),i=1:f0(X-2)+1,f1(X),当X0时,f0(X)=-;当X 0时,有f0(X)=0当X0时,f1(X)=-当0X2时,f1(X)=maxf0(X),f0(X-2)+1=max0,-+1=0当X2时,f1(X)=maxf0(X),f0(X-2)+1=max0,0+1=1,61,i=2:f1(X-3)+2,f2(X),f1(X),当X0 时,f2(X)=-当0X2时,f2(X)=maxf1(X),f1(X-3)+2=max 0,-+2=0当2X3 时,f2(X)=maxf1(X),f1(X-3)+2=max 1,-+2=1当3X5 时,f2(X)=maxf1(X),f1(X-3)+2=max 1,0+2=2当 5X 时,f2(X)=maxf1(X),f1(X-3)+2=max 1,1+2=3,62,i=3:f2(x-4)+5,f3(X),当X0 时,f3(X)=-当0X2 时,f3(X)=maxf2(X),f2(X-4)+5=max0,-+5=0当2X3 时,f3(X)=maxf2(X),f2(X-4)+5=max1,-+5=1当3X4 时,f3(X)=maxf2(X),f2(X-4)+5=max2,-+5=2当4X5 时,f3(X)=maxf2(X),f2(X-4)+5=max2,0+5=5当5X6 时,f3(X)=maxf2(X),f2(X-4)+5=max3,0+5=5当6X7 时,f3(X)=maxf2(X),f2(X-4)+5=max3,1+5=6当7X9 时,f3(X)=maxf2(X),f2(X-4)+5=max3,2+5=7当9X 时,f3(X)=maxf2(X),f2(X-4)+5=max3,3+5=8,63,0/1背包问题实例图解法,由图可看出以下几点：每一个fi 完全由一些序偶(Pj,Wj)组成的集合所说明，其中Wj是使fi 在其处产生一次阶跃的X值，Pj=fi(Wi)。第一对序偶(P0,W0)=(0,0)如果有r次阶跃，就还要知道r对序偶(Pj,Wj),1jrr对序偶中，假定WjWj+1，由公式4.14可得PjPj+1设Si-1表示fi-1的所有序偶的集合Si1表示fi-1(X-wi)+pi 的所有序偶的集合。把(pi,wi)加到Si-1中,每一对序偶就得到Si1,64,0/1背包问题实例,支配规则由于取fi-1(X)和fi-1(X-wi)+pi的最大值，也就是将 Si-1 和 Si1 归并成 Si如果 Si-1 和 Si1中一个有序偶(Pj,Wj)，另一个有序偶(Pk,Wk)，并且在WjWk的同时有PjPk，那么，序偶(Pj,Wj)被放弃。也就是递推关系式中求最大值的运算fi(Wj)=max(Pj,Pk)=Pk,65,0/1背包问题实例,例：n=3,(p1,p2,p3)=(1,2,5),(w1,w2,w3)=(2,3,4),M=6S0=(0,0)S11=(P,W)|(P-p1,W-w1)S0=(1,2)S1=(0,0),(1,2)S21=(P,W)|(P-p2,W-w2)S1=(2,3),(3,5)S2=(0,0),(1,2),(2,3),(3,5)S31=(P,W)|(P-p3,W-w3)S2=(5,4),(6,6),(7,7),(8,9)S3=(0,0),(1,2),(2,3),(5,4),(6,6),(7,7),(8,9)根据支配规则，在S3中删去了序偶(3,5),66,Si的推导过程,在用直接枚举法求解0/1背包问题时，由于每个xi的取值只能为0或1，因此x1,x2,xn有2n个不同的0、1值序列。对于每一个序列，若把 wlxl 记为Wj，plxl 记为Pj，则此序列产生一对与之对应的序偶(Pj,Wj)在这2n个序偶中，满足WjM，且使Pj取最大值的序偶就是背包问题的最优解。在用动态规划的向后处理法求解时，Si-1表示的就是由x1,x2,xi-1的2i-1个决策序列中一些可能的序列所产生的序偶(Pj,Wj)。,67,Si的推导过程,若已知Si-1，则求 Si 可有下述步骤得到：在xi=0的情况下，产生的序偶集与Si-1相同在xi=1的情况下，产生的序偶集是将(pi,wi)加到Si-1的每一对序偶(Pj,Wj)得到的，也就是Si1再根据支配规则将Si-1和Si1归并在一起就得到Si此外，在生成序偶集Si同时，还应将WM的那些序偶(Pj,Wj)除掉。,68,最优解序列的确定,这样生成的Si的所有序偶是背包问题KNAP(1,i,X)在0XM各种情况下的最优解。KNAP(1,n,M)的最优解fn(M)由Sn的最后一对序偶的P值给出。如果已找到 Sn 的最末序偶(Pl,Wl),那么，使pixi=Pl,wixi=Wl 的x1,xn的决策值可以通过检索这些 Si 来确定。若(Pl,Wl)Sn-1，xn=0；若(Pl,Wl)Sn-1，且(Pl-pn,Wl-wn)Sn-1，xn=1；再判断留在Sn-1的序偶(Pl,Wl)或(Pl-pn,Wl-wn)是否属于Sn-2以确定xn-1的取值。,69,最优解序列的确定,例：n=3,(p1,p2,p3)=(1,2,5),(w1,w2,w3)=(2,3,4),M=6f3(6)的值由S3中的序偶(6,6)给出(6,6)S2,并且(6-p3,6-w3)=(1,2)S2,因此x3=1。(1,2)S2,又因为(1,2)S1,于是x2=0。(1,2)S0,(1-p1,2-w1)=(0,0)S0，所以x1=1。f3(6)=6的最优决策序列是(x1,x2,x3)=(1,0,1),70,0/1背包问题DKP算法,procedure DKP(p,w,n,M)S0(0,0)for i1 to n-1 doSi1(Pl,Wl)|(Pl-pi,Wl-wi)Si-1 and WlMSiMERGE_PURGE(Si-1,Si1)repeat(PX,WX)Sn-1的最末序偶(PY,WY)(Pl+pn,Wl+wn)其中，Wl 是Sn-1中使得W+wnM的所有序偶中取最大值的Wif PXPY then xn0/PX是Sn的最末序偶/xn1/PY是Sn的最末序偶/endif回溯确定xn-1,x1End DKP,初始值,利用支配规则生成Si的序偶集合,确定最优解序列,确定xi取0还是1,71,4.6 可靠性设计,假定要设计一个系统,这个系统由若干个以串联方式连接在一起的不同设备所组成。设ri是设备Di的可靠性（正常运转的概率），则整个系统的可靠性就是若第i级的设备Di的台数为mi,则这mi台设备同时出现故障的概率为(1-ri)mi，从而第i级的可靠性就变成1-(1-ri)mi。,72,可靠性设计(1),假设第i级的可靠性由函数i(mi)给定，这个多级系统的可靠性是假设Cj 是一台设备j的成本，由于系统中每种设备至少有一台，故设备j允许配置的台数至多为,73,可靠性设计(2),如果RELI(1,i,X)表示在可容许成本X约束下，对第1种到第i种设备的可靠性设计问题，它的形式描述为极大化约束条件,74,可靠性设计(3),于是整个系统的可靠性设计问题可用RELI(1,n,c)表示。它的一个最优解是对m1,mn的一系列决策的结果。每得到一个mi都要对其取值进行一次决策。设fi(X)是在容许成本值X约束下对前i种设备组成的子系统可靠性设计的最优值。,75,可靠性设计(4),于是最优解的可靠性是fn(c).一般性况：,76,4.7 货郎担问题,问题描述：某售货员要到若干个村庄售货，各村庄之间的路程是己知的，为了提高效率，售货员决定从所在商店出发，到每个村庄售一次货然后返回商店，问他应选择一条什么路线才能使所走的总路程最短?设G(V,E)是一个具有边成本cij的有向图。G的一条周游路线是包含V中每个结点的一个有向环。周游路线的成本是此路线上所有边的成本之和，货郎担问题(traveling salesperson problem)是求取具有最小成本的周游路线问题。,77,货郎担问题实例,邮路问题在一条装配线上用一个机械手取紧固待装配部件上的螺帽问题产品的生产安排问题,78,是否能用动态规划解决,假设周游路线是开始于结点1并终止于结点1的一条简单路径。每一条周游路线都由一条边和一条由结点k到结点1的路径所组成，其中kV-1;而这条由结点k到结点1的路径通过V-1,k的每个结点各一次。容易看出，如果这条周游路线是最优的，那么这条由k到1的路径必定是通过V-1,k中所有结点的由k到1的最短路径，因此最优性原理成立。,79,动态规划的解决方法,假设g(i,S)是由结点i开始，通过S中的所有结点，在结点1终止的一条最段路径长度。g(1,V-1)是一条最优的周游路线长度。于是可以得到：,k,80,货郎担问题实例,10,5,9,15,6,10,8,13,20,8,12,9,81,货郎担问题实例,g(2,)=c21=5,g(3,)=c31=6,g(4,)=c41=8g(2,3)=c23+g(3,)=9+6=15（结点2经过结点3到结点1的路线长度）g(2,4)=c24+g(4,)=10+8=18g(3,2)=c32+g(2,)=13+5=18 g(3,4)=c34+g(4,)=12+8=20 g(4,2)=c42+g(2,)=8+5=13g(4,3)=c43+g(3,)=9+6=15,82,货郎担问题实例,g(2,3,4)=minc23+g(3,4),c24+g(4,3)=min9+20,10+15=25（结点2经过结点3、4到结点1的路线长度）g(3,2,4)=minc32+g(2,4),c34+g(4,2)=min13+18,12+13=25g(4,2,3)=minc42+g(2,3),c43+g(3,2)=min8+15,9+18=23,83,货郎担问题实例,最后，可得 g(1,2,3,4)=minc12+g(2,3,4),c13+g(3,2,4),c14+g(4,2,3)=min10+25,15+25,20+23=35（结点1经过结点2、3、4最后到达结点1的路线长度）因此可得这条最优周游路线是:1-2-4-3-1,84,4.8 流水线调度问题,设有n个作业，每个作业要执行m个任务：T1i,T2i,Tmi,(1 i n)任务Tji只能在设备Pj上执行。对任一作业i,在任务Tj-1，i没完成以前，不能对任务Tji开始处理。同一台设备在任何时刻不能同时处理一个以上的任务。假设完成任务Tji所要求的时间是tji。如何将这n*m个任务分配给这m台设备，才能使这n个作业在以上要求下顺利完成？,85,两种可能的调度,非抢先调度抢先调度例6.18(P148),86,最优完成时间OFT调度,一组给定作业的最优完成时间OFT调度是一种非抢先调度S，它对所有非抢先调度而言，调度S完成时间F(S)的值最小。本节只讨论当m=2时获取OFT调度这种特殊情况的算法。为方便起见，用ai表示t1i，bi表示t2i,87,最优调度排列具有的性质,在给出了这个排列的第一个作业后，剩下的排列相对于这两台设备在完成第一个作业时所处的状态而言是最何优。,88,递推关系式,假设对作业1,2,k的一种调度排列为a1,a2,ak。对于这种调度，设h1和h2分别是在设备P1和P2上完成任务(T11,T12,T1k)和(T21,T22,T2k)的时间。设t=h2-h1，则在t这段时间及其以前，设备P2不能用来处理别的作业的任务。,89,递推关系式,假设g(S,t)是上述t下S的最优调度长度。g(1,2,n,0)=minai+g(1,2,.,n-i,bi)1i n一般情况：g(S,t)=minai+g(S-i,bi+maxt-ai,0)(1i n),90,递推关系式,g(S,t)=ai+g(S-i,bi+maxt-ai,0)=ai+aj+g(S-i,j,bj+maxbi+maxt-ai,0-aj,0)令tij=bj+maxbi+maxt-ai,0-aj,0=bj+bi-aj-ai+maxt,ai+aj-bi,ai如果作业i和j互易其位，则完成时间为：g(S,t)=ai+aj+g(S-i,j,tji)若maxt,ai+aj-bi,ai maxt,ai+aj-bi,ai或minbi,ajminbj,ai则g(S,t)g(S,t),91,调度规则,把全部ai和bi分类成非降序列按照这一分类次序考察些序列：1.如果序列中下一个数是aj且作j还没调度，那么在还没使用的最左位置调度作业j;2.如果下个数是bj且作业j还没有调度，那么在还没有使用的最右位置调度作业j；3.如果已经调度了作业j，则转