算法分析與設計動態(tài)規(guī)劃1.ppt

1、第四章 動態(tài)規(guī)劃,2,第四章 動態(tài)規(guī)劃,什么是動態(tài)規(guī)劃 多段圖 最優(yōu)二分檢索樹 0/1背包問題 可靠性設計 貨郎擔問題,3,在實際生活中，有這么一類問題，它們的活動過程可以分為若干個階段，而且在任一階段后的行為都依賴于i 階段的過程狀態(tài)，而與i 階段之前的過程是如何達到這種狀態(tài)的方式無關，這樣的過程就構成了一個多階段決策過程。 根據(jù)這類問題的多階段決策的特性，提出了解決這類問題的“最優(yōu)性原理”，從而創(chuàng)建了最優(yōu)化問題的一種新的算法設計方法動態(tài)規(guī)劃。,4.1 一般方法,4,在多階段決策過程的每一個階段，都可能有多種選擇的決策，但必須從中選取一種決策。一旦各種階段的決策選定之后，就構成了解決這一問題

2、的一個決策序列。決策序列不同，導致的問題結果也不同。 動態(tài)規(guī)劃的目標就是要在所有容許選擇的決策序列中選取一個會獲得問題最優(yōu)解的決策序列，即最優(yōu)決策序列。,什么是動態(tài)規(guī)劃,5,最優(yōu)性原理,最優(yōu)性原理(Principle of Optimality) 過程的最優(yōu)決策序列具有如下性質：無論過程的初始狀態(tài)和初始決策是什么，其余的決策都必須相對于初始決策所產(chǎn)生的狀態(tài)構成一個最優(yōu)決策序列。 利用動態(tài)規(guī)劃求解問題的前提 1) 證明問題滿足最優(yōu)性原理 如果對所求解問題證明滿足最優(yōu)性原理，則說明用動態(tài)規(guī)劃方法有可能解決該問題 2) 獲得問題狀態(tài)的遞推關系式 獲得各階段間的遞推關系式是解決問題的關鍵。,6,多段圖

3、問題,多段圖問題,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,多段圖問題,最優(yōu)性原理對多段圖成立 假設s,v2,v3,vk-1,t是一條由s到t的最短路徑 再假設從源點s開始，已作出了到結點V2的決策，因此V2就

4、是初始決策所產(chǎn)生的狀態(tài) 如果把V2看成是原問題的一個子問題的初始狀態(tài)，解決這個子問題就是找出一條由V2到t的最短路徑 這條最短路徑顯然是v2,v3,vk-1,t 如果不是，設v2,q3,qk-1,t由V2到t的更短路徑，則這條路徑肯定比v2,v3,vk-1,t路徑短，這與假設矛盾，因此最優(yōu)性原理成立,9,0/1背包問題,背包問題中的xj限定只能取0或1值，用KNAP(1,j,X)來表示這個問題,效益值,背包容量,則0/1背包問題就是KNAP(1,n,M),10,最優(yōu)化決策序列的表示,設S0是問題的初始狀態(tài)。假定要作n次決策xi,1in X1=r1,1,r1,2,r1,pj是x1的可能決策值的集

5、合，而S1,1是在選取決策值r1,j1以后所產(chǎn)生的狀態(tài)， 1j1p1 又設F1,j1是相應于狀態(tài)S1,j1的最優(yōu)決策序列 則相應于S0的最優(yōu)決策序列就是r1,j1 F1,j1 | 1j1p1中最優(yōu)的序列，記作,如果已作了k-1次決策，1k-1n。設x1,xk-1的最優(yōu)決策值是r1,.,rk-1，他們所產(chǎn)生的狀態(tài)為S1,Sk-1,11,最優(yōu)化決策序列的表示,又設Xk=rk,1,rk,2,rk,pk是xk的可能值的集合。 Sk,jk是選取rk,jk決策之后所產(chǎn)生的狀態(tài), 1jkpk Fk,jk 是相應于Sk,jk的最優(yōu)決策序列。 因此，相應于Sk-1的最優(yōu)決策序列是,于是相應于S0的最優(yōu)決策序列為

6、：r1,rk-1, rk , Fk,12,向前處理法(forward approach),從最后階段開始，以逐步向前遞推的方式列出求前一階段決策值的遞推關系式，即根據(jù)xi+1,xn的那些最優(yōu)決策序列來列出求取xi決策值的關系式，這就是動態(tài)規(guī)劃的向前處理法 向后處理方法(backward approach)就是根據(jù)x1,xi-1的那些最優(yōu)決策序列列出求xi的遞推關系式。 多段圖的向前處理和向后處理 0/1背包問題的向前處理和向后處理,13,4.2 多段圖,多段圖向前處理的算法 設P(i, j)是一條從Vi中的節(jié)點j 到匯點t 的最小成本路徑，COST(i, j)表示這條路徑的成本，根據(jù)向前處理方

7、法有公式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段圖的 實現(xiàn)計算步驟： 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+COS

8、T(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段圖的實現(xiàn)計算步驟： 在計算每一個COST(i, j)的同時，記下每個狀態(tài)(結點j)所做出

9、的決策，設為D(i, j)，則可容易地求出這條最小成本路徑。 D(3,6)=10D(3,7)=10D(3,8)=10D(2,2)=7 D(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,n COST(n)0 fo

10、r jn -1 to 1 by 1 do 設r是一個這樣的結點,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,計算出COST(j)的值，并找出一條最小成本路徑,找出最小成本路徑上的第j個結點,19,多段圖的向后處理算法,向后處理方法(backward approach)就是根據(jù)x1,xi-1的那些最優(yōu)決策序列列出求xi的遞推關系式。,20,多段圖的向后處理算法,設BP(i, j)是一條由源點s到Vi中結點j的最

11、小成本路徑，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；,

12、多段圖的向后處理算法,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

13、,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)

14、=minBCOST(4,9)+4,BCOST(4,10)+2, BCOST(4,11)+5=16,12,25,多段圖的向后處理算法,在計算每一個BCOST(i, j)的同時，記下每個狀態(tài)(結點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

15、,k,n,P) real BCOST(n),integer D(n-1),P(k),r,j,k,n BCOST(1)0 for j2 to n do 設r是一個這樣的結點，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,計算出BCOST(j)的值，并找出一條最小成本路徑,找出最小成本路徑上的第j個結點,28,4.3 每對結點之間的最短路徑,復習（略）,29,4.4 最優(yōu)二分檢索樹,問題的描述

16、 1）二分檢索樹定義 二分檢索樹是一棵二元樹，它或者為空，或者其每個結點含有一個可以比較大小的數(shù)據(jù)元素，且有： 的左子樹的所有元素比根結點中的元素小； 的右子樹的所有元素比根結點中的元素大； 的左子樹和右子樹也是二分檢索樹。 注： 二分檢索樹要求樹中所有結點的元素值互異,30,二分檢索樹,對于一個給定的標識符集合，可能有若干棵不同的二分檢索樹:,不同形態(tài)的二分檢索樹對標識符的檢索性能是不同的。,31,二分檢索樹,檢索一棵二分檢索樹算法 procedure SEARCH(T,X,i) i=T while i0 do case :XIDENT(i):i=RCHILD(i) endcase repe

17、at end REARCH,32,最優(yōu)二分檢索樹問題,設給定的標識符集合是a1,a2,an，并假定a1a2 an 。 設，P(i)是對ai檢索的概率，Q(i)是正被檢索的標識符X恰好滿足： ai Xai+1，0in（設a0=-,an+1=+)時的概率，即一種不成功檢索情況下的概率。 則 表示所有成功檢索的概率 表示所有不成功檢索的概率 考慮所有可能的成功和不成功檢索情況，共2n+1種可能的情況，有,33,二分檢索樹,二分檢索樹（如右圖所示） 內結點：代表成功檢索情況，剛好有n個。 外結點：代表不成功檢索情況，剛好有n1個。,34,二分檢索樹的預期成本,預期成本：算法對于所有可能的成功檢索情況和

18、不成功檢索情況，平均所要做的比較次數(shù)。根據(jù)期望值計算方法， 平均檢索成本每種情況出現(xiàn)的概率該情況下所需的比較次數(shù) 平均檢索成本的構成：成功檢索成分不成功檢索成分 成功檢索：在l級內結點終止的成功檢索，需要做l次比較運算（基于二分檢索樹結構）。該級上的任意結點ai的成本檢索的成本分擔額為： P(i)*level(ai) ； 其中，level(ai) = 結點ai 的級數(shù)=l,35,二分檢索樹的預期成本,不成功檢索： 不成功檢索的等價類：每種不成功檢索情況定義了一個等價類，共有n+1個等價類Ei(0in)。其中， E0=X|Xa0 Ei=X|aiXai+1(1in) En=X|Xan 若Ei處于l

19、級，則算法需作l-1次迭代。則，l級上的外部結點的不成功檢索的成本分擔額為： Q(i)*(level(Ei)-1) 則預期總的成本公式表示如下：,36,最優(yōu)二分檢索樹,最優(yōu)二分檢索樹問題： 求一棵使得預期成本最小的二分檢索樹 例4.9 標識符集合（a1,a2,a3）=（do,if,stop）?？赡艿亩謾z索樹如下所示。 成 功 檢 索：3種 不成功情況：4種,37,最優(yōu)二分檢索樹,38,最優(yōu)二分檢索樹,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/

20、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,多階段決策過程,把構造二分檢索樹的過程看成一系列決策的結果。 決策的策略：決策樹根，如果a1,a2,an存在一棵二分檢索樹，ak是該樹的根，則內結點a1,a2,ak-1和外部結點E0,E1,Ek-1將位于根ak的左子樹中，而其余的結點將位于右子樹中。,40,定義,含義： 左、右子樹的預期成

21、本左、右子樹的根處于第一級 左、右子樹中所有結點的級數(shù)相對于子樹的根測定，而相對于原樹的根少1,41,定義,記： 則，原二分檢索樹的預期成本可表示為： COST(T)=P(k)+COST(L)+COST(R)+W(0,k-1)+W(k,n) 最優(yōu)二分檢索樹：COST(T)有最小值 最優(yōu)性原理成立 若T最優(yōu)二分檢索樹，則COST(L)和COST(R)將分別是包含a1,a2,ak-1和E0,E1,Ek-1、及ak1, ak+2, ,an和Ek,Ek+1,En的最優(yōu)二分檢索(子)樹。 記由ai+1,ai+2,aj和Ei,Ei+!,Ej構成的二分檢索樹的成本為C(i,j)，則對于最優(yōu)二分檢索樹T有，

22、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)=最優(yōu)二分檢索樹的成本。 初始值 C(i,i) = 0 W(i,i) = Q(i)，0in,43,用動態(tài)歸劃求最優(yōu)二分檢索樹,首先計算所有使得j-i=1的C(i,j) 接著計算所有使得j-i=2的C(i,j) . 如果在這一計算期間，記下每棵Tij樹的根R(i,j),那么最優(yōu)二分檢索樹就可以由這些R(i,j)構造出來。,44,用動態(tài)歸劃求最優(yōu)二分檢索樹,例4.10 設n

23、=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)

24、= 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,用動態(tài)歸劃求最優(yōu)二分檢索樹,W, C, R計算結果 則，C(0,4)=32 二分檢索樹： T04=2 =T01(左子樹），T24(右子樹） T01=1 =T00(左子樹），T11(右子樹） T24=3 =T22(左子樹），T34(右子樹）,j

25、,i,46,用動態(tài)歸劃求最優(yōu)二分檢索樹,樹的形態(tài),47,算法描述,procedure OBST(P,Q,n) /給定n個標識符a1a2an。已知成功檢索的概率P(i),不成功檢索概率Q(i), 0in。算法對于標識符ai+1,aj計算最優(yōu)二分檢索樹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+

26、1)(Q(i)+Q(i+1)+P(i+1),i+1, Q(i)+Q(i+1)+P(i+1) repeat /含有一個結點的最優(yōu)樹/ (W(n,n), R(n,n), C(n,n)(Q(n),0,0) for m2 to n do /找有m個結點的最優(yōu)樹/ 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結論/ C(i,j) W(i,j)+C(i,k-1)+C(k,j) R(i,j)k repeat repeat end OBST,48,計算時間

27、, 當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背包問題最優(yōu)化原理證明,若y1,y2,yn是最優(yōu)解，則y2,y3,yn將是是0/1 背包問題的子問題,的最優(yōu)解。因為，若y2 , y3 , yn 是子問題的最優(yōu)解，且使得,51,0/1背包問題最

28、優(yōu)化原理證明,則y1, y2 , y3 , yn 將是原問題的可行解，并且使得,這與假設y1,y2,yn是最優(yōu)解相矛盾。 因此，0/1 背包問題具有最優(yōu)子結構性質得以證明，可以用動態(tài)規(guī)劃的方法求最優(yōu)解。,52,0/1背包問題-解決方法,根據(jù)問題描述，可通過作出變量x1,x2,xn的一個決策序列來得到它的解。 假定決策x的次序為x1,x2,xn 則在對x1作出決策后，問題處于下列兩種狀態(tài)： X1=0, 背包的剩余容量為M，沒有產(chǎn)生任何效益 X1=1, 背包剩余容量為M-w1，效益值增加了p1 顯然，剩下來對x2,xn的決策相對于決策了x1后所產(chǎn)生的問題狀態(tài)應該是最優(yōu)的，否則， x1,x2,xn就

29、不可能是最優(yōu)的決策序列。,53,0/1背包問題解決方法,設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 則對于任意的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)= - 根據(jù)遞推關系式，馬上可求出0Xw1和Xw1情況下的f1(X)的值,54,0/1背包問題實例,例：n=3,

30、 (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 時,

31、 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(

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

33、 當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) /二維數(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

34、(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的取值情況可以確定獲得最優(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) 也可通過圖解法得到 fi-1(X-wi)+pi的圖像可由fi-1(X

35、)在x軸上右移wi個單位，然后上移pi個單位得到 fi(X)的圖像由fi-1(X)和fi-1(X-wi)+pi 的函數(shù)曲線按X相同時取最大值的規(guī)則歸并而成,60,0/1背包問題實例圖解法,fi-1(X-wi)+pi,fi(X),i=0:函數(shù)不存在,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,

36、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) = - 當

37、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 ,

38、 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 在其處產(chǎn)生一次階躍的X值，Pj=fi(Wi)。 第一對序偶(P0,W0)=(0,0) 如果有r次階躍，就還要知道r對序偶(Pj,Wj), 1jr r對序偶中，假定WjWj+1，由公式4.14可得PjPj+1 設Si-1表示fi-1的所有序

39、偶的集合 Si1表示fi-1(X-wi)+pi 的所有序偶的集合。把( pi , wi ) 加到Si-1中, 每一對序偶就得到Si1,64,0/1背包問題實例,支配規(guī)則 由于取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)=

40、(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的推導過程,在用直接枚舉法求解0/1背包問題時，由于每個xi的取值只能為0或1，因此

41、x1,x2,xn有2n個不同的0、1值序列。 對于每一個序列，若把 wlxl 記為Wj， plxl 記為Pj，則此序列產(chǎn)生一對與之對應的序偶(Pj,Wj) 在這2n個序偶中，滿足WjM，且使Pj取最大值的序偶就是背包問題的最優(yōu)解。 在用動態(tài)規(guī)劃的向后處理法求解時，Si-1表示的就是由x1,x2,xi-1的2i-1個決策序列中一些可能的序列所產(chǎn)生的序偶(Pj,Wj)。,67,Si的推導過程,若已知Si-1 ，則求 Si 可有下述步驟得到： 在xi=0的情況下，產(chǎn)生的序偶集與Si-1相同 在xi=1的情況下，產(chǎn)生的序偶集是將(pi,wi)加到Si-1的每一對序偶(Pj,Wj)得到的，也就是Si1

42、再根據(jù)支配規(guī)則將Si-1和Si1歸并在一起就得到Si 此外，在生成序偶集Si同時，還應將WM的那些序偶(Pj,Wj)除掉。,68,最優(yōu)解序列的確定,這樣生成的Si的所有序偶是背包問題KNAP(1,i,X)在0XM各種情況下的最優(yōu)解。 KNAP(1,n,M)的最優(yōu)解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

43、)或(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 , 又因為(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背包問題DKP算法,procedure DKP(p,

44、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 可靠性設計,假定要設

45、計一個系統(tǒng),這個系統(tǒng)由若干個以串聯(lián)方式連接在一起的不同設備所組成。設ri是設備Di的可靠性（正常運轉的概率），則整個系統(tǒng)的可靠性就是 若第i級的設備Di的臺數(shù)為mi,則這mi臺設備同時出現(xiàn)故障的概率為(1-ri)mi，從而第i級的可靠性就變成1- (1-ri)mi。,72,可靠性設計(1),假設第i級的可靠性由函數(shù)i(mi)給定，這個多級系統(tǒng)的可靠性是 假設Cj 是一臺設備j的成本，由于系統(tǒng)中每種設備至少有一臺，故設備j允許配置的臺數(shù)至多為,73,可靠性設計(2),如果RELI(1,i,X)表示在可容許成本X約束下，對第1種到第i種設備的可靠性設計問題，它的形式描述為極大化約束條件,74,可靠

46、性設計(3),于是整個系統(tǒng)的可靠性設計問題可用RELI(1,n,c)表示。它的一個最優(yōu)解是對m1,mn的一系列決策的結果。每得到一個mi都要對其取值進行一次決策。 設fi(X)是在容許成本值X約束下對前i種設備組成的子系統(tǒng)可靠性設計的最優(yōu)值。,75,可靠性設計(4),于是最優(yōu)解的可靠性是fn(c).一般性況：,76,4.7 貨郎擔問題,問題描述： 某售貨員要到若干個村莊售貨，各村莊之間的路程是己知的，為了提高效率，售貨員決定從所在商店出發(fā)，到每個村莊售一次貨然后返回商店，問他應選擇一條什么路線才能使所走的總路程最短? 設G(V,E)是一個具有邊成本cij的有向圖。G的一條周游路線是包含V中每個

47、結點的一個有向環(huán)。 周游路線的成本是此路線上所有邊的成本之和，貨郎擔問題(traveling salesperson problem)是求取具有最小成本的周游路線問題。,77,貨郎擔問題實例,郵路問題 在一條裝配線上用一個機械手取緊固待裝配部件上的螺帽問題 產(chǎn)品的生產(chǎn)安排問題 ,78,是否能用動態(tài)規(guī)劃解決,假設周游路線是開始于結點1并終止于結點1的一條簡單路徑。 每一條周游路線都由一條邊和一條由結點k到結點1的路徑所組成，其中kV-1; 而這條由結點k到結點1的路徑通過V-1,k的每個結點各一次。 容易看出，如果這條周游路線是最優(yōu)的，那么這條由k到1的路徑必定是通過V-1,k中所有結點的由k到1的最短路徑，因此最優(yōu)性原理成立。,79,動態(tài)規(guī)劃的解決方法,假設g(i,S)是由結點i開始，通過S中的所有結點，在結點1終止的一條最段路徑長度。 g(1,V-1)是一條最優(yōu)的周游路線長度。于是可以得到：,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=8 g(2,3)=c23 + g(3,) = 9+6 =15 （結點2經(jīng)過結點3到結點1的路線長度） g(2,