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

1、第四章第四章 动态规划动态规划第四章第四章 动态规划动态规划 什么是动态规划什么是动态规划 多段图多段图 最优二分检索树最优二分检索树 0/1背包问题背包问题 可靠性设计可靠性设计 货郎担问题货郎担问题 在实践生活中，有这么一类问题，它们的活在实践生活中，有这么一类问题，它们的活动过程可以分为假设干个阶段，而且在任一动过程可以分为假设干个阶段，而且在任一阶段后的行为都依赖于阶段后的行为都依赖于i 阶段的过程形状，阶段的过程形状，而与而与i 阶段之前的过程是如何到达这种形状阶段之前的过程是如何到达这种形状的方式无关，这样的过程就构成了一个多阶的方式无关，这样的过程就构成了一个多阶段决策过程。段决

2、策过程。 根据这类问题的多阶段决策的特性，提出理根据这类问题的多阶段决策的特性，提出理处理这类问题的处理这类问题的“最优性原理，从而创建最优性原理，从而创建了最优化问题的一种新的算法设计方法了最优化问题的一种新的算法设计方法动态规划。动态规划。4.1 普通方法普通方法 在多阶段决策过程的每一个阶段，都能在多阶段决策过程的每一个阶段，都能够有多种选择的决策，但必需从中选取够有多种选择的决策，但必需从中选取一种决策。一旦各种阶段的决策选定之一种决策。一旦各种阶段的决策选定之后，就构成理处理这一问题的一个决策后，就构成理处理这一问题的一个决策序列。决策序列不同，导致的问题结果序列。决策序列不同，导致

3、的问题结果也不同。也不同。 动态规划的目的就是要在一切允许选择动态规划的目的就是要在一切允许选择的决策序列中选取一个会获得问题最优的决策序列中选取一个会获得问题最优解的决策序列，即最优决策序列。解的决策序列，即最优决策序列。什么是动态规划最优性原理最优性原理 最优性原理最优性原理(Principle of Optimality) 过程的最优决策序列具有如下性质：无论过程过程的最优决策序列具有如下性质：无论过程的初始形状和初始决策是什么，其他的决策都必需相的初始形状和初始决策是什么，其他的决策都必需相对于初始决策所产生的形状构成一个最优决策序列。对于初始决策所产生的形状构成一个最优决策序列。 利

4、用动态规划求解问题的前提利用动态规划求解问题的前提 1) 证明问题满足最优性原理证明问题满足最优性原理 假设对所求解问题证明满足最优性原理，那么假设对所求解问题证明满足最优性原理，那么阐明用动态规划方法有能够处理该问题阐明用动态规划方法有能够处理该问题 2) 获得问题形状的递推关系式获得问题形状的递推关系式 获得各阶段间的递推关系式是处理问题的关键。获得各阶段间的递推关系式是处理问题的关键。多段图问题多段图问题多段图问题多段图问题123458761110912st97324227111118654356524V1V2V3V4V5多段图问题多段图问题 多段图多段图G(V, E)是是个有向图。它具

5、有如下特性：个有向图。它具有如下特性： 图中的结点被划分成图中的结点被划分成k 2个不相交的集合个不相交的集合Vi ,1ik,其中其中V1和和Vk分别只需一个结点分别只需一个结点s (源点源点) 和和 t ( 汇点汇点)。 图中一切的边图中一切的边均具有如下性质：假设均具有如下性质：假设uVi ，那么那么v Vi+1 ,1ik,且每条边且每条边均附有本钱均附有本钱c(u, v)。 从从s到到t的一条途径本钱是这条途径上边的本钱和。的一条途径本钱是这条途径上边的本钱和。 多段图问题多段图问题(multistage graph problem)是求由是求由s到到t的最小本钱途径。的最小本钱途径。多

6、段图问题多段图问题 最优性原理对多段图成立最优性原理对多段图成立 假设假设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的更

7、的更短途径，那么这条途径一定比短途径，那么这条途径一定比v2,v3,vk-1,t途径短，这与假设矛盾，因此最优性原途径短，这与假设矛盾，因此最优性原理成立理成立0/1背包问题背包问题背包问题中的背包问题中的xj限定只能取限定只能取0或或1值，用值，用KNAP(1,j,X)来表示这个问题来表示这个问题效益值背包容量那么那么0/1背包问题就是背包问题就是KNAP(1,n,M)最优化决策序列的表示最优化决策序列的表示 设设S0是问题的初始形状。假定要作是问题的初始形状。假定要作n次决策次决策xi,1in X1=r1,1,r1,2,r1,pj是是x1的能够决策值的集合，的能够决策值的集合，而而S1,1

8、是在选取决策值是在选取决策值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最优化决策序列的表示最优化决策序列的表示 又设又设Xk=rk,1,rk,2,rk,pk是是xk的能够值的能够值的集合。的集

9、合。 Sk,jk是选取是选取rk,jk决策之后所产生决策之后所产生的形状的形状, 1jkpk Fk,jk 是相应于是相应于Sk,jk的最优决策序列。的最优决策序列。 因此，相应于因此，相应于Sk-1的最优决策序列是的最优决策序列是于是相应于于是相应于S0的最优决策序列为：的最优决策序列为：r1,rk-1, rk , Fk向前处置法向前处置法(forward approach) 从最后阶段开场，以逐渐向前递推的方式列出从最后阶段开场，以逐渐向前递推的方式列出求前一阶段决策值的递推关系式，即根据求前一阶段决策值的递推关系式，即根据xi+1,xn的那些最优决策序列来列出求取的那些最优决策序列来列出求

10、取xi决决策值的关系式，这就是动态规划的向前处置法策值的关系式，这就是动态规划的向前处置法 向后处置方法向后处置方法(backward approach)就是根据就是根据x1,xi-1的那些最优决策序列列出求的那些最优决策序列列出求xi的递推的递推关系式。关系式。 多段图的向前处置和向后处置多段图的向前处置和向后处置 0/1背包问题的向前处置和向后处置背包问题的向前处置和向后处置4.2 多段图多段图 多段图向前处置的算法多段图向前处置的算法 设设P(i, j)是一条从是一条从Vi中的节点中的节点j 到汇点到汇点t 的的最小本钱途径，最小本钱途径，COST(i, j)表示这条途径表示这条途径的本

11、钱，根据向前处置方法有公式的本钱，根据向前处置方法有公式4.5：由于，假设由于，假设 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)多段图的向前处置算法多段图的向前处置算法 例子中例子中5段图的段图的 实现计算步骤

12、：实现计算步骤： COST(4,9)=4 COST(4,10)=2 COST(4,11)=5 COST(3,6)=min6+COST(4,9), 5+COST(4,10)=7 COST(3,7)=min4+COST(4,9), 3+COST(4,10)=5 COST(3,8)=min5+COST(4,10), 6+COST(4,11)=7多段图的向前处置算法多段图的向前处置算法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

13、), 7+COST(2,3), 3+COST(2,4), 2+COST(2,5)=16多段图的向前处置算法多段图的向前处置算法 例子中例子中5段图的实现计算步骤：段图的实现计算步骤： 在计算每一个在计算每一个COST(i, j)的同时，记下每个的同时，记下每个形状形状(结点结点j)所做出的决策，设为所做出的决策，设为D(i, j)，那，那么可容易地求出这条最小本钱途径。么可容易地求出这条最小本钱途径。 D(3,6)=10D(3,7)=10 D(3,8)=10 D(2,2)=7 D(2,3)=6D(2,4)=8 D(2,5)=8 D(1,1)=2 设这条最小本钱途径是设这条最小本钱途径是sl ,

14、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多段图的向前处置算法多段图的向前处置算法多段图的向前处置算法多段图的向前处置算法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)rre

15、peatP(1)1;P(k)nfor j2 to k-1 doP(j)D(P(j-1)repeatEnd FGRAPH计算出计算出COST(j)的值，的值，并找出一条最小本钱并找出一条最小本钱途径途径找出最小本钱途径找出最小本钱途径上的第上的第j个结点个结点多段图的向后处置算法多段图的向后处置算法 向后处置方法向后处置方法(backward approach)就是就是根据根据x1,xi-1的那些最优决策序列列出的那些最优决策序列列出求求xi的递推关系式。的递推关系式。123458761110912st97324227111118654356524V1V2V3V4V5多段图的向后处置算法多段图的

16、向后处置算法 设设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的边长的边长, 所得的一切和所得的一切和中最小的那个值。中最小的那个值。由于，假设由于，假设 E成立成立, BCOST(2,j)=c(1,j),假设假设 E不成立，不成立，那么

17、有那么有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； 多段图的向后处置算法多段图的向后处置算法123458761110912st97324227111118654356524BCOST(3,6)=minBCOST(2,2)+4, BCOST(2,3)+2= 9BCOST(3,7)= minBCOST(2,2)+2,

18、BCOST(2,3)+7, BCOST(2,5)+11 = 11BCOST(3,8)= minBCOST(2,2)+1, BCOST(2,4)+11, BCOST(2,5)+8 = 101632728V1V2V3V4V5123458761110912st973242271111186543565241632728BCOST(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)=1691011V1V2V3V4V51234587611109

19、12st97324227111118654356524163272891011BCOST(5,12)=minBCOST(4,9)+4,BCOST(4,10)+2, BCOST(4,11)+5=1612V1V2V3V4V5多段图的向后处置算法多段图的向后处置算法 在计算每一个在计算每一个BCOST(i, j)的同时，记的同时，记下每个形状下每个形状(结点结点j)所做出的决策所做出的决策( 即即, 使使BCOST(i-1, j)+c(l, j)取最小值的取最小值的 l 值值), 设为设为D(i, j)，那么可容易地求出这条最，那么可容易地求出这条最小本钱途径。小本钱途径。对于实例中的最小本钱途径如

20、下所示：对于实例中的最小本钱途径如下所示：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)=10123458761110912st9732422711111865435652416327289101112V1V2V3V4V5多段图的向后处置算法多段图的向后处置算法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且使且使BCOS

21、T(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个结点个结点4.3 每对结点之间的最短途径复习略4.4 最优二分检索树问题的描画问题的描画1二分检索树定义二分检索树定义 二分检索树是一棵二元树，它或者为空，或者其每个二分检索树是一棵二元树，它或者为空，或者其每个结点含有一个可以比较大小的数

22、据元素，且有：结点含有一个可以比较大小的数据元素，且有：的左子树的一切元素比根结点中的元素小；的左子树的一切元素比根结点中的元素小；的右子树的一切元素比根结点中的元素大；的右子树的一切元素比根结点中的元素大；的左子树和右子树也是二分检索树。的左子树和右子树也是二分检索树。 注：注： 二分检索树要求树中一切结点的元素值互异二分检索树要求树中一切结点的元素值互异二分检索树ifforwhilerepeatloopifforrepeatloopwhile 对于一个给定的标识符集合，能够有假设干棵不同的二分检索树:不同形状的二分检索树对标识符的检索性能是不同的。不同形状的二分检索树对标识符的检索性能是不

23、同的。二分检索树检索一棵二分检索树算法检索一棵二分检索树算法procedure SEARCH(T,X,i)i=Twhile i0 do case :XIDENT(i):i=RCHILD(i) endcaserepeatend REARCH最优二分检索树问题最优二分检索树问题nii1)(Pnii0)(Q 设给定的标识符集合是设给定的标识符集合是a1,a2,an，并假定，并假定a1a2 an 。 设，设，P(i)是对是对ai检索的概率，检索的概率，Q(i)是正被检索的标识符是正被检索的标识符X恰好满足：恰好满足： ai Xai+1，0in设设a0=-,an+1=+)时的概率，即时的概率，即一种不胜

24、利检索情况下的概率。一种不胜利检索情况下的概率。那么那么 表示一切胜利检索的概率表示一切胜利检索的概率 表示一切不胜利检索的概率表示一切不胜利检索的概率 思索一切能够的胜利和不胜利检索情况，共思索一切能够的胜利和不胜利检索情况，共2n+1种能种能够的情况，有够的情况，有1Q(i)P(i)ni0ni1二分检索树二分检索树如右图所示内结点：代表胜利检索情况，刚好有n个。外结点：代表不胜利检索情况，刚好有n1个。二分检索树的预期本钱二分检索树的预期本钱 预期本钱：算法对于一切能够的胜利检索情况和不胜利检预期本钱：算法对于一切能够的胜利检索情况和不胜利检索情况，平均所要做的比较次数。根据期望值计算方法

25、，索情况，平均所要做的比较次数。根据期望值计算方法， 平均检索本钱平均检索本钱每种情况出现的概率每种情况出现的概率该情况下所需的该情况下所需的比较次数比较次数 平均检索本钱的构成：胜利检索成分不胜利检索成分平均检索本钱的构成：胜利检索成分不胜利检索成分 胜利检索：在胜利检索：在l级内结点终止的胜利检索，需求做级内结点终止的胜利检索，需求做l次比较次比较运算基于二分检索树构造。该级上的恣意结点运算基于二分检索树构造。该级上的恣意结点ai的本钱的本钱检索的本钱分担额为：检索的本钱分担额为： P(i)*level(ai) ； 其中，其中，level(ai) = 结点结点ai 的级数的级数=l二分检索

26、树的预期本钱二分检索树的预期本钱不胜利检索： 不胜利检索的等价类：每种不胜利检索情况定义了一个等价类，共有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) 那么预期总的本钱公式表示如下：) 1)(*Q(i)(*P(i)ni0ni1Eilevelaleveli最优二分检索树最优二分检索树最优二分检索树问题：最优二分检索树问题： 求一棵使得预期本钱最小的二分检索树求一棵使得预期本钱最小的二分检索树例例4.9

27、 标识符集合标识符集合a1,a2,a3=do,if,stop。能。能够的二分检索树如下所示。够的二分检索树如下所示。 成成 功功 检检 索：索：3种种 不胜利情况：不胜利情况：4种种最优二分检索树最优二分检索树stopdoifdoifstopstopifdoifdostopdostopif(a)(b)(c)(d)(e)最优二分检索树最优二分检索树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

28、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.6ifdostopdostopif(b)(c)多阶段决策过程多阶段决策过程 把构造二分检索树的过程看成一系列决策的结果。把构造二分检索树的过程看成一系列决策的结果。 决策的战略：决策树根，假设决策的战略：决策树根，假设a1,a2,an存在一棵二分存在一棵二分检索树，检索树，ak是该树的根，那么内结点是该树的根，那么内结点a1,a2,

29、ak-1和外部结和外部结点点E0,E1,Ek-1将位于根将位于根ak的左子树中，而其他的结点将位的左子树中，而其他的结点将位于右子树中。于右子树中。ak定义含义：含义： 左、右子树的预期本钱左、右子树的预期本钱左、右子树的根处左、右子树的根处于第一级于第一级 左、右子树中一切结点的级数相对于子树的根左、右子树中一切结点的级数相对于子树的根测定，而相对于原树的根少测定，而相对于原树的根少1kiikiiEleveliQaleveliPLCOST01) 1)(*)()(*)()(nikinikiEleveliQaleveliPRCOST) 1)(*)()(*)()(定义记：记： 那么，原二分检索树的

30、预期本钱可表示为：那么，原二分检索树的预期本钱可表示为： 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构成的二分检索树的本钱为构成的二分检索树的本钱为

31、C(i,j)，那么，那么对于最优二分检索树对于最优二分检索树T有，有， COST(L) = C(0,k-1) COST(R) = C(k,n)jilPlQiQjiW1)()()(),(定义那么，那么，对任何对任何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),() 1, 0()(),() 1, 0(min), 0(1nkWkWkPnkCkCnCnk

32、),() 1,()(),() 1,(min),(jkWkiWkPjkCkiCjiCjki),(),() 1,(minjiWjkCkiCjki用动态归划求最优二分检索树 首先计算一切使得j-i=1的C(i,j) 接着计算一切使得j-i=2的C(i,j) . 假设在这一计算期间，记下每棵Tij树的根R(i,j),那么最优二分检索树就可以由这些R(i,j)构造出来。 用动态归划求最优二分检索树例例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) (概率值概率值“扩展了扩展了

33、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

34、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),(),()1,(min),(jiWjkCkiCjicjki例4.10 (P) 用动态归划求最优二分检索树W, C, R计算结果计算结果那么，那么，C(0,4)=32二分检索树：二分检索树： T04=2 =T01(左子树，左子树，T24(右子树右子树 T01=1 =T00(左子树，左子树，T11(右子树右子树 T24=3 =T22(左子树，左子树，T34(右子树右子树 0123402,0,03,0,01,0,01,0,01,0

35、,018,8,17,7,23,3,33,3,4212,19,19,12,25,8,3316,25,211,19,2416,32,2W(j,j+i),C(j,j+i),R(j,j+i)ji 用动态归划求最优二分检索树树的形状ifdoreadwhile算法描画算法描画 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) /

36、 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 i

37、0 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计算时间计算时间 当当j-i=m时，有时，有n-m+1个个C(i,j)要计算要计算 C(i,j)的计算：的计算：(m) 每个每个C(i,j)要求找出要求找出m个量中的最小值。个量中的最小值。 那么，那么，n-m+1个个C(i,j)的计算时间：的计算时间： (

38、nm-m2) 对一切能够的对一切能够的m，总计算时间为：，总计算时间为：)()(312nmnmnm4.5 0/1背包问题背包问题 问题描画问题描画 背包问题中的背包问题中的xj限定只能取限定只能取0或或1值，用值，用KNAP(1,j,X)来表示这个问题来表示这个问题效益值效益值背包容量背包容量那么那么0/1背包问题就是背包问题就是KNAP(1,n,M)0/10/1背包问题最优化原理证明背包问题最优化原理证明 假设假设y1,y2,yn是最优解，那么是最优解，那么y2,y3,yn将是是将是是0/1 背包问题的子问题背包问题的子问题的最优解。由于，假设的最优解。由于，假设y2 , y3 , yn 是

39、子是子问题的最优解，且使得问题的最优解，且使得0/10/1背包问题最优化原理证明背包问题最优化原理证明 那么y1, y2 , y3 , yn 将是原问题的可行解，并且使得这与假设这与假设y1,y2,yny1,y2,yn是最优解相矛盾。是最优解相矛盾。因此，因此，0/1 0/1 背包问题具有最优子构造性质背包问题具有最优子构造性质得以证明，可以用动态规划的方法求最优得以证明，可以用动态规划的方法求最优解。解。0/1背包问题背包问题-处理方法处理方法 根据问题描画，可经过作出变量根据问题描画，可经过作出变量x1,x2,xn的一的一个决策序列来得到它的解。个决策序列来得到它的解。 假定决策假定决策x

40、的次序为的次序为x1,x2,xn 那么在对那么在对x1作出决策后，问题处于以下两种形状：作出决策后，问题处于以下两种形状： X1=0, 背包的剩余容量为背包的剩余容量为M，没有产生任何效益，没有产生任何效益 X1=1, 背包剩余容量为背包剩余容量为M-w1，效益值添加了，效益值添加了p1 显然，剩下来对显然，剩下来对x2,xn的决策相对于决策了的决策相对于决策了x1后所产生的问题形状应该是最优的，否那么，后所产生的问题形状应该是最优的，否那么， x1,x2,xn就不能够是最优的决策序列。就不能够是最优的决策序列。0/1背包问题背包问题处理方法处理方法 设设fj(X)是是KNAP(1,j,X)最

41、优解的值最优解的值 那么那么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情况情况下

42、的下的f1(X)的值的值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=10/1背包问题实例背包问题实例当当X0 时时, f2(X) = -

43、当当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。0/1背包问题实例背包问题实例 当当X0 时时, f

44、3(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)

45、 , 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。0/1背包问题实例背包问题实例0/1背包问题算法背包问题算法procedure DynamicKnapsack(p,w,n,M,f) /二维数组二维数组f(1:n,1:M)的定义与的定义与fj(X) 一样一样for

46、 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 DynamicKnapsack0/1背包问题实例背包问题实例 可经过检测可经过检测fi的取值情况可以确定获得最优解的最的取值情况可以确定获得最优解的最优决策序列优决策序列 f3(M)=6是在是在X3

47、=1的情况下获得的，因此的情况下获得的，因此X3=1 f3(M)-p3=1，f2(X)和和f1(X)都可取都可取1，那么，那么x2=0 f0不能取值不能取值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一样时取最大值的规那么归并而成一样时取最大值的规那么归并而成0/1背包

48、问题实例背包问题实例图解法图解法fi-1(X-wi)+pifi(X)i=0:函数不存在函数不存在f0(X)i=1: f0(X-2)+1f1(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=1i=2: f1(X-3)+2f2(X)f1(X)当当X0 时时, f2(X) = -当当0X2时时, f2(X) = maxf1(X) , f1(X-

49、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 =3i=3:f2(x-4)+5f3(X)当当X0 时时, f3(X) = -当当0X2 时时, f3(X) = maxf2(X), f2(X-4)+5= max0, - +5= 0当当2X3 时时, f3(X) = maxf2(X)

50、, 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 时

51、时, f3(X) =maxf2(X) , f2(X-4)+5=max3 , 3 + 5 = 80/1背包问题实例背包问题实例图解法图解法 由图可看出以下几点：由图可看出以下几点： 每一个每一个fi 完全由一些序偶完全由一些序偶(Pj,Wj)组成的集合所阐组成的集合所阐明，其中明，其中Wj是使是使fi 在其处产生一次阶跃的在其处产生一次阶跃的X值，值，Pj=fi(Wi)。 第一对序偶第一对序偶(P0,W0)=(0,0) 假设有假设有r次阶跃，就还要知道次阶跃，就还要知道r对序偶对序偶(Pj,Wj), 1jr r对序偶中，假定对序偶中，假定WjWj+1，由公式，由公式4.14可得可得PjM的那些序

52、偶的那些序偶(Pj,Wj)除掉。除掉。最优解序列确实定最优解序列确实定 这样生成的这样生成的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，且

53、，且(Pl-pn,Wl-wn)Sn-1，xn=1； 再判别留在再判别留在Sn-1的序偶的序偶(Pl,Wl)或或(Pl-pn,Wl-wn)能能否属于否属于Sn-2以确定以确定xn-1的取值。的取值。最优解序列确实定最优解序列确实定 例：例：n=3, (p1,p2,p3)=(1,2,5) ,(w1,w2,w3)=(2,3,4), M=6 f3(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,

54、2-w1)=(0,0)S0，所以，所以x1=1。 f3(6)=6的最优决策序列是的最优决策序列是(x1,x2,x3)=(1,0,1) 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

55、 xn0 /PX是是Sn的最末序偶的最末序偶/ xn1 /PY是是Sn的最末序偶的最末序偶/endif回溯确定回溯确定xn-1,x1End DKP初始值初始值利用支配规那么利用支配规那么生成生成Si的序偶集的序偶集合合确定最优确定最优解序列解序列确定确定xi取取0还是还是14.6 可靠性设计假定要设计一个系统,这个系统由假设干个以串联方式衔接在一同的不同设备所组成。设ri是设备Di的可靠性正常运转的概率，那么整个系统的可靠性就是假设第i级的设备Di的台数为mi,那么这mi台设备同时出现缺点的概率为(1-ri)mi，从而第i级的可靠性就变成1- (1-ri)mi。niir1可靠性设计(1)假设第

56、i级的可靠性由函数i(mi)给定，这个多级系统的可靠性是假设Cj 是一台设备j的本钱，由于系统中每种设备至少有一台，故设备j允许配置的台数至多为ni 1ijiim1)(jnkkjjccccu/ )(1可靠性设计(2)假设RELI(1,i,X)表示在可允许本钱X约束下，对第1种到第i种设备的可靠性设计问题，它的方式描画为极大化约束条件ijiim1)(Xmcijjj1可靠性设计(3) 于是整个系统的可靠性设计问题可用RELI(1,n,c)表示。它的一个最优解是对m1,mn的一系列决策的结果。每得到一个mi都要对其取值进展一次决策。 设fi(X)是在允许本钱值X约束下对前i种设备组成的子系统可靠性设

57、计的最优值。ijjjimXf1)(max)(可靠性设计(4)于是最优解的可靠性是fn(c).普通性况： )()(max)(11nnnnnumnmccfmcfnn)()(max)(11iiiiiumimccfmXfjj4.7 货郎担问题货郎担问题问题描画：问题描画：某售货员要到假设干个村庄售货，各村庄之间某售货员要到假设干个村庄售货，各村庄之间的路程是己知的，为了提高效率，售货员决议的路程是己知的，为了提高效率，售货员决议从所在商店出发，到每个村庄售一次货然后前从所在商店出发，到每个村庄售一次货然后前往商店，问他应选择一条什么道路才干使所走往商店，问他应选择一条什么道路才干使所走的总路程最短的总

58、路程最短?设设G(V,E)是一个具有边本钱是一个具有边本钱cij的有向图。的有向图。G的的一条周游道路是包含一条周游道路是包含V中每个结点的一个有向中每个结点的一个有向环。环。周游道路的本钱是此道路上一切边的本钱之和，周游道路的本钱是此道路上一切边的本钱之和，货郎担问题货郎担问题(traveling salesperson problem)是是求取具有最小本钱的周游道路问题。求取具有最小本钱的周游道路问题。货郎担问题实例货郎担问题实例 邮路问题邮路问题 在一条装配线上用一个机械手取紧固待在一条装配线上用一个机械手取紧固待装配部件上的螺帽问题装配部件上的螺帽问题 产品的消费安排问题产品的消费安排问题 能否能用动态规划处理能否能用动态规划处理 假设周游道路是开场于结点假设周游道路是开场于结点1并终止于结点并终止于结点1的的一条简单途径。一条简单途径。 每一条周游道路都由一条边每一条周游道路都由一条边和一条由结和一条由结点点k到结点到结点1的途径所组成，其中的途径所组成，其中kV-1; 而这条由结点而这条由结点k到结点到结点1的途径经过的途径经过V-1,k的每的每个结点各一次。个结点各一次。 容易看出，假设这条周游道路是最优的，那么容易看出，假设这条周游道路是最优的，那么这条由这条由k到到1的途径必定是经过的途径必定是经过V-1,k中一切结中一切结点的由点的由k到到