計(jì)算機(jī)算法設(shè)計(jì)與分析課件：第四章 動(dòng)態(tài)規(guī)劃

1、第四章 動(dòng)態(tài)規(guī)劃 4.1 一般方法 一、面向的問題類：多階段決策過程。 多階段決策過程：活動(dòng)的過程可以分為若干個(gè)階段，而且在任一階段后的行為都僅依賴于該階段的過程狀態(tài)，而與該階段之前的過程如何達(dá)到這種狀態(tài)的方式無關(guān)。 二、目標(biāo)：獲得問題最優(yōu)解的決策序列，即最優(yōu)決策序列。 在多階段決策的每一階段，都可能有多種可供選擇的決策，必須從中選取一種決策。一旦各個(gè)階段的決策選定之后，就構(gòu)成了解決這一問題的一個(gè)決策序列。決策序列不同，所導(dǎo)致的問題的結(jié)果也不同。動(dòng)態(tài)規(guī)劃的目標(biāo)就是要在所有容許選擇的決策序列中選取一個(gè)會(huì)獲得問題最優(yōu)解的決策序列，即最優(yōu)決策序列。 三、方法： 窮舉笨。 貪心太嚴(yán)格。它要求每一決策步

2、上都能得到局部最優(yōu)解。（有時(shí)不能僅從局部信息獲得最優(yōu)判定序列） 動(dòng)態(tài)規(guī)劃每一步上列出各種可能的局部解，然后按某些條件放棄哪些不能得到最優(yōu)解的局部解。 四、依據(jù)：最優(yōu)性原理 最優(yōu)性原理：過程的最優(yōu)決策序列具有如下性質(zhì)：無論過程的初始狀態(tài)和初始決策是什么，其余的決策必須相對(duì)于初始決策所產(chǎn)生的狀態(tài)構(gòu)成一個(gè)最優(yōu)決策序列。 五、實(shí)現(xiàn)：獲取各階段間的遞推關(guān)系。 利用動(dòng)態(tài)規(guī)劃方法解決問題的三個(gè)重要步驟： 建立解決問題的多階段決策模型 證明滿足最優(yōu)性原理 獲取各階段間的遞推關(guān)系 獲取遞推關(guān)系式可以采用向前處理或向后處理法 向前處理法：從最后階段開始，以逐步向前遞推的方式列出求前一階段決策的遞推關(guān)系式，即根據(jù)x

3、i1，xn的那些最優(yōu)決策序列來列出求取xi決策值的關(guān)系式，就是動(dòng)態(tài)規(guī)劃的向前處理法。列出關(guān)系式后，由最后階段開始，回溯求解這些關(guān)系式得出最優(yōu)決策序列。 向后處理法：由前向后遞推求解，從而得出最優(yōu)決策序列。就是根據(jù)x1，xi1的那些最優(yōu)決策序列列出求xi的遞推關(guān)系式。 無論是使用向前處理還是向后處理法，都將所有子問題的最優(yōu)解保存下來。 4.2 多段圖問題一、問題描述及多段圖例 p124多段圖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

4、 ，則v Vi+1 ,1ik,且每條邊均附有成本c(u, v)。從s到t的一條路徑成本是這條路徑上邊的成本和。多段圖問題是求由s到t的最小成本路徑。 2345876111091s12t97324227111118654356524V1V2V3V4V5二、對(duì)最優(yōu)性原理的滿足性 p124 假設(shè)s,v2,v3,vk-1,t是一條由s到t的最短路徑再假設(shè)從源點(diǎn)s開始，已作出了到結(jié)點(diǎn)V2的決策，因此V2就是初始決策所產(chǎn)生的狀態(tài)如果把V2看成是原問題的一個(gè)子問題的初始狀態(tài)，解決這個(gè)子問題就是找出一條由V2到t的最短路徑這條最短路徑顯然是v2,v3,vk-1,t如果不是，設(shè)v2,q3,qk-1,t由V2到t

5、的更短路徑，則這條路徑肯定比v2,v3,vk-1,t路徑短，這與假設(shè)矛盾，因此最優(yōu)性原理成立。 1s9732V123454227111118V2876654356V31110912t524V4V5三、向前處理法: 從最后階段開始, 逐步向前遞推, 根據(jù)xi+1, xn的那些最優(yōu)決策序列來列出求取xi 決策值的關(guān)系式向前處理階段間遞推關(guān)系式：設(shè)P(i, j)是一條從Vi中的節(jié)點(diǎn)j 到匯點(diǎn)t 的最小成本路徑, COST(i, j)表示這條路徑的成本, 根據(jù)向前處理方法有公式: COST（k,1）=0 COST（i, j）= min c（j, l ）+ COST（i+1, l） 其中: lVi+1

6、, 邊E, c（j, l）表示該邊的成本 對(duì)于k段圖, t是vk，1 , COST（k,1）=0；當(dāng)i=k-1時(shí), 有COST(k-1, j)= c(j, t)+ COST（k,1）可求得, 依次可以通過公式對(duì)所有jVk-2, 計(jì)算COST(k-2, j), 再對(duì)所有的jVk-3, 計(jì)算COST(k-3, j), 依次向前求解, 最后計(jì)算出COST(1, 1)即S點(diǎn)COST值。多段圖向前處理計(jì)算過程COST(4, 9)=c(9,12)=4COST(4,10)=c(10,12)=2COST(4,11)=c(11,12)=51110912t524V4V5876654356V3COST(3,6)=m

7、inc(6,9)+COST(4,9) , c(6,10)+COST(4,10) =min6+4, 5+2=7COST(3,7)=minc(7,9)+COST(4,9) , c(7,10)+COST(4,10) =min4+4, 3+2=5COST(3,8)=minc(8,10)+COST(4,10) , c(8,11)+COST(4,11) =min5+2, 6+5=7COST(i, j)=min c(j, l)+ COST(i+1, l) l Vi+1 , c（j, l）表示該邊的成本1s9732V123454227111118V21110912t524V4V5876654356V3COST

8、(2,2)=minc(2,6)+COST(3,6), c(2,7)+COST(3,7), c(2,8)+COST(3,8)=min4+7, 2+5, 1+7=7COST(3,6)=7COST(3,7)=5COST(3,8)=7COST(2,3)=min2+7,7+5=9COST(2,4)=min11+7=18COST(2,5)=min11+5,8+7=15COST(1,1)=minc(1,2)+COST(2,2), c(1,3)+COST(2,3), c(1,4)+COST(2,4), c(1,5)+COST(2,5)=min9+7,7+9,3+18,2+15=16在計(jì)算每個(gè)COST(i, j

9、)的同時(shí), 記下每個(gè)狀態(tài)(結(jié)點(diǎn)j)所做出的決策(即l 的取值),令D(i, j)= l, 則容易求出這條最小成本的路徑COST(2,2)=minc(2,6)+COST(3,6), c(2,7)+COST(3,7), c(2,8)+COST(3,8) =7COST(1,1)=minc(1,2)+COST(2,2), c(1,3)+COST(2,3), c(1,4)+COST(2,4), c(1,5)+COST(2,5)=16D(1, 1)=2D(2, 2)=7D(2, 3)=6D(2, 4)=8D(2, 5)=8D(3, 6)=10D(3, 7)=10D(3, 8)=10COST(3,6)=mi

10、nc(6,9)+COST(4,9) , c(6,10)+COST(4,10)=71271012最小成本的路徑為:四、向后處理及階段間遞推關(guān)系式設(shè)BP(i, j)是一條從源點(diǎn)s到 Vi中的結(jié)點(diǎn)j的最小成本路徑, BCOST(i, j)表示這條路徑的成本, 根據(jù)向后處理方法有公式: BCOST（1,1）= 0 BCOST（i, j）= minBCOST（i-1, l）+ c（ l , j ） 其中: lVi-1 , 邊E, c（l, j）表示該邊的成本向后處理的計(jì)算過程1s97322345BCOST(j)=minBCOST(l)+ c( l , j) 4227111118876BCOST(2)=c

11、(1,2)=9BCOST(3)=c(1,3)=7BCOST(4)=c(1,4)=3BCOST(5)=c(1,5)=2BCOST(6)=minBCOST(2)+c(2,6), BCOST(3)+c(3,6) = min9+4,7+2=9BCOST(7)=11 BCOST(8)=10D(2)=1D(3)=1D(4)=1D(5)=1D(6)=3D(7)=2D(8)=2D(9)=6D(10)=6D(11)=8BCOST(9)=15 BCOST(10)=14BCOST(11)=16BCOST(12)=16 D(12)=101361012最小成本的路徑為:procedure FGRAPH(E,k,n,P)

12、real COST(n), int D(n-1), P(k), r, j, k, nCOSTn=0for jn-1 to 1 by -1do 尋找結(jié)點(diǎn)r, 滿足E且使c(j,r)+COST(r)值最小 COSTj=c(j,r)+COSTr; Dj=r ; repeatP1 1; Pk nfor j 2 to k-1 do Pj=DPj-1 repeat end FGRAPH 五、 多段圖的向前處理算法為了算法描述的簡(jiǎn)單, 對(duì)結(jié)點(diǎn)進(jìn)行編號(hào), 從V1開始 s 編為1號(hào), 然后V2中的結(jié)點(diǎn)依次編為2,3,4,5號(hào), 按此規(guī)則編下去, 最后V5的結(jié)點(diǎn)t 編為12號(hào), 有了編號(hào)可以將COST, D中表示

13、段數(shù)的第一個(gè)下標(biāo)省略 通過計(jì)算找到一條最小成本的路徑數(shù)組p用來保存最小成本路徑上結(jié)點(diǎn)編程實(shí)現(xiàn)算法時(shí)要先將多段圖用鄰接表表示1s9732234542271111181110912t524876654356鄰接表: 鄰接表是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu), 對(duì)圖中的每個(gè)頂點(diǎn)建立一個(gè)單鏈表, 鏈表中的結(jié)點(diǎn)有3個(gè)域, 分別存儲(chǔ)頂點(diǎn), 邊的成本和下一個(gè)結(jié)點(diǎn)的指針.123456789101112118412212512927334254627182677117886951049310510611k5; n 12;COST12 0;for j 11 to 1 by -1 do COSTj inc(j,r)+COSTr

14、 Dj r repeat P1 1; Pk 12;for j 2 to 4 do Pj DPj-1 repeat1234567891011120123456789101112345112COSTDPCOST(11)=5COST(10)=2COST(9)=4512241212COST(8)=7COST(7)=5COST(6)=7D(8)=10D(7)=10D(6)=10710571010COST(5)=15COST(4)=18COST(3)=9COST(2)=7 D(11)=12 D(10)=12 D(9)=12D(5)=8D(4)=8D(3)=6D(2)=71581897867D(1)=2CO

15、ST(1)=161622710算法的執(zhí)行過程procedure BGRAPH(E,k,n,P)real BCOST(n); int D(n-1), P(k), r, j, k, n;BCOST10;for j 2 to n do 尋找結(jié)點(diǎn)r, 滿足E且使BCOST(r)+c(r, j)值最小 BCOSTj= BCOSTr+c(r, j); Dj=r ; repeatP1 1; Pk nfor j k-1 to 2 do Pj=DPj+1 ;end BGRAPH*向后處理算法多段圖用反鄰接表來存儲(chǔ)多段圖的向后處理算法 七、多段圖的應(yīng)用例：資源分配 4.3 每對(duì)頂點(diǎn)最短路徑一、問題描述二、解決方法

16、 1、以每個(gè)結(jié)點(diǎn)為起始點(diǎn)，n次調(diào)用D-PATH算法 2、多階段決策的直接求解三、動(dòng)態(tài)規(guī)劃方法的步驟 1、多階段決策過程的建立 以路徑的中間結(jié)點(diǎn)條件作為階段劃分的依據(jù)。 體現(xiàn)形式為A (K) i,j:從i到j(luò)中間經(jīng)過點(diǎn)號(hào)不大于k的結(jié)點(diǎn)的最短路徑。（K可以看作是階段的標(biāo)志參數(shù)），遞推產(chǎn)生矩陣序列。(狀態(tài)點(diǎn)及狀態(tài)參數(shù)的表達(dá)) 2、滿足最優(yōu)性原理 3、階段間遞推關(guān)系式 四、算法實(shí)現(xiàn) 若同時(shí)考慮路徑 在3-4語句間加 if costi,j+ then pi,j i else pi,j 0 endif 第9語句改為 if Ai,jAi,k+Ak,j then Ai,j Ai,k+Ak,j pi,j pk,

17、j endif 五、時(shí)間代價(jià) (n3) 4.4 最優(yōu)二分檢索樹 一、問題的提出 二分檢索樹定義生成（種類）性質(zhì)（中序） 檢索檢索代價(jià)平均檢索效率最優(yōu)二分檢索樹定義 二、二分檢索樹代價(jià)的表示形式轉(zhuǎn)化 cost(T)=cost(L)+cost(R)+w(T) 從中看出問題的兩點(diǎn)特性：樹型（根）的確定取決于子樹的選取，滿足最優(yōu)性原理子樹的構(gòu)成仍與原問題同類。 三、解決思路 按結(jié)點(diǎn)數(shù)的遞增順序來確定最優(yōu)樹型結(jié)構(gòu)，將構(gòu)造過程看成一系列決策結(jié)果，構(gòu)成多階段決策過程。 四、多階段決策過程描述 定義狀態(tài)點(diǎn)T(i,j)、狀態(tài)集、狀態(tài)參數(shù)（r(i,j）,t(i,j),c(i,j),w(i,j) 定義階段 (j-i

18、) 階段間遞推關(guān)系: C(i, i)=0, W(i, i)=Q(i), 0in C(i,j)=minC(i, k-1)+C(k, j)+P(k)+W(i, k-1)+W(k, j) =minC(i, k-1)+C(k, j)+W(i, j) 五、算法實(shí)現(xiàn) p136-137 六、例子 4.5 0/1背包問題一、問題描述背包問題中的xj限定只能取0或1值，用KNAP(l,j,X)來表示這個(gè)問題效益值背包容量若對(duì)于有n個(gè)物品，容量為M的背包，則0/1背包問題就可表示為KNAP(1,n,M) 二、問題的分析與解決 問題形式化：KNAP（l,j,X）,原問題： KNAP（1,n,M） 解決： 多階段決策

19、：對(duì)lj作出決策序列 向后： KNAP（1,1,x）， KNAP（1,2,x）， ， KNAP（1,n,x） 向前： KNAP（1,n,x）， KNAP（2,n,x）， ， KNAP（n,n,x） 最優(yōu)性原理： 假設(shè)y1,y2,yn是最優(yōu)解, 若y1=0，則y2,y3,yn 必須是KNAP(2, n, M)的一個(gè)最優(yōu)序列； 若y1=1, 則y2,y3,yn 必須是KNAP(2, n, M-w1)的一個(gè)最優(yōu)序列； 最優(yōu)性原理對(duì)0/1背包問題成立。 階段間遞推關(guān)系 對(duì)于任意的fi(X), i0 有以下公式: f0(X) =0 fi(X) = max fi-1(X) , fi-1(X-wi)+pi

20、三、實(shí)例：p137 例6.11 n=3, (w1,w2,w3)=(2,3,4) , (p1,p2,p3)=(1,2,5) , M=6遞推求解過程如下: f0(X) = - ； X0時(shí), f0(X)= 0 X0時(shí) f1(X) = - X0 f1(X)=maxf0(X) , f0(X-2)+1=max0, - +1=0 ，0X2 f1(X)=maxf0(X) , f0(X-2)+1 =max0, 0+1=1 X2 f2(X) =- X0 f2(X)=maxf1(X) , f1(X-3)+2=max0 , -+2=0 0X2f2(X)=maxf1(X) , f1(X-3)+2=max1 , -+2=

21、1 2X3 f2(X)=maxf1(X) , f1(X-3)+2=max1 , 0+2 =2 3X5 f2(X)=maxf1(X) , f1(X-3)+2=max1 , 1+2 =3 X 5 f3(X)=- X0 f3(X)=maxf2(X), f2(X-4)+5=max0,-+5= 0 0X2 f3(X)=maxf2(X), f2(X-4)+5=max1,-+5= 1 2X3, f3(X)=maxf2(X), f2(X-4)+5=max2,-+5= 2 3X4 f3(X)=maxf2(X), f2(X-4)+5=max2 ,0+5 = 5 4X5 f3(X)=maxf2(X), f2(X-4

22、)+5=max3 ,0+5 = 5 5X6 f3(X)=maxf2(X), f2(X-4)+5=max3 ,1+5 = 6 6X7 f3(X)=maxf2(X), f2(X-4)+5=max3 ,2+5 = 7 7X9 f3(X)=maxf2(X), f2(X-4)+5=max3 ,3+5 = 8 X9 f3(X)=maxf2(X), f2(X-4)+5=max3, 1+5 = 6f2(X)=maxf1(X), f1(X-3)+2=max1, -+2=1f1(X)=maxf0(X), f0(X-2)+1=max0, 0+1=1X3=1X2=0X1=1最優(yōu)決策序列為: (x1,x2,x3)=(1

23、,0,1)通過檢測(cè)fi的取值情況可以確定最優(yōu)決策序列四、解的圖示表達(dá)圖解法實(shí)例fi-1(X-wi)+pifi(X)i=0: 函數(shù)不存在f0(X)=0i=1: f0(X-2)+1f1(X)f0(X) =- X00 X0f1(X) =- X0 max0, 0+1=1 X2max0,-+1=0 0X2 1 2 3 4 5 6 2 1 1 2 3 4 5 6 2 1 1 2 3 4 5 6 2 1 n=3, (w1,w2,w3)=(2,3,4) , (p1,p2,p3)=(1,2,5) , M=6f2(X) =- X0 max1,1+2=3 X5max1,0+2=2 3X50 0X21 2X3f1(X

24、) 1 2 3 4 5 6 2 1 1 2 3 4 5 6 3 2 1i=2: f1(X-3)+2f2(X) 1 2 3 4 5 6 3 2 1- X0 max0, -+5= 0 0X2 max1, -+5= 1 2X3 max2, -+5 = 2 3X4 max2 , 0 + 5 = 5 4X5 max3 , 0 + 5 = 5 5X6 max3 , 1 + 5 = 6 6X7 max3 , 2 + 5 = 7 7X9 max3 , 3 + 5 = 8 X9 f3(X) = 1 2 3 4 5 6 7 8 9 8 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 9 8 7 6 5

25、 4 3 2 1 1 2 3 4 5 6 3 2 1f2(X)i=3:f2(X-4)+5f3(X)五、解的序偶表示 每一個(gè)fi 完全由一些序偶(Pj,Wj)組成的集合所說明, 其中Wj 是使fi 在其處產(chǎn)生一次階躍的X值，Pj=fi(Wj) 第一對(duì)序偶(P0,W0)=(0,0); 如果有r 次階躍, 就還有r 對(duì)序偶(Pj,Wj), 1jr ; 在r對(duì)序偶中, 假定WjWj+1, 則有PjPj+1 在0jr情況下, 對(duì)所有滿足WjXWj+1的X, 有fi(X)=fi(Wj); 對(duì)所有滿足XWr的X, 有fi(X)=fi(Wr)f2(X) 1 2 3 4 5 6 3 2 1344且3M的那些序偶

26、(P,W)除掉, 因?yàn)樗鼈儾荒軐?dǎo)出滿足約束條件的可行解這樣生成的Si的所有序偶是背包問題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的決策值可通過檢索 Si 來確定再判斷留在Sn-1的序偶(Pl,Wl)或(Pl-pn,Wl-wn)是否屬于Sn-2以確定xn-1的取值。例: S1 =(0,0),(1,2) S2 =(0,0),(1,2),(2,3),(3,5) S3 =(0,0),(1,2),(2,3),(5,4),(6,6)

27、S3的最末序偶(Pl,Wl)=(6,6)若(Pl,Wl)Sn-1，則xn=0;若(Pl,Wl) Sn-1，且(Pl-pn,Wl-wn)Sn-1，則xn=1;(6,6) S2, 并且(6-p3,6-w3)=(1,2) S2 , 所以x3=1再判斷留在S2的序偶(1,2), 因(1,2) S1 , 所以x2=0(1,2) S0 , (1-p1,2-w1)=(0,0)S0，所以x1=1最優(yōu)解fn(M)的最優(yōu)決策序列是(x1,x2,x3)=(1,0,1)例: n=3, (p1,p2,p3)=(1,2,5) ,(w1,w2,w3)=(2,3,4), M=6 S0=(0,0) S11=(1,2)，將S0

28、和S11歸并, 得：S1 =(0,0),(1,2) S21=(2,3),(3,5)，S1 和S21歸并得：S2 =(0,0),(1,2),(2,3),(3,5) S31=(5,4),(6,6),(7,7),(8,9)，S2 和S31歸并, 根據(jù)支配規(guī)則刪去(3,5), 并將WM的那些序偶除掉 得：S3 =(0,0),(1,2),(2,3),(5,4),(6,6)七、 0/1背包問題非形式化的DKP算法procedure DKP(p,w,n,M)S0 =(0,0);for i=1 to n-1 do Si1= (Pl,Wl)|(Pl-pi,Wl-wi) Si-1 and WlM Si = MER

29、GE_PURGE(Si-1,Si1) (PX,WX) = Sn-1的最末序偶(PY,WY) = (Pl+pn,Wl+wn) ; 其中Wl 是Sn-1中使得W+wnM的所有序偶中取最大值的Wlif PXPY then xn=0 /PX是Sn的最末序偶/ else xn=1 /PY是Sn的最末序偶/沿Sn-1, S1回溯確定xn-1,x1的值end DKPS1 =(0,0),(1,2) S2 =(0,0),(1,2),(2,3),(3,5)(PX,WX)=(3,5)(P3,W3) =(5,4) , Wl =2(PY,WY)=(1+5,2+4)=(6,6)(PX=3)(PY=6)所以x3=10/1背

30、包問題DKP算法的實(shí)現(xiàn)可用兩個(gè)一維數(shù)組P和W來存放所有的序偶(Pl ,Wl)序偶集S0,S1,Sn-1互相鄰接的存放各個(gè)集合用指針Fi來指示, 0in, Fi指示S中的第一個(gè)元素所在的位置S0 =(0,0) S1 =(0,0),(1,2)S2 =(0,0),(1,2),(2,3),(3,5)1234567800101230020235 PWF0F1F3F2在生成Si1的過程中, 同時(shí)將Si-1和Si1按支配規(guī)則進(jìn)行歸并而生成Si , 因此不需要附加空間存放Si1在Si-1中序偶是按P和W的遞增次序排列的, 因此Si的序偶也按這種次序生成procedure DKNAP(p,w,n,M,m)F0=

31、1; P1=W1=0; l=h=1; F1=next=2;for i=1 to n-1 do k=l ; u=r ; r是在lrh中,使得Wr+wiM最大 for j=l to u do (pp,ww)=(Pj+pi,Wj+wi) while ( kh and WkPnext-1 ) (Pnext,Wnext)=(pp,ww); next+; while ( kh and PkPnext-1 ) do k+; /end for while kh do (Pnext),Wnext)=(Pk,Wk); next+; k+; l=h+1; h=next-1; Fi+1=next; /end forc

32、all PARTS /算法DKP的611行end DKNAP計(jì)算S1到Sn-1/要加代碼才能實(shí)現(xiàn)/將(pi,wi)加到Si-1中的序偶上/將Si-1中的序偶并入Si中/將Si-1中剩余的序偶并入Si中/ l和h分別指向Si的首端和末端 Fi+1指向Si+1的第一個(gè)元素Si-1和Si1按支配規(guī)則進(jìn)行歸并, 生成Si 八、算法的時(shí)間分析 4.6 可靠性設(shè)計(jì) 一、問題描述 二、問題的形式化表達(dá) 三、問題的動(dòng)態(tài)規(guī)劃求解 四、用序偶法求解4.7 貨郎擔(dān)問題問題描述: 某售貨員要到若干個(gè)村莊售貨, 各村莊之間的路程是己知的, 為了提高效率, 售貨員決定從所在商店出發(fā)，到每個(gè)村莊售貨一次, 然后返回商店,

33、問他應(yīng)選擇一條什么路線才能使所走的總路程最短?設(shè)G(V,E)是一個(gè)具有邊成本cij的有向圖, G的一條周游路線是包含V中每個(gè)結(jié)點(diǎn)的一個(gè)有向環(huán), 周游路線的成本是此路線上所有邊的成本之和。貨郎擔(dān)問題就是求取具有最小成本的周游路線問題。1432156820129913510108假設(shè)周游路線是開始于結(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的路徑通過V-1,k的每個(gè)結(jié)點(diǎn)各一次最優(yōu)性原理對(duì)貨郎擔(dān)問題成立如果這條周游路線是最優(yōu)的, 則這條由k到1的路徑必定是通過V-1,k中所有結(jié)點(diǎn)的由k到1的最短路徑, 因此

34、最優(yōu)性原理成立1432156820129913510108設(shè)g(i,S)是由結(jié)點(diǎn)i開始, 通過S中的所有結(jié)點(diǎn), 在結(jié)點(diǎn)1終止的一條最段路徑長(zhǎng)度2kng(1,V-1)是一條最優(yōu)的周游路線長(zhǎng)度 于是可以得到: g(1,V-1)=minc1k+g(k,V-1,k)jS上式一般化可得: g(i,S)=mincij +g(j,V-j)1234101015202509103613012488901432156820129913510108g(2,)=c21=5 g(3,)=c31=6 g(4,)=c41=8g(2,3)=c23+g(3,)=9+6=15 g(2,4)=c24+g(4,)=10+8=18g(i,S)表示由結(jié)點(diǎn)i經(jīng)過S中所有結(jié)點(diǎn)到結(jié)點(diǎn)1的最短路線長(zhǎng)度g(3,2)=c32+g(2,)=1