算法分析與設(shè)計(jì)動(dòng)態(tài)規(guī)劃.ppt

第四章 動(dòng)態(tài)規(guī)劃,2,第四章 動(dòng)態(tài)規(guī)劃,什么是動(dòng)態(tài)規(guī)劃 多段圖 最優(yōu)二分檢索樹(shù) 0/1背包問(wèn)題 可靠性設(shè)計(jì) 貨郎擔(dān)問(wèn)題,3,在實(shí)際生活中，有這么一類問(wèn)題，它們的活動(dòng)過(guò)程可以分為若干個(gè)階段，而且在任一階段后的行為都依賴于i 階段的過(guò)程狀態(tài)，而與i 階段之前的過(guò)程是如何達(dá)到這種狀態(tài)的方式無(wú)關(guān)，這樣的過(guò)程就構(gòu)成了一個(gè)多階段決策過(guò)程。 根據(jù)這類問(wèn)題的多階段決策的特性，提出了解決這類問(wèn)題的“最優(yōu)性原理”，從而創(chuàng)建了最優(yōu)化問(wèn)題的一種新的算法設(shè)計(jì)方法動(dòng)態(tài)規(guī)劃。,4.1 一般方法,4,在多階段決策過(guò)程的每一個(gè)階段，都可能有多種選擇的決策，但必須從中選取一種決策。一旦各種階段的決策選定之后，就構(gòu)成了解決這一問(wèn)題的一個(gè)決策序列。決策序列不同，導(dǎo)致的問(wèn)題結(jié)果也不同。 動(dòng)態(tài)規(guī)劃的目標(biāo)就是要在所有容許選擇的決策序列中選取一個(gè)會(huì)獲得問(wèn)題最優(yōu)解的決策序列，即最優(yōu)決策序列。,什么是動(dòng)態(tài)規(guī)劃,5,最優(yōu)性原理,最優(yōu)性原理(Principle of Optimality) 過(guò)程的最優(yōu)決策序列具有如下性質(zhì)：無(wú)論過(guò)程的初始狀態(tài)和初始決策是什么，其余的決策都必須相對(duì)于初始決策所產(chǎn)生的狀態(tài)構(gòu)成一個(gè)最優(yōu)決策序列。 利用動(dòng)態(tài)規(guī)劃求解問(wèn)題的前提 1) 證明問(wèn)題滿足最優(yōu)性原理 如果對(duì)所求解問(wèn)題證明滿足最優(yōu)性原理，則說(shuō)明用動(dòng)態(tài)規(guī)劃方法有可能解決該問(wèn)題 2) 獲得問(wèn)題狀態(tài)的遞推關(guān)系式 獲得各階段間的遞推關(guān)系式是解決問(wèn)題的關(guān)鍵。,6,多段圖問(wèn)題,多段圖問(wèn)題,7,多段圖問(wèn)題,多段圖G(V, E)是個(gè)有向圖。它具有如下特性： 圖中的結(jié)點(diǎn)被劃分成k 2個(gè)不相交的集合Vi ,1ik,其中V1和Vk分別只有一個(gè)結(jié)點(diǎn)s (源點(diǎn)) 和 t ( 匯點(diǎn))。 圖中所有的邊均具有如下性質(zhì)：若uVi ，則v Vi+1 ,1ik,且每條邊均附有成本c(u, v)。 從s到t的一條路徑成本是這條路徑上邊的成本和。 多段圖問(wèn)題(multistage graph problem)是求由s到t的最小成本路徑。,8,多段圖問(wèn)題,最優(yōu)性原理對(duì)多段圖成立 假設(shè)s,v2,v3,vk-1,t是一條由s到t的最短路徑 再假設(shè)從源點(diǎn)s開(kāi)始，已作出了到結(jié)點(diǎn)V2的決策，因此V2就是初始決策所產(chǎn)生的狀態(tài) 如果把V2看成是原問(wèn)題的一個(gè)子問(wèn)題的初始狀態(tài)，解決這個(gè)子問(wèn)題就是找出一條由V2到t的最短路徑 這條最短路徑顯然是v2,v3,vk-1,t 如果不是，設(shè)v2,q3,qk-1,t由V2到t的更短路徑，則這條路徑肯定比v2,v3,vk-1,t路徑短，這與假設(shè)矛盾，因此最優(yōu)性原理成立,9,0/1背包問(wèn)題,背包問(wèn)題中的xj限定只能取0或1值，用KNAP(1,j,X)來(lái)表示這個(gè)問(wèn)題,效益值,背包容量,則0/1背包問(wèn)題就是KNAP(1,n,M),10,最優(yōu)化決策序列的表示,設(shè)S0是問(wèn)題的初始狀態(tài)。假定要作n次決策xi,1in X1=r1,1,r1,2,r1,pj是x1的可能決策值的集合，而S1,1是在選取決策值r1,j1以后所產(chǎn)生的狀態(tài)， 1j1p1 又設(shè)F1,j1是相應(yīng)于狀態(tài)S1,j1的最優(yōu)決策序列 則相應(yīng)于S0的最優(yōu)決策序列就是r1,j1 F1,j1 | 1j1p1中最優(yōu)的序列，記作,如果已作了k-1次決策，1k-1n。設(shè)x1,xk-1的最優(yōu)決策值是r1,rk-1，他們所產(chǎn)生的狀態(tài)為S1,Sk-1,11,最優(yōu)化決策序列的表示,又設(shè)Xk=rk,1,rk,2,rk,pk是xk的可能值的集合。 Sk,jk是選取rk,jk決策之后所產(chǎn)生的狀態(tài), 1jkpk Fk,jk 是相應(yīng)于Sk,jk的最優(yōu)決策序列。 因此，相應(yīng)于Sk-1的最優(yōu)決策序列是,于是相應(yīng)于S0的最優(yōu)決策序列為：r1,rk-1, rk , Fk,12,向前處理法(forward approach),從最后階段開(kāi)始，以逐步向前遞推的方式列出求前一階段決策值的遞推關(guān)系式，即根據(jù)xi+1,xn的那些最優(yōu)決策序列來(lái)列出求取xi決策值的關(guān)系式，這就是動(dòng)態(tài)規(guī)劃的向前處理法 向后處理方法(backward approach)就是根據(jù)x1,xi-1的那些最優(yōu)決策序列列出求xi的遞推關(guān)系式。 多段圖的向前處理和向后處理 0/1背包問(wèn)題的向前處理和向后處理,13,4.2 多段圖,多段圖向前處理的算法 設(shè)P(i, j)是一條從Vi中的節(jié)點(diǎn)j 到匯點(diǎn)t 的最小成本路徑，COST(i, j)表示這條路徑的成本，根據(jù)向前處理方法有公式4.5：,14,因?yàn)?，?E成立,有COST(k-1,j)=c(j,t),若 E不成立，則有COST(k-1,j)=，所以可以通過(guò)如下步驟解式公式（4.5），并求出COST(1,s)。 首先對(duì)于所有jVk-2，計(jì)算COST(k-2, j)，然后對(duì)所有的jVk-3，計(jì)算計(jì)算COST(k-3, j)等等，最后計(jì)算出計(jì)算COST(1, s),多段圖的向前處理算法,15,例子中5段圖的 實(shí)現(xiàn)計(jì)算步驟： 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,多段圖的向前處理算法,16,COST(2,2)=min4+COST(3,6), 2+COST(3,7), 1+COST(3,8)=7 COST(2,3)=9 COST(2,4)=18 COST(2,5)=15 COST(1,1)=min9+COST(2,2), 7+COST(2,3), 3+COST(2,4), 2+COST(2,5)=16,多段圖的向前處理算法,17,例子中5段圖的實(shí)現(xiàn)計(jì)算步驟： 在計(jì)算每一個(gè)COST(i, j)的同時(shí)，記下每個(gè)狀態(tài)(結(jié)點(diǎn)j)所做出的決策，設(shè)為D(i, j)，則可容易地求出這條最小成本路徑。 D(3,6)=10 D(3,7)=10 D(3,8)=10 D(2,2)=7 D(2,3)=6 D(2,4)=8 D(2,5)=8 D(1,1)=2 設(shè)這條最小成本路徑是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,n COST(n)0 for jn -1 to 1 by 1 do 設(shè)r是一個(gè)這樣的結(jié)點(diǎn),E且使c(j,r)+COST(r)取小值 COST(j)c(j,r)+COST(r) D(j)r repeat P(1)1;P(k)n for j2 to k-1 do P(j)D(P(j-1) repeat End FGRAPH,計(jì)算出COST(j)的值，并找出一條最小成本路徑,找出最小成本路徑上的第j個(gè)結(jié)點(diǎn),19,多段圖的向后處理算法,向后處理方法(backward approach)就是根據(jù)x1,xi-1的那些最優(yōu)決策序列列出求xi的遞推關(guān)系式。,20,多段圖的向后處理算法,設(shè)BP(i, j)是一條由源點(diǎn)s到Vi中結(jié)點(diǎn)j的最小成本路徑，BCOST(i, j)表示BP(i, j)的成本，由向后處理方法得到公式4.6：,即由源點(diǎn)s到Vi中結(jié)點(diǎn)j的最小成本，等于由源點(diǎn)s到Vi-1中任一結(jié)點(diǎn)l 的最小成本加上Vi-1中結(jié)點(diǎn)l 到Vi中結(jié)點(diǎn)j的邊長(zhǎng), 所得的所有和中最小的那個(gè)值。,21,因?yàn)?，?E成立, BCOST(2,j)=c(1,j),若 E不成立，則有BCOST(2,j)=，所以可以通過(guò)如下步驟解式公式（4.6），首先對(duì)i3計(jì)算BCOST，然后對(duì) i4 計(jì)算BCOST等，最后計(jì)算出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= 9 BCOST(3,7)= minBCOST(2,2)+2, BCOST(2,3)+7, BCOST(2,5)+11 = 11 BCOST(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=15 BCOST(4,10)=minBCOST(3,6)+5, BCOST(3,7)+3, BCOST(3,8)+5=14 BCOST(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,多段圖的向后處理算法,在計(jì)算每一個(gè)BCOST(i, j)的同時(shí)，記下每個(gè)狀態(tài)(結(jié)點(diǎn)j)所做出的決策( 即, 使BCOST(i-1, j)+c(l, j)取最小值的 l 值), 設(shè)為D(i, j)，則可容易地求出這條最小成本路徑。,26,對(duì)于實(shí)例中的最小成本路徑如下所示： 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,n BCOST(1)0 for j2 to n do 設(shè)r是一個(gè)這樣的結(jié)點(diǎn)，E且使BCOST(r) +c(r,j)取小值 BCOST(j)BCOST(r)+ c(r,j) D(j)r repeat P(1)1;P(k)n for jk-1 to 2 by -1 do P(j)D(P(j+1) repeat End BGRAPH,計(jì)算出BCOST(j)的值，并找出一條最小成本路徑,找出最小成本路徑上的第j個(gè)結(jié)點(diǎn),28,4.3 每對(duì)結(jié)點(diǎn)之間的最短路徑,復(fù)習(xí)（略）,29,4.4 最優(yōu)二分檢索樹(shù),問(wèn)題的描述 1）二分檢索樹(shù)定義 二分檢索樹(shù)是一棵二元樹(shù)，它或者為空，或者其每個(gè)結(jié)點(diǎn)含有一個(gè)可以比較大小的數(shù)據(jù)元素，且有： 的左子樹(shù)的所有元素比根結(jié)點(diǎn)中的元素??； 的右子樹(shù)的所有元素比根結(jié)點(diǎn)中的元素大； 的左子樹(shù)和右子樹(shù)也是二分檢索樹(shù)。 注： 二分檢索樹(shù)要求樹(shù)中所有結(jié)點(diǎn)的元素值互異,30,二分檢索樹(shù),對(duì)于一個(gè)給定的標(biāo)識(shí)符集合，可能有若干棵不同的二分檢索樹(shù):,不同形態(tài)的二分檢索樹(shù)對(duì)標(biāo)識(shí)符的檢索性能是不同的。,31,二分檢索樹(shù),檢索一棵二分檢索樹(shù)算法 procedure SEARCH(T,X,i) i=T while i0 do case :XIDENT(i):i=RCHILD(i) endcase repeat end REARCH,32,最優(yōu)二分檢索樹(shù)問(wèn)題,設(shè)給定的標(biāo)識(shí)符集合是a1,a2,an，并假定a1a2 an 。 設(shè)，P(i)是對(duì)ai檢索的概率，Q(i)是正被檢索的標(biāo)識(shí)符X恰好滿足： ai Xai+1，0in（設(shè)a0=-,an+1=+)時(shí)的概率，即一種不成功檢索情況下的概率。 則 表示所有成功檢索的概率 表示所有不成功檢索的概率 考慮所有可能的成功和不成功檢索情況，共2n+1種可能的情況，有,33,二分檢索樹(shù),二分檢索樹(shù)（如右圖所示） 內(nèi)結(jié)點(diǎn)：代表成功檢索情況，剛好有n個(gè)。 外結(jié)點(diǎn)：代表不成功檢索情況，剛好有n1個(gè)。,34,二分檢索樹(shù)的預(yù)期成本,預(yù)期成本：算法對(duì)于所有可能的成功檢索情況和不成功檢索情況，平均所要做的比較次數(shù)。根據(jù)期望值計(jì)算方法， 平均檢索成本每種情況出現(xiàn)的概率該情況下所需的比較次數(shù) 平均檢索成本的構(gòu)成：成功檢索成分不成功檢索成分 成功檢索：在l級(jí)內(nèi)結(jié)點(diǎn)終止的成功檢索，需要做l次比較運(yùn)算（基于二分檢索樹(shù)結(jié)構(gòu)）。該級(jí)上的任意結(jié)點(diǎn)ai的成本檢索的成本分擔(dān)額為： P(i)*level(ai) ； 其中，level(ai) = 結(jié)點(diǎn)ai 的級(jí)數(shù)=l,35,二分檢索樹(shù)的預(yù)期成本,不成功檢索： 不成功檢索的等價(jià)類：每種不成功檢索情況定義了一個(gè)等價(jià)類，共有n+1個(gè)等價(jià)類Ei(0in)。其中， E0=X|Xa0 Ei=X|aiXai+1(1in) En=X|Xan 若Ei處于l級(jí)，則算法需作l-1次迭代。則，l級(jí)上的外部結(jié)點(diǎn)的不成功檢索的成本分擔(dān)額為： Q(i)*(level(Ei)-1) 則預(yù)期總的成本公式表示如下：,36,最優(yōu)二分檢索樹(shù),最優(yōu)二分檢索樹(shù)問(wèn)題： 求一棵使得預(yù)期成本最小的二分檢索樹(shù) 例4.9 標(biāo)識(shí)符集合（a1,a2,a3）=（do,if,stop）。可能的二分檢索樹(shù)如下所示。 成 功 檢 索：3種 不成功情況：4種,37,最優(yōu)二分檢索樹(shù),38,最優(yōu)二分檢索樹(shù),1) 等概率：P(i)=Q(i)=1/7 cost(a) = 15/7 cost(b) = 13/7 最優(yōu) 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 最優(yōu) cost(d) = 2.15 cost(e) = 1.6,39,多階段決策過(guò)程,把構(gòu)造二分檢索樹(shù)的過(guò)程看成一系列決策的結(jié)果。 決策的策略：決策樹(shù)根，如果a1,a2,an存在一棵二分檢索樹(shù)，ak是該樹(shù)的根，則內(nèi)結(jié)點(diǎn)a1,a2,ak-1和外部結(jié)點(diǎn)E0,E1,Ek-1將位于根ak的左子樹(shù)中，而其余的結(jié)點(diǎn)將位于右子樹(shù)中。,40,定義,含義： 左、右子樹(shù)的預(yù)期成本左、右子樹(shù)的根處于第一級(jí) 左、右子樹(shù)中所有結(jié)點(diǎn)的級(jí)數(shù)相對(duì)于子樹(shù)的根測(cè)定，而相對(duì)于原樹(shù)的根少1,41,定義,記： 則，原二分檢索樹(shù)的預(yù)期成本可表示為： COST(T)=P(k)+COST(L)+COST(R)+W(0,k-1)+W(k,n) 最優(yōu)二分檢索樹(shù)：COST(T)有最小值 最優(yōu)性原理成立 若T最優(yōu)二分檢索樹(shù)，則COST(L)和COST(R)將分別是包含a1,a2,ak-1和E0,E1,Ek-1、及ak1, ak+2, ,an和Ek,Ek+1,En的最優(yōu)二分檢索(子)樹(shù)。 記由ai+1,ai+2,aj和Ei,Ei+!,Ej構(gòu)成的二分檢索樹(shù)的成本為C(i,j)，則對(duì)于最優(yōu)二分檢索樹(shù)T有， COST(L) = C(0,k-1) COST(R) = C(k,n),42,定義,則， 對(duì)任何C(i,j)有， 向前遞推過(guò)程： 首先計(jì)算所有j-i=1的C(i,j) 然后依次計(jì)算j-i=2,3,n的C(i,j)。 C(0,n)=最優(yōu)二分檢索樹(shù)的成本。 初始值 C(i,i) = 0 W(i,i) = Q(i)，0in,43,用動(dòng)態(tài)歸劃求最優(yōu)二分檢索樹(shù),首先計(jì)算所有使得j-i=1的C(i,j) 接著計(jì)算所有使得j-i=2的C(i,j) . 如果在這一計(jì)算期間，記下每棵Tij樹(shù)的根R(i,j),那么最優(yōu)二分檢索樹(shù)就可以由這些R(i,j)構(gòu)造出來(lái)。,44,用動(dòng)態(tài)歸劃求最優(yōu)二分檢索樹(shù),例4.10 設(shè)n=4,且(a1,a2,a3,a4)=(do,if,read,while)。 設(shè)P(1:4) = (3,3,1,1)，Q(0:4) = (2,3,1,1,1) (概率值“擴(kuò)大”了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階段的計(jì)算： 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,用動(dòng)態(tài)歸劃求最優(yōu)二分檢索樹(shù),W, C, R計(jì)算結(jié)果 則，C(0,4)=32 二分檢索樹(shù)： T04=2 =T01(左子樹(shù)），T24(右子樹(shù)） T01=1 =T00(左子樹(shù)），T11(右子樹(shù)） T24=3 =T22(左子樹(shù)），T34(右子樹(shù)）,j,i,46,用動(dòng)態(tài)歸劃求最優(yōu)二分檢索樹(shù),樹(shù)的形態(tài),47,算法描述,procedure OBST(P,Q,n) /給定n個(gè)標(biāo)識(shí)符a1a2an。已知成功檢索的概率P(i),不成功檢索概率Q(i), 0in。算法對(duì)于標(biāo)識(shí)符ai+1,aj計(jì)算最優(yōu)二分檢索樹(shù)Tij的成本C(i,j)、根 R(i,j)、權(quán)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 /含有一個(gè)結(jié)點(diǎn)的最優(yōu)樹(shù)/ (W(n,n), R(n,n), C(n,n)(Q(n),0,0) for m2 to n do /找有m個(gè)結(jié)點(diǎn)的最優(yōu)樹(shù)/ for i0 to n-m do ji+m W(i,j) W(i,j-1)+P(j)+Q(j) k區(qū)間R(i,j-1), R(i+1,j)中使C(i,l-1)+C(l,j)取最小值的l值 /Knuth結(jié)論/ C(i,j) W(i,j)+C(i,k-1)+C(k,j) R(i,j)k repeat repeat end OBST,48,計(jì)算時(shí)間, 當(dāng)j-i=m時(shí)，有n-m+1個(gè)C(i,j)要計(jì)算 C(i,j)的計(jì)算：(m) 每個(gè)C(i,j)要求找出m個(gè)量中的最小值。 則，n-m+1個(gè)C(i,j)的計(jì)算時(shí)間： (nm-m2) 對(duì)所有可能的m，總計(jì)算時(shí)間為：,49,4.5 0/1背包問(wèn)題,問(wèn)題描述,背包問(wèn)題中的xj限定只能取0或1值，用KNAP(1,j,X)來(lái)表示這個(gè)問(wèn)題,效益值,背包容量,則0/1背包問(wèn)題就是KNAP(1,n,M),50,0/1背包問(wèn)題最優(yōu)化原理證明,若y1,y2,yn是最優(yōu)解，則y2,y3,yn將是是0/1 背包問(wèn)題的子問(wèn)題,的最優(yōu)解。因?yàn)?，若y2 , y3 , yn 是子問(wèn)題的最優(yōu)解，且使得,51,0/1背包問(wèn)題最優(yōu)化原理證明,則y1, y2 , y3 , yn 將是原問(wèn)題的可行解，并且使得,這與假設(shè)y1,y2,yn是最優(yōu)解相矛盾。 因此，0/1 背包問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)得以證明，可以用動(dòng)態(tài)規(guī)劃的方法求最優(yōu)解。,52,0/1背包問(wèn)題-解決方法,根據(jù)問(wèn)題描述，可通過(guò)作出變量x1,x2,xn的一個(gè)決策序列來(lái)得到它的解。 假定決策x的次序?yàn)閤1,x2,xn 則在對(duì)x1作出決策后，問(wèn)題處于下列兩種狀態(tài)： X1=0, 背包的剩余容量為M，沒(méi)有產(chǎn)生任何效益 X1=1, 背包剩余容量為M-w1，效益值增加了p1 顯然，剩下來(lái)對(duì)x2,xn的決策相對(duì)于決策了x1后所產(chǎn)生的問(wèn)題狀態(tài)應(yīng)該是最優(yōu)的，否則， x1,x2,xn就不可能是最優(yōu)的決策序列。,53,0/1背包問(wèn)題解決方法,設(shè)fj(X)是KNAP(1,j,X)最優(yōu)解的值 則fn(M) (KNAP(1,n,M)可表示為： fn(M) = max fn-1(M) , fn-1(M-wn)+pn 則對(duì)于任意的fi(X) (KNAP(1,i,X)可表示公式4.14為： fi(X) = max fi-1(X) , fi-1(X-wi)+pi 為了能由前向后遞推而最后求解出fn(M),須從f0(X)開(kāi)始 對(duì)于所有的X0，有f0(X)=0；當(dāng)X0時(shí)，有f0(X)= - 根據(jù)遞推關(guān)系式，馬上可求出0Xw1和Xw1情況下的f1(X)的值,54,0/1背包問(wèn)題實(shí)例,例：n=3, (w1,w2,w3)=(2,3,4) , (p1,p2,p3)=(1,2,5) , M=6。 利用公式4.14遞推求解如下： 當(dāng)X0時(shí), f0(X) = -;當(dāng)X 0時(shí), 有f0(X)= 0 當(dāng)X0時(shí), f1(X) = - 當(dāng)0X2時(shí), f1(X) = maxf0(X) , f0(X-2)+1 =max0, -+1=0 當(dāng)X2時(shí), f1(X) = maxf0(X) , f0(X-2)+1 =max0, 0+1=1,55,0/1背包問(wèn)題實(shí)例,當(dāng)X0 時(shí), f2(X) = - 當(dāng)0X2時(shí), f2(X) = maxf1(X) , f1(X-3)+2 = max 0 , -+2 =0 當(dāng)2X3 時(shí), f2(X) = maxf1(X) , f1(X-3)+2 = max 1 , -+2 = 1 當(dāng)3X5 時(shí), f2(X) = maxf1(X) , f1(X-3)+2 =max 1 , 0+2 =2 當(dāng) 5X 時(shí), 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背包問(wèn)題實(shí)例,當(dāng)X0 時(shí), f3(X) = - 當(dāng)0X2 時(shí), f3(X) = maxf2(X),f2(X-4)+5= max0, - +5= 0 當(dāng)2X3 時(shí), f3(X) = maxf2(X),f2(X-4)+5= max1, - +5= 1 當(dāng)3X4 時(shí), f3(X) =maxf2(X),f2(X-4)+5=max2, - + 5 = 2 當(dāng)4X5 時(shí), f3(X) =maxf2(X) , f2(X-4)+5=max2 , 0 + 5 = 5 當(dāng)5X6 時(shí), f3(X) =maxf2(X) , f2(X-4)+5=max3 , 0 + 5 = 5 當(dāng)6X7 時(shí), f3(X) =maxf2(X) , f2(X-4)+5=max3 , 1 + 5 = 6 當(dāng)7X9 時(shí), f3(X) =maxf2(X) , f2(X-4)+5=max3 , 2 + 5 = 7 當(dāng)9X 時(shí), 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背包問(wèn)題實(shí)例,58,0/1背包問(wèn)題算法,procedure DynamicKnapsack(p,w,n,M,f) /二維數(shù)組f(1:n,1:M)的定義與fj(X) 相同 for i 0 to M do f(0,i) 0; repeat for i 0 to n do f(i,0) 0; repeat for 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背包問(wèn)題實(shí)例,可通過(guò)檢測(cè)fi的取值情況可以確定獲得最優(yōu)解的最優(yōu)決策序列 f3(M)=6是在X3=1的情況下取得的，因此X3=1 f3(M)-p3=1，f2(X)和f1(X)都可取1，則x2=0 f0不能取值1，故x1=1 于是最優(yōu)決策序列為(x1,x2,x3)=(1,0,1) 也可通過(guò)圖解法得到 fi-1(X-wi)+pi的圖像可由fi-1(X)在x軸上右移wi個(gè)單位，然后上移pi個(gè)單位得到 fi(X)的圖像由fi-1(X)和fi-1(X-wi)+pi 的函數(shù)曲線按X相同時(shí)取最大值的規(guī)則歸并而成,60,0/1背包問(wèn)題實(shí)例圖解法,fi-1(X-wi)+pi,fi(X),i=0:函數(shù)不存在,f0(X),i=1: f0(X-2)+1,f1(X),當(dāng)X0時(shí), f0(X) = -;當(dāng)X 0時(shí), 有f0(X)= 0 當(dāng)X0時(shí), f1(X) = - 當(dāng)0X2時(shí), f1(X) = maxf0(X) , f0(X-2)+1 =max0, -+1=0 當(dāng)X2時(shí), f1(X) = maxf0(X) , f0(X-2)+1 =max0, 0+1=1,61,i=2: f1(X-3)+2,f2(X),f1(X),當(dāng)X0 時(shí), f2(X) = - 當(dāng)0X2時(shí), f2(X) = maxf1(X) , f1(X-3)+2 = max 0 , -+2 =0 當(dāng)2X3 時(shí), f2(X) = maxf1(X) , f1(X-3)+2 = max 1 , -+2 = 1 當(dāng)3X5 時(shí), f2(X) = maxf1(X) , f1(X-3)+2 =max 1 , 0+2 =2 當(dāng) 5X 時(shí), f2(X) = maxf1(X) , f1(X-3)+2 = max 1 , 1+2 =3,62,i=3:f2(x-4)+5,f3(X),當(dāng)X0 時(shí), f3(X) = - 當(dāng)0X2 時(shí), f3(X) = maxf2(X), f2(X-4)+5= max0, - +5= 0 當(dāng)2X3 時(shí), f3(X) = maxf2(X), f2(X-4)+5= max1, - +5= 1 當(dāng)3X4 時(shí), f3(X) =maxf2(X), f2(X-4)+5=max2, - + 5 = 2 當(dāng)4X5 時(shí), f3(X) =maxf2(X) , f2(X-4)+5=max2 , 0 + 5 = 5 當(dāng)5X6 時(shí), f3(X) =maxf2(X) , f2(X-4)+5=max3 , 0 + 5 = 5 當(dāng)6X7 時(shí), f3(X) =maxf2(X) , f2(X-4)+5=max3 , 1 + 5 = 6 當(dāng)7X9 時(shí), f3(X) =maxf2(X) , f2(X-4)+5=max3 , 2 + 5 = 7 當(dāng)9X 時(shí), f3(X) =maxf2(X) , f2(X-4)+5=max3 , 3 + 5 = 8,63,0/1背包問(wèn)題實(shí)例圖解法,由圖可看出以下幾點(diǎn)： 每一個(gè)fi 完全由一些序偶(Pj,Wj)組成的集合所說(shuō)明，其中Wj是使fi 在其處產(chǎn)生一次階躍的X值，Pj=fi(Wi)。 第一對(duì)序偶(P0,W0)=(0,0) 如果有r次階躍，就還要知道r對(duì)序偶(Pj,Wj), 1jr r對(duì)序偶中，假定WjWj+1，由公式4.14可得PjPj+1 設(shè)Si-1表示fi-1的所有序偶的集合 Si1表示fi-1(X-wi)+pi 的所有序偶的集合。把( pi , wi ) 加到Si-1中, 每一對(duì)序偶就得到Si1,64,0/1背包問(wèn)題實(shí)例,支配規(guī)則 由于取fi-1(X)和fi-1(X-wi)+pi的最大值，也就是將 Si-1 和 Si1 歸并成 Si 如果 Si-1 和 Si1中一個(gè)有序偶(Pj,Wj)，另一個(gè)有序偶(Pk,Wk)，并且在WjWk的同時(shí)有PjPk，那么，序偶(Pj,Wj)被放棄。 也就是遞推關(guān)系式中求最大值的運(yùn)算 fi(Wj)=max(Pj,Pk)=Pk,65,0/1背包問(wèn)題實(shí)例,例：n=3, (p1,p2,p3)=(1,2,5) ,(w1,w2,w3)=(2,3,4), M=6 S0=(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) 根據(jù)支配規(guī)則，在S3中刪去了序偶(3,5),66,Si的推導(dǎo)過(guò)程,在用直接枚舉法求解0/1背包問(wèn)題時(shí)，由于每個(gè)xi的取值只能為0或1，因此x1,x2,xn有2n個(gè)不同的0、1值序列。 對(duì)于每一個(gè)序列，若把 wlxl 記為Wj， plxl 記為Pj，則此序列產(chǎn)生一對(duì)與之對(duì)應(yīng)的序偶(Pj,Wj) 在這2n個(gè)序偶中，滿足WjM，且使Pj取最大值的序偶就是背包問(wèn)題的最優(yōu)解。 在用動(dòng)態(tài)規(guī)劃的向后處理法求解時(shí)，Si-1表示的就是由x1,x2,xi-1的2i-1個(gè)決策序列中一些可能的序列所產(chǎn)生的序偶(Pj,Wj)。,67,Si的推導(dǎo)過(guò)程,若已知Si-1 ，則求 Si 可有下述步驟得到： 在xi=0的情況下，產(chǎn)生的序偶集與Si-1相同 在xi=1的情況下，產(chǎn)生的序偶集是將(pi,wi)加到Si-1的每一對(duì)序偶(Pj,Wj)得到的，也就是Si1 再根據(jù)支配規(guī)則將Si-1和Si1歸并在一起就得到Si 此外，在生成序偶集Si同時(shí)，還應(yīng)將WM的那些序偶(Pj,Wj)除掉。,68,最優(yōu)解序列的確定,這樣生成的Si的所有序偶是背包問(wèn)題KNAP(1,i,X)在0XM各種情況下的最優(yōu)解。 KNAP(1,n,M)的最優(yōu)解fn(M)由Sn的最后一對(duì)序偶的P值給出。 如果已找到 Sn 的最末序偶(Pl,Wl),那么，使pixi=Pl, wixi=Wl 的x1,xn的決策值可以通過(guò)檢索這些 Si 來(lái)確定。 若(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,最優(yōu)解序列的確定,例：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 , 又因?yàn)?1,2) S1 ,于是x2=0。 (1,2) S0 , (1-p1,2-w1)=(0,0)S0，所以x1=1。 f3(6)=6的最優(yōu)決策序列是(x1,x2,x3)=(1,0,1),70,0/1背包問(wèn)題DKP算法,procedure DKP(p,w,n,M) S0(0,0) for i1 to n-1 do Si1(Pl,Wl)|(Pl-pi,Wl-wi) Si-1 and WlM SiMERGE_PURGE(Si-1,Si1) repeat (PX,WX) Sn-1的最末序偶 (PY,WY) (Pl+pn,Wl+wn)其中，Wl 是Sn-1中使得W+wnM的所有序偶中取最大值的W if PXPY then xn0 /PX是Sn的最末序偶/ xn1 /PY是Sn的最末序偶/ endif 回溯確定xn-1,x1 End DKP,初始值,利用支配規(guī)則生成Si的序偶集合,確定最優(yōu)解序列,確定xi取0還是1,71,4.6 可靠性設(shè)計(jì),假定要設(shè)計(jì)一個(gè)系統(tǒng),這個(gè)系統(tǒng)由若干個(gè)以串聯(lián)方式連接在一起的不同設(shè)備所組成。設(shè)ri是設(shè)備Di的可靠性（正常運(yùn)轉(zhuǎn)的概率），則整個(gè)系統(tǒng)的可靠性就是 若第i級(jí)的設(shè)備Di的臺(tái)數(shù)為mi,則這mi臺(tái)設(shè)備同時(shí)出現(xiàn)故障的概率為(1-ri)mi，從而第i級(jí)的可靠性就變成1- (1-ri)mi。,72,可靠性設(shè)計(jì)(1),假設(shè)第i級(jí)的可靠性由函數(shù)i(mi)給定 ，這個(gè)多級(jí)系統(tǒng)的可靠性是 假設(shè)Cj 是一臺(tái)設(shè)備j的成本，由于系統(tǒng)中每種設(shè)備至少有一臺(tái)，故設(shè)備j允許配置的臺(tái)數(shù)至多為,73,可靠性設(shè)計(jì)(2),如果RELI(1,i,X)表示在可容許成本X約束下，對(duì)第1種到第i種設(shè)備的可靠性設(shè)計(jì)問(wèn)題，它的形式描述為 極大化 約束條件,74,可靠性設(shè)計(jì)(3),于是整個(gè)系統(tǒng)的可靠性設(shè)計(jì)問(wèn)題可用RELI(1,n,c)表示。它的一個(gè)最優(yōu)解是對(duì)m1,mn的一系列決策的結(jié)果。每得到一個(gè)mi都要對(duì)其取值進(jìn)行一次決策。 設(shè)fi(X)是在容許成本值X約束下對(duì)前i種設(shè)備組成的子系統(tǒng)可靠性設(shè)計(jì)的最優(yōu)值。,75,可靠性設(shè)計(jì)(4),于是最優(yōu)解的可靠性是fn(c). 一般性況：,76,4.7 貨郎擔(dān)問(wèn)題,問(wèn)題描述： 某售貨員要到若干個(gè)村莊售貨，各村莊之間的路程是己知的，為了提高效率，售貨員決定從所在商店出發(fā)，到每個(gè)村莊售一次貨然后返回商店，問(wèn)他應(yīng)選擇一條什么路線才能使所走的總路程最短? 設(shè)G(V,E)是一個(gè)具有邊成本cij的有向圖。G的一條周游路線是包含V中每個(gè)結(jié)點(diǎn)的一個(gè)有向環(huán)。 周游路線的成本是此路線上所有邊的成本之和，貨郎擔(dān)問(wèn)題(traveling salesperson problem)是求取具有最小成本的周游路線問(wèn)題。,77,貨郎擔(dān)問(wèn)題實(shí)例,郵路問(wèn)題 在一條裝配線上用一個(gè)機(jī)械手取緊固待裝配部件上的螺帽問(wèn)題 產(chǎn)品的生產(chǎn)安排問(wèn)題 ,78,是否能用動(dòng)態(tài)規(guī)劃解決,假設(shè)周游路線是開(kāi)始于結(jié)點(diǎn)1并終止于結(jié)點(diǎn)1的一條簡(jiǎn)單路徑。 每一條周游路線都由一條邊和一條由結(jié)點(diǎn)k到結(jié)點(diǎn)1的路徑所組成，其中kV-1; 而這條由結(jié)點(diǎn)k到結(jié)點(diǎn)1的路徑通過(guò)V-1,k的每個(gè)結(jié)點(diǎn)各一次。 容易看出，如果這條周游路線是最優(yōu)的，那么這條由k到1的路徑必定是通過(guò)V-1,k中所有結(jié)點(diǎn)的由k到1的最短路徑，因此最優(yōu)性原理成立。,79,動(dòng)態(tài)規(guī)劃的解決方法,假設(shè)g(i,S)是由結(jié)點(diǎn)i開(kāi)始，通過(guò)S中的所有結(jié)點(diǎn)，在結(jié)點(diǎn)1終止的一條最段路徑長(zhǎng)度。 g(1,V-1)是一條最優(yōu)的周游路線長(zhǎng)度。于是可以得到：,k,80,貨郎擔(dān)問(wèn)題實(shí)例,10,5,9,15,6,10,8,13,20,8,12,9,81,貨郎擔(dān)問(wèn)題實(shí)例,g(2,)=c21=5 , g(3,)=c31=6 , g(4,)=c41=8 g(2,3)=c23 + g(3,) = 9+6 =15 （結(jié)點(diǎn)2經(jīng)過(guò)結(jié)點(diǎn)3到結(jié)點(diǎn)1的路線長(zhǎng)度） g(2,4