第四章第四章 动态规划动态规划第四章第四章 动态规划动态规划什么是动态规划什么是动态规划多段图多段图最优二分检索树最优二分检索树0/1背包问题背包问题可靠性设计可靠性设计货郎担问题货郎担问题2在在实际生活中，有这么一类问题，它们的活实际生活中，有这么一类问题，它们的活动过程可以分为若干个阶段，而且在任一阶动过程可以分为若干个阶段，而且在任一阶段后的行为都依赖于段后的行为都依赖于i 阶段的过程状态，而阶段的过程状态，而与与i 阶段之前的过程是如何达到这种状态的阶段之前的过程是如何达到这种状态的方式无关，这样的过程就构成了一个方式无关，这样的过程就构成了一个多阶段多阶段决策过程决策过程。根据这类问题的多阶段决策的特性，提出了根据这类问题的多阶段决策的特性，提出了解决这类问题的解决这类问题的“最优性原理最优性原理”，从而创建，从而创建了最优化问题的一种新的算法设计方法了最优化问题的一种新的算法设计方法动态规划动态规划。4.1 一般方法一般方法3在多阶段决策过程的每一个阶段，都可在多阶段决策过程的每一个阶段，都可能有多种选择的决策，但必须从中选取能有多种选择的决策，但必须从中选取一种决策。一旦各种阶段的决策选定之一种决策。一旦各种阶段的决策选定之后，就构成了解决这一问题的一个决策后，就构成了解决这一问题的一个决策序列。决策序列不同，导致的问题结果序列。决策序列不同，导致的问题结果也不同。也不同。动态规划的目标就是要在所有容许选择动态规划的目标就是要在所有容许选择的决策序列中选取一个会获得问题最优的决策序列中选取一个会获得问题最优解的决策序列，即解的决策序列，即最优决策序列最优决策序列。什么是动态规划4最优性原理最优性原理最优性原理最优性原理(Principle of Optimality) 过程的最优决策序列过程的最优决策序列具有如下性质：无论过程的具有如下性质：无论过程的初始状态和初始决策是什么，其余的决策都必须相对初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。于初始决策所产生的状态构成一个最优决策序列。 利用动态规划求解问题的前提利用动态规划求解问题的前提 1) 证明问题满足最优性原理证明问题满足最优性原理 如果对所求解问题证明满足最优性原理，则说明如果对所求解问题证明满足最优性原理，则说明用动态规划方法有可能解决该问题用动态规划方法有可能解决该问题 2) 获得问题状态的递推关系式获得问题状态的递推关系式 获得各阶段间的递推关系式是解决问题的关键。获得各阶段间的递推关系式是解决问题的关键。5多段图问题多段图问题多段图问题多段图问题123458761110912st97324227111118654356524V1V2V3V4V56多段图问题多段图问题多段图多段图G(V, E)是是个有向图。它具有如下特性：个有向图。它具有如下特性：图中的结点被划分图中的结点被划分成成k 2个不相交的集合个不相交的集合Vi ,1ik,ik,其中其中V1和和Vk分别只有一个结点分别只有一个结点s (源源点点) 和和 t ( 汇点汇点)。图中所有的边图中所有的边均具有如下性质：若均具有如下性质：若uVi ，则，则v Vi+1 ,1ik,ik,且每条边且每条边均附有均附有成本成本c(u, v)。从从s到到t的一条路径成本是这条路径上边的成本的一条路径成本是这条路径上边的成本和。和。多段图问题多段图问题(multistage graph problem)是求由是求由s到到t的的最小成本路径最小成本路径。7多段图问题多段图问题最优性原理对多段图成立最优性原理对多段图成立假设假设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路径路径短，这与假设矛盾，因此最优性原理成立短，这与假设矛盾，因此最优性原理成立80/1背包问题背包问题背包问题中的背包问题中的xj限定只能取限定只能取0或或1值，用值，用KNAP(1,j,X)来表示这个问题来表示这个问题效益值背包容量则则0/1背包问题就是背包问题就是KNAP(1,n,M)9最优化决策序列的表示最优化决策序列的表示设设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-1nk-1n。设。设x x1 1,x,xk-1k-1的最优的最优决策值是决策值是r r1 1,.,r,.,rk-1k-1，他们所产生的状态为他们所产生的状态为S S1 1,S,Sk-1k-110最优化决策序列的表示最优化决策序列的表示又设又设Xk=rk,1,rk,2,rk,pk是是xk的可能值的的可能值的集合。集合。 Sk,jk是选取是选取rk,jk决策之后所产生的状决策之后所产生的状态态, 1jkpkFk,jk 是相应于是相应于Sk,jk的的最优决策序列。最优决策序列。因此，相应于因此，相应于Sk-1的最优决策序列是的最优决策序列是于是相应于于是相应于S0的最优决策序列为：的最优决策序列为：r1,rk-1, rk , Fk11向前处理法向前处理法(forward approach)从最后阶段开始，以逐步向前递推的方式列出从最后阶段开始，以逐步向前递推的方式列出求前一阶段决策值的递推关系式，即根据求前一阶段决策值的递推关系式，即根据xi+1,xn的那些最优决策序列来列出求取的那些最优决策序列来列出求取xi决决策值的关系式，这就是动态规划的策值的关系式，这就是动态规划的向前处理法向前处理法向后处理方法向后处理方法(backward approach)就是根据就是根据x1,xi-1的那些最优决策序列列出求的那些最优决策序列列出求xi的的递推递推关系式。关系式。多段图的向前处理和向后处理多段图的向前处理和向后处理0/1背包问题的向前处理和向后处理背包问题的向前处理和向后处理124.2 多段图多段图多段图向前处理的算法多段图向前处理的算法设设P(i, j)是一条从是一条从Vi中的节点中的节点j 到汇到汇点点t 的最小的最小成本路径，成本路径，COST(i, j)表示这条路径的成本，表示这条路径的成本，根据向前处理方法有公式根据向前处理方法有公式4.5：13因为，若因为，若 EE成立成立, ,有有COST(k-1,j)=c(j,t),(k-1,j)=c(j,t),若若 EE不成立，则有不成立，则有COST(k-1,j)=(k-1,j)=，所以所以可以通过如下步骤解式公式（可以通过如下步骤解式公式（4.54.5），并求出），并求出COST(1,s)。首先对于所有首先对于所有jVk-2，计算计算COST(k-2, j)，然后对然后对所有的所有的jVk-3，计算计算计算计算COST(k-3, j)等等，最后等等，最后计算出计算计算出计算COST(1, s)多段图的多段图的向前处理算法向前处理算法14例子中例子中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多段图的多段图的向前处理算法向前处理算法15COST(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多段图的多段图的向前处理算法向前处理算法16例子中例子中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多段图的多段图的向前处理算法向前处理算法17多段图的多段图的向前处理算法向前处理算法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个结点个结点18多段图的多段图的向后处理算法向后处理算法向后处理方法向后处理方法(backward approach)就是就是根据根据x1,xi-1的那些最优决策序列列出的那些最优决策序列列出求求xi的递推关系式。的递推关系式。123458761110912st97324227111118654356524V1V2V3V4V519多多段图的段图的向后处理算法向后处理算法设设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的边长的边长, 所得的所有和所得的所有和中最小的那个值。中最小的那个值。20因为，若因为，若 EE成立成立, , BCOST(2,j)=c(1,j),BCOST(2,j)=c(1,j),若若 EE不成立，不成立，则有则有BCOST(2,j)=BCOST(2,j)=，所以可以通过如下步所以可以通过如下步骤解式公式（骤解式公式（4.64.6），），首先对首先对i3计算计算BCOST，然后对然后对 i4 计算计算BCOST等，最后等，最后计算出计算出BCOST(k，t)。BCOST(2，2)=9； BCOST(2，3)=7；BCOST(2，4)=3； BCOST(2，5)=2； 多段图的多段图的向后处理算法向后处理算法21123458761110912st97324227111118654356524BCOST(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 = 101632728V1V2V3V4V522123458761110912st973242271111186543565241632728BCOST(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)=1691011V1V2V3V4V523123458761110912st97324227111118654356524163272891011BCOST(5,12)=minBCOST(4,9)+4,BCOST(4,10)+2, BCOST(4,11)+5=1612V1V2V3V4V524多段图的多段图的向后处理算法向后处理算法在计算每一个在计算每一个BCOST(i, j)的同时，记的同时，记下每个状态下每个状态(结点结点j)所做出的决策所做出的决策( 即即, 使使BCOST(i-1, j)+c(l, j)取最小值的取最小值的 l 值值), 设为设为D(i, j)，则可容易地求出这条最则可容易地求出这条最小成本路径。小成本路径。25对于实例中的最小成本路径如下所示：对于实例中的最小成本路径如下所示：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)=10123458761110912st9732422711111865435652416327289101112V1V2V3V4V526多段图的多段图的向后处理算法向后处理算法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个结点个结点274.3 每对结点之间的最短路径复习（略）284.4 最优二分检索树问题的描述问题的描述1）二分检索树定义）二分检索树定义 二分检索树是一棵二元树，它或者为空，或者其每个二分检索树是一棵二元树，它或者为空，或者其每个结点含有一个可以比较大小的数据元素，且有：结点含有一个可以比较大小的数据元素，且有：的左子树的所有元素比根结点中的元素小；的左子树的所有元素比根结点中的元素小；的右子树的所有元素比根结点中的元素大；的右子树的所有元素比根结点中的元素大；的左子树和右子树也是二分检索树。的左子树和右子树也是二分检索树。 注：注： 二分检索树要求树中所有结点的元素值互异二分检索树要求树中所有结点的元素值互异29二分检索树ifforwhilerepeatloopifforrepeatloopwhile 对于一个给定的对于一个给定的标识符标识符集合，可能有集合，可能有若干棵若干棵不同的二分检索树不同的二分检索树: :不同形态的二分检索树对标识符的不同形态的二分检索树对标识符的检索性能检索性能是是不同不同的。的。30二分检索树检索一棵二分检索树算法检索一棵二分检索树算法procedure SEARCH(T,X,i)i=Twhile i0 do case :XIDENT(i):i=RCHILD(i) endcaserepeatend REARCH31最优二分检索树问题最优二分检索树问题 设给定的标识符集合是设给定的标识符集合是a1,a2,an，并假定，并假定a1a2 an 。 设，设，P(i)是对是对ai检索的概率，检索的概率，Q(i)是正被检索的标识符是正被检索的标识符X恰好满足：恰好满足： ai Xai+1，0in（设（设a0=-,an+1=+)时的概率，即一时的概率，即一种不成功检索情况下的概率。种不成功检索情况下的概率。则则 表示所有成功检索的概率表示所有成功检索的概率 表示所有不成功检索的概率表示所有不成功检索的概率 考虑所有可能的成功和不成功检索情况，共考虑所有可能的成功和不成功检索情况，共2n+1种可种可能的情况，有能的情况，有32二分检索树二分检索树（如右图所示）内结点：代表成功检索情况，刚好有n个。外结点：代表不成功检索情况，刚好有n1个。33二分检索树的预期成本二分检索树的预期成本 预期成本预期成本：算法对于所有可能的成功检索情况和不成功检：算法对于所有可能的成功检索情况和不成功检索情况，平均所要做的比较次数。根据期望值计算方法，索情况，平均所要做的比较次数。根据期望值计算方法， 平均检索成本平均检索成本每种情况出现的每种情况出现的概率概率该情况下所需的该情况下所需的比较比较次数次数 平均检索成本的平均检索成本的构成构成：成功检索成分成功检索成分不成功检索成分不成功检索成分 成功检索成功检索：在：在l级内结点终止的成功检索，需要做级内结点终止的成功检索，需要做l次比较次比较运算（基于二分检索树结构）。该级上的任意结点运算（基于二分检索树结构）。该级上的任意结点ai的的成本检成本检索的成本分担额索的成本分担额为：为： P(i)*level(ai) ； 其中，其中，level(ai) = 结点结点ai 的级数的级数=l34二分检索树的预期成本二分检索树的预期成本不成功检索：不成功检索的不成功检索的等价类等价类：每种不成功检索情况定义了一个：每种不成功检索情况定义了一个等价类，共有等价类，共有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) 则预期总的成本公式表示如下：则预期总的成本公式表示如下：35最优二分检索树最优二分检索树最优二分检索树问题最优二分检索树问题： 求一棵使得求一棵使得预期成本预期成本最小最小的二分检索树的二分检索树例例4.9 标识符集合（标识符集合（a1,a2,a3）=（do,if,stop）。可）。可能的二分检索树如下所示。能的二分检索树如下所示。 成成 功功 检检 索：索：3种种 不成功情况：不成功情况：4种种36最优二分检索树最优二分检索树stopdoifdoifstopstopifdoifdostopdostopif(a)(b)(c)(d)(e)37最优二分检索树最优二分检索树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.6ifdostopdostopif(b)(c)38多阶段决策过程多阶段决策过程 把构造二分检索树的过程看成一系列决策的结果。把构造二分检索树的过程看成一系列决策的结果。 决策的策略：决策树根，如果决策的策略：决策树根，如果a1,a2,an存在一棵二分存在一棵二分检索树，检索树，ak是该树的根，则内结点是该树的根，则内结点a1,a2,ak-1和外部结点和外部结点E0,E1,Ek-1将位于根将位于根ak的左子树中，而其余的结点将位于右的左子树中，而其余的结点将位于右子树中。子树中。ak由ak1, ak+2, ,an及Ek,Ek+1,En构成的二分检索树由a1,a2,ak-1及E0,E1,Ek-1构成的二分检索树39定义含义：含义： 左、右子树左、右子树的的预期成本预期成本左、右子树的左、右子树的根根处处于于第一级第一级 左、右子树中所有结点的级数相对于子树的根左、右子树中所有结点的级数相对于子树的根测定，而相对于原树的根少测定，而相对于原树的根少140定义记：记： 则，原二分检索树的预期成本可表示为：则，原二分检索树的预期成本可表示为： 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)41定义则，则，对任何对任何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)，0in42用动态归划求最优二分检索树首先计算所有使得j-i=1的C(i,j)接着计算所有使得j-i=2的C(i,j).如果在这一计算期间，记下每棵Tij树的根R(i,j),那么最优二分检索树就可以由这些R(i,j)构造出来。43 用动态归划求最优二分检索树例例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)44 用动态归划求最优二分检索树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,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)ji45 用动态归划求最优二分检索树树的形态ifdoreadwhile46算法描述算法描述 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 OBST47计算时间计算时间 当当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，总计算时间为总计算时间为：484.5 0/1背包问题背包问题问题描述问题描述背包问题中的背包问题中的xj限定只能取限定只能取0或或1值，用值，用KNAP(1,j,X)来表示这个问题来表示这个问题效益值效益值背包容量背包容量则则0/1背包问题就是背包问题就是KNAP(1,n,M)490/10/1背包问题最优化原理证明背包问题最优化原理证明若若y1,y2,yn是是最优解，则最优解，则y2,y3,yn将是是将是是0/1 背包问题的子问题背包问题的子问题的最优解。因为，若的最优解。因为，若y2 , y3 , yn 是子是子问题的最优解，且使得问题的最优解，且使得500/10/1背包问题最优化原理证明背包问题最优化原理证明则y1,y2 , y3 , yn 将是原问题的可将是原问题的可行解，并且使得行解，并且使得这与假设这与假设y1,y2,yn是最优解相矛盾。是最优解相矛盾。因此，因此，0/1 背包问题具有最优子结构性质得背包问题具有最优子结构性质得以证明，以证明，可以用动态规划的方法求最优解可以用动态规划的方法求最优解。510/1背包问题背包问题-解决方法解决方法根据问题描述，可通过作出变量根据问题描述，可通过作出变量x1,x2,xn的一的一个决策序列来得到它的解。个决策序列来得到它的解。假定决策假定决策x的次序为的次序为x1,x2,xn则则在对在对x1作出决策后，问题处于下列两种状态：作出决策后，问题处于下列两种状态：X1=0, 背包的剩余容量为背包的剩余容量为M，没有产生任何效益没有产生任何效益X1=1, 背包剩余容量为背包剩余容量为M-w1，效益值增加了效益值增加了p1显然，剩下来显然，剩下来对对x2,xn的决策相对于决策了的决策相对于决策了x1后所产生的问题状态应该是最优的，否则，后所产生的问题状态应该是最优的，否则， x1,x2,xn就不可能是最优的决策序列。就不可能是最优的决策序列。520/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和和Xww1 1情况下的情况下的f f1 1(X)(X)的值的值530/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+1=0当当X2时时, f1(X) = maxf0(X) , f0(X-2)+1 =max0, 0+1=1540/1背包问题实例背包问题实例当当X0 时时, f2(X) = -当当0X2时时, f2(X) = maxf1(X) , f1(X-3)+2 = max 0 , -+2 +2 =0当当2X3 时时, f2(X) = maxf1(X) , f1(X-3)+2 = max 1 , -+2 +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。550/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。560/1背包问题实例背包问题实例570/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 DynamicKnapsack580/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相同时相同时取最大值的规则归并而成取最大值的规则归并而成590/1背包问题实例背包问题实例图图解法解法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+1=0当当X2时时, f1(X) = maxf0(X) , f0(X-2)+1 =max0, 0+1=160i=2: f1(X-3)+2f2(X)f1(X)当当X0 时时, f2(X) = -当当0X2时时, f2(X) = maxf1(X) , f1(X-3)+2 = max 0 , -+2+2 =0当当2X3 时时, f2(X) = maxf1(X) , f1(X-3)+2 = max 1 , -+2+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 =361i=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), 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 = 8620/1背包问题实例背包问题实例图图解法解法由图可看出以下几点：由图可看出以下几点：每一个每一个fi 完全由一些序偶完全由一些序偶(Pj,Wj)组成的集合所说明，其组成的集合所说明，其中中Wj是使是使fi 在在其处产生一次阶跃的其处产生一次阶跃的X值，值，Pj=fi(Wi)。第一对序偶第一对序偶(P0,W0)=(0,0)如果有如果有r次阶跃，就还要知道次阶跃，就还要知道r对序偶对序偶(Pj,Wj), 1jrjrr对序偶中，假定对序偶中，假定WjWj+1，由公式由公式4.14可得可得PjM的那的那些序偶些序偶(Pj,Wj)除掉。除掉。67最优解序列的确定最优解序列的确定这样生成的这样生成的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的取值。的取值。68最优解序列的确定最优解序列的确定例：例：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) 690/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还是还是1704.6 可靠性设计假定要设计一个系统,这个系统由若干个以串联方式连接在一起的不同设备所组成。设ri是设备Di的可靠性（正常运转的概率），则整个系统的可靠性就是若第i级的设备Di的台数为mi,则这mi台设备同时出现故障的概率为(1-ri)mi，从而第i级的可靠性就变成1-(1-ri)mi。71可靠性设计(1)假设第i级的可靠性由函数i(mi)给定，这个多级系统的可靠性是假设Cj是一台设备j的成本，由于系统中每种设备至少有一台，故设备j允许配置的台数至多为72可靠性设计(2)如果RELI(1,i,X)表示在可容许成本X约束下，对第1种到第i种设备的可靠性设计问题，它的形式描述为极大化约束条件73可靠性设计(3)于是整个系统的可靠性设计问题可用RELI(1,n,c)表示。它的一个最优解是对m1,mn的一系列决策的结果。每得到一个mi都要对其取值进行一次决策。设fi(X)是在容许成本值X约束下对前i种设备组成的子系统可靠性设计的最优值。74可靠性设计(4)于是最优解的可靠性是fn(c).一般性况：754.7 货郎担问题货郎担问题问题描述：问题描述：某售货员要到若干个村庄售货，各村庄之间的路程某售货员要到若干个村庄售货，各村庄之间的路程是己知的，为了提高效率，售货员决定从所在商店是己知的，为了提高效率，售货员决定从所在商店出发，到每个村庄售一次货然后返回商店，问他应出发，到每个村庄售一次货然后返回商店，问他应选择一条什么路线才能使所走的总路程最短选择一条什么路线才能使所走的总路程最短?设设G(V,E)是一个具有边成本是一个具有边成本cij的有向图。的有向图。G的一条的一条周游路线是包含周游路线是包含V中每个结点的一个有向环。中每个结点的一个有向环。周游路线的成本是此路线上所有边的成本之和，周游路线的成本是此路线上所有边的成本之和，货货郎担问题郎担问题(traveling salesperson problem)是求取具是求取具有最小成本的周游路线问题。有最小成本的周游路线问题。76货郎担问题实例货郎担问题实例邮路问题邮路问题在一条装配线上用一个机械手取紧固待在一条装配线上用一个机械手取紧固待装配部件上的螺帽问题装配部件上的螺帽问题产品的生产安排问题产品的生产安排问题77是否能用动态规划解决是否能用动态规划解决假设周游路线是开始于结点假设周游路线是开始于结点1并终止于结点并终止于结点1的的一条简单路径。一条简单路径。每一条周游路线都由一条边每一条周游路线都由一条边和一条由结和一条由结点点k到结点到结点1的路径所组成，其中的路径所组成，其中kV-1;而这条由结点而这条由结点k到结点到结点1的路径通过的路径通过V-1,k的每的每个结点各一次。个结点各一次。容易看出，容易看出，如果这条周游路线是最优的，那么如果这条周游路线是最优的，那么这条由这条由k到到1的路径必定是通过的路径必定是通过V-1,k中所有结中所有结点的由点的由k到到1的最短路径，因此最优性原理成立的最短路径，因此最优性原理成立。78动态规划的解决方法动态规划的解决方法假设假设g(i,S)是由结点是由结点i开始，通过开始，通过S中的所有中的所有结点，在结点结点，在结点1终止的一条最段路径长度终止的一条最段路径长度。 g(1,V-1)是一条最优的周游路线长度。于是一条最优的周游路线长度。于是可以得到：是可以得到：k79货郎担问题实例货郎担问题实例143212341010152025091036130124889010591561081320812980货郎担问题实例货郎担问题实例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 81货郎担问题实例货郎担问题实例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 = 2382货郎担问题实例货郎担问题实例最后，可得最后，可得 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 - 1834.8 流水线调度问题设有n个作业，每个作业要执行m个任务：T1i,T2i,Tmi,(1in)任务Tji只能在设备Pj上执行。对任一作业i,在任务Tj-1，i没完成以前，不能对任务Tji开始处理。同一台设备在任何时刻不能同时处理一个以上的任务。假设完成任务Tji所要求的时间是tji。如何将这n*m个任务分配给这m台设备，才能使这n个作业在以上要求下顺利完成？84两种可能的调度非抢先调度抢先调度例6.18(P148)85最优完成时间OFT调度一组给定作业的最优完成时间OFT调度是一种非抢先调度S，它对所有非抢先调度而言，调度S完成时间F(S)的值最小。本节只讨论当m=2时获取OFT调度这种特殊情况的算法。为方便起见，用ai表示t1i，bi表示t2i86最优调度排列具有的性质在给出了这个排列的第一个作业后，剩下的排列相对于这两台设备在完成第一个作业时所处的状态而言是最何优。87递推关系式假设对作业1,2,k的一种调度排列为a1,a2,ak。对于这种调度，设h1和h2分别是在设备P1和P2上完成任务(T11,T12,T1k)和(T21,T22,T2k)的时间。设t=h2-h1，则在t这段时间及其以前，设备P2不能用来处理别的作业的任务。88递推关系式假设g(S,t)是上述t下S的最优调度长度。g(1,2,n,0)=minai+g(1,2,.,n-i,bi)1in一般情况：g(S,t)=minai+g(S-i,bi+maxt-ai,0)(1in)89递推关系式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,aimaxt,ai+aj-bi,ai或minbi,ajminbj,ai则g(S,t)g(S,t)90调度规则把全部ai和bi分类成非降序列按照这一分类次序考察些序列：1.如果序列中下一个数是aj且作j还没调度，那么在还没使用的最左位置调度作业j;2.如果下个数是bj且作业j还没有调度，那么在还没有使用的最右位置调度作业j；3.如果已经调度了作业j，则转到该序列的下一个数。91