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

1、算法設(shè)計(jì)與分析,2010-2011學(xué)年 第2學(xué)期,第3章 動(dòng)態(tài)規(guī)劃法,本 章 目 錄,返回,3.1 概 述,3.2 圖問題中的動(dòng)態(tài)規(guī)劃法,3.3 組合問題中的動(dòng)態(tài)規(guī)劃法,3.4 查找問題中的動(dòng)態(tài)規(guī)劃法,3.1 概 述,3.1.2 最優(yōu)化問題,3.1.3 最優(yōu)性原理,3.1.4 動(dòng)態(tài)規(guī)劃法的設(shè)計(jì)思想,返回,3.1.1 動(dòng)態(tài)規(guī)劃法簡介,動(dòng)態(tài)規(guī)劃法與分治法類似，其基本思想也是將待求解的問題分解成若干個(gè)子問題，先求解子問題，然后從這些子問題的解得到原問題的解。,3.1.1 動(dòng)態(tài)規(guī)劃法簡介,與分治法不同的是，適合用動(dòng)態(tài)規(guī)劃求解的問題，經(jīng)分解得到的子問題往往不是互相獨(dú)立的。若用分治法解這類問題，則分解得到

2、的子問題太多，以致于最后解決原問題需要耗費(fèi)指數(shù)時(shí)間。在用分治求解時(shí)，有些子問題被重復(fù)計(jì)算了多次。如果能夠保存已解決的子問題的答案。在需要的時(shí)候再找出已求的答案，就可以避免大量的重復(fù)計(jì)算，從而簡化了算法。為了達(dá)到這個(gè)目的，可以用一個(gè)表來記錄所有已解決的子問題答案。不管該子問題以后是否被用到，只要他被計(jì)算過，就將其結(jié)果填入表中。這就是動(dòng)態(tài)規(guī)劃法的基本思想。,圖中每個(gè)頂點(diǎn)代表一個(gè)城市，兩個(gè)城市間的連線代表道路，連線上的數(shù)值代表道路的長度?，F(xiàn)在，想從城市A到達(dá)城市E，怎樣走路程最短，最短路程的長度是多少?,多階段決策過程最優(yōu)化問題,最短路徑的特性:最短路徑的第k階段通過Xk 點(diǎn)，則這一最短路徑在由Xk

3、 出發(fā)到終點(diǎn)的那一部分路徑，對(duì)于起始點(diǎn)為Xk 到終點(diǎn)的所有可能的路徑來說必定也是路徑最短的.,利用倒推方法求解A到E的最短距離。把從A到E的全過程分成四個(gè)階段，用k表示階段變量，第1階段有一個(gè)初始狀態(tài)A，兩條可供選擇的支路ABl、AB2；第2階段有兩個(gè)初始狀態(tài)B1、B2，B1有三條可供選擇的支路，B2有兩條可供選擇的支路。用dk( xk，xk+1 )表示在第k階段由初始狀態(tài)xk 到下階段的初始狀態(tài)xk+1的路徑距離，F(xiàn)k(xk)表示從第k階段的xk 到終點(diǎn)E的最短距離。,求從A到E的最短路問題Fk(A) ，可以轉(zhuǎn)化為兩個(gè)性質(zhì)完全相同，但規(guī)模較小的問題，即分別從B1、B2到E的最短路問題Fk(B

4、1)和Fk(B2)，這時(shí)有： Fk(A)=mind1(A,B1)+ Fk(B1),d1(A,B2)+ Fk(B2) 同樣， 計(jì)算Fk(B1) ，又可以轉(zhuǎn)化為性質(zhì)完全相同，但規(guī)模更小的問題，即分別從C1、C2、C3到E的最短路問題Fk(C1)、 Fk(C2)和 Fk(C3)，最后，歸結(jié)為Fk(D1)、 Fk(D2)兩個(gè)子問題。由于Fk(D1)、 Fk(D2)是已知的，因此，可以從這兩個(gè)值開始，逆向遞歸計(jì)算出Fk(A)的值。最終，可以得到從A到E的最短路徑。 動(dòng)態(tài)規(guī)劃法就是根據(jù)最優(yōu)性原理，以自底向上的方式從子問題的最優(yōu)解逐步構(gòu)造出整個(gè)問題的最優(yōu)解。（逆向遞歸的方法）,S1：K=4，有： F4(D1

5、)=3，F(xiàn)4(D2)=4，F(xiàn)4(D3)=3 S2: K=3，有： F3(C1)=mind3(C1,D1)+F4(D1),d3(C1,D2)+F4(D2) =min8,10=8 F3(C2)=d3(C2,D1)+F4(D1)=5+3=8 F3(C3)=d3(C3,D3)+F4(D3)=8+3=11 F3(C4)=d3(C4,D3)+F4(D3)=3+3=6 S2: K=2，有： F2(B1)=mind2(B1,C1)+F3(C1),d2(B1,C2)+F3(C2),d2(B1,C3) +F3(C3)=min9,14,14=9 F2(B2)=mind2(B2,c2)+F3(C2),d2(B2,C4

6、)+F3(C4) =min16,10=10 S4：k=1，有： F1( A)=mind1(A,B1)+F2(B1),d1(A,B2)+F2(B2) =min14,13=13 因此由A到E的全過程的最短路徑為 AB2一C4D3E, 最短路程長度為13。,數(shù)塔問題 有形如圖所示的一個(gè)數(shù)塔，從頂部出發(fā)，在每一結(jié)點(diǎn)可以選擇向左走或是向右走，一直走到底層，要求找出一條路徑，使路徑上的數(shù)值和最大。,算法設(shè)計(jì)過程如下： 1.階段劃分： 第一步對(duì)于第五層的數(shù)據(jù)，我們做如下決策： 對(duì)經(jīng)過第四層2的路徑選擇第五層的19， 對(duì)經(jīng)過第四層18的路徑選擇第五層的10， 對(duì)經(jīng)過第四層9的路徑也選擇第五層的10， 對(duì)經(jīng)過第

7、四層5的路徑選擇第五層的16。,以上的決策結(jié)果將五階數(shù)塔問題變?yōu)?階子問題，遞推出第四層與第五層的和為: 21(2+19),28(18+10),19(9+10),21(5+16)。 用同樣的方法還可以將4階數(shù)塔問題,變?yōu)?階數(shù)塔問題。 最后得到的1階數(shù)塔問題，就是整個(gè)問題的最優(yōu)解。,2存儲(chǔ)、求解： 1) 原始信息存儲(chǔ) 原始信息有層數(shù)和數(shù)塔中的數(shù)據(jù)，層數(shù)用一個(gè)整型變量 n 存儲(chǔ)，數(shù)塔中的數(shù)據(jù)用二維數(shù)組data，存儲(chǔ)成如下的下三角陣: 9 12 15 10 6 8 2 18 9 5 19 7 10 4 16,2) 動(dòng)態(tài)規(guī)劃過程存儲(chǔ) 用二維數(shù)組d存儲(chǔ)各階段的決策結(jié)果。二維數(shù)組d的存儲(chǔ)內(nèi)容如下： dn

8、j=datanj j=1,2,n； dij=max(di+1j，di+1j+1)+dataij i=n-1,n-2,1，j=1,2,i； 最后d11存儲(chǔ)的就是問題的結(jié)果。,數(shù)組data 數(shù)組d 9 59 12 15 50 49 10 6 8 38 34 29 2 18 9 5 21 28 19 21 19 7 10 4 16 19 7 10 4 16 數(shù)塔及動(dòng)態(tài)規(guī)劃過程數(shù)據(jù),輸出data11 9 b=d11-data11=59-9=50 b與d21,d22比較,b與d21相等輸出data2112 b=d21-data21=50-12=38 b與d31,d32 比較b與d31相等輸出data31

9、10 b=d31-data31=38-10=28 b與d41,d42 比較b與d42相等輸出data4218 b=d42-data42=28-18=10 b與d52,d53 比較b與d53相等輸出data5310“,3) 最優(yōu)解路徑求解及存儲(chǔ),為了設(shè)計(jì)簡潔的算法，用三維數(shù)組a50503存儲(chǔ)以上確定的三個(gè)數(shù)組的信息。 a50501代替數(shù)組data， a50502代替數(shù)組d, a50503記錄解路徑。,for (i=n-1 ; i=1; i-) for (j=1; jai+1j+12) aij2=aij2+ai+1j2; aij3=0; else aij2=aij2+ai+1j+12; aij3=

10、1; ,cout; j=j+aij3; coutanj1;,返回,最優(yōu)化問題：有n個(gè)輸入，它的解由這n個(gè)輸入的一個(gè)子集組成，這個(gè)子集必須滿足某些事先給定的條件，這些條件稱為約束條件，滿足約束條件的解稱為問題的可行解。滿足約束條件的可行解可能不只一個(gè)，為了衡量這些可行解的優(yōu)劣，事先給出一定的標(biāo)準(zhǔn)，這些標(biāo)準(zhǔn)通常以函數(shù)的形式給出，這些標(biāo)準(zhǔn)函數(shù)稱為目標(biāo)函數(shù)，使目標(biāo)函數(shù)取得極值（極大或極?。┑目尚薪夥Q為最優(yōu)解，這類問題就稱為最優(yōu)化問題。,3.1.2 最優(yōu)化問題,例：付款問題： 超市的自動(dòng)柜員機(jī)（POS機(jī)）要找給顧客數(shù)量最少的現(xiàn)金。 假定POS機(jī)中有n張面值為pi(1in)的貨幣，用集合P=p1, p2,

11、 , pn表示，如果POS機(jī)需支付的現(xiàn)金為A，那么，它必須從P中選取一個(gè)最小子集S，使得,如果用向量X=( x1, x2, , xn)表示S中所選取的貨幣，則 （式3.2）,（式3.1）,那么，POS機(jī)支付的現(xiàn)金必須滿足 （式3.3）,并且 （式3.4）,在付款問題中，集合P是該問題的輸入，滿足式2.1的解稱為可行解，式3.2是解的表現(xiàn)形式，因?yàn)橄蛄縓中有n個(gè)元素，每個(gè)元素的取值為0或1，所以，可以有2n個(gè)不同的向量，所有這些向量的全體構(gòu)成該問題的解空間，式3.3是該問題的約束條件，式3.4是該問題的目標(biāo)函數(shù)，使式3.4取得極小值的解稱為該問題的最優(yōu)解。,返回,3.1.3 最優(yōu)性原理,對(duì)于一個(gè)

12、具有n個(gè)輸入的最優(yōu)化問題，其求解過程往往可以劃分為若干個(gè)階段，每一階段的決策僅依賴于前一階段的狀態(tài)，由決策所采取的動(dòng)作使?fàn)顟B(tài)發(fā)生轉(zhuǎn)移，成為下一階段決策的依據(jù)。從而，一個(gè)決策序列在不斷變化的狀態(tài)中產(chǎn)生。這個(gè)決策序列產(chǎn)生的過程稱為多階段決策過程。,在每一階段的決策中有一個(gè)賴以決策的策略或目標(biāo)，這種策略或目標(biāo)是由問題的性質(zhì)和特點(diǎn)所確定，通常以函數(shù)的形式表示并具有遞推關(guān)系，稱為動(dòng)態(tài)規(guī)劃函數(shù)。,多階段決策過程滿足最優(yōu)性原理（Optimal Principle）：無論決策過程的初始狀態(tài)和初始決策是什么，其余的決策都必須相對(duì)于初始決策所產(chǎn)生的當(dāng)前狀態(tài)，構(gòu)成一個(gè)最優(yōu)決策序列。 如果一個(gè)問題滿足最優(yōu)性原理通常稱

13、此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。,返回,3.1.4 動(dòng)態(tài)規(guī)劃法的設(shè)計(jì)思想,動(dòng)態(tài)規(guī)劃法將待求解問題分解成若干個(gè)相互重疊的子問題，每個(gè)子問題對(duì)應(yīng)決策過程的一個(gè)階段，一般來說，子問題的重疊關(guān)系表現(xiàn)在對(duì)給定問題求解的遞推關(guān)系（也就是動(dòng)態(tài)規(guī)劃函數(shù)）中，將子問題的解求解一次并填入表中，當(dāng)需要再次求解此子問題時(shí)，可以通過查表獲得該子問題的解而不用再次求解，從而避免了大量重復(fù)計(jì)算。,動(dòng)態(tài)規(guī)劃法的求解過程,n=5時(shí)分治法計(jì)算斐波那契數(shù)的過程。,例：計(jì)算斐波那契數(shù)：,動(dòng)態(tài)規(guī)劃法求解斐波那契數(shù)F(9)的填表過程 ：,注意到，計(jì)算F(n)是以計(jì)算它的兩個(gè)重疊子問題 F(n-1)和F(n-2)的形式來表達(dá)的，所以，可以設(shè)計(jì)一

14、張表填入n+1個(gè)F(n)的值。,用動(dòng)態(tài)規(guī)劃法求解的問題具有特征： 能夠分解為相互重疊的若干子問題； 滿足最優(yōu)性原理（也稱最優(yōu)子結(jié)構(gòu)性質(zhì)）：該問題的最優(yōu)解中也包含著其子問題的最優(yōu)解。 （用反證法）分析問題是否滿足最優(yōu)性原理： 先假設(shè)由問題的最優(yōu)解導(dǎo)出的子問題的解不是最優(yōu)的; 然后再證明在這個(gè)假設(shè)下可構(gòu)造出比原問題最優(yōu)解更好的解，從而導(dǎo)致矛盾。,動(dòng)態(tài)規(guī)劃法設(shè)計(jì)算法一般分成三個(gè)階段： （1）分段：將原問題分解為若干個(gè)相互重疊的子問題； （2）分析：分析問題是否滿足最優(yōu)性原理，找出動(dòng)態(tài)規(guī)劃函數(shù)的遞推式； （3）求解：利用遞推式自底向上計(jì)算，實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃過程。 動(dòng)態(tài)規(guī)劃法利用問題的最優(yōu)性原理，以自底向上

15、的方式從子問題的最優(yōu)解逐步構(gòu)造出整個(gè)問題的最優(yōu)解。（逆向遞歸的方法）,返回,3.2 圖問題中的動(dòng)態(tài)規(guī)劃法,3.2.2 TSP問題,3.2.1 多段圖的最短路徑問題,返回,3.2.1 多段圖的最短路徑問題,設(shè)圖G=(V, E)是一個(gè)帶權(quán)有向連通圖，如果把頂點(diǎn)集合V劃分成k個(gè)互不相交的子集Vi（2kn, 1ik），使得E中的任何一條邊(u, v)，必有uVi，vVi+m（1ik, 1i+mk），則稱圖G為多段圖，稱sV1為源點(diǎn)，tVk為終點(diǎn)。多段圖的最短路徑問題是求從源點(diǎn)到終點(diǎn)的最小代價(jià)路徑。,由于多段圖將頂點(diǎn)劃分為k個(gè)互不相交的子集，所以，多段圖劃分為k段，每一段包含頂點(diǎn)的一個(gè)子集。不失一般性，

16、將多段圖的頂點(diǎn)按照段的順序進(jìn)行編號(hào)，同一段內(nèi)頂點(diǎn)的相互順序無關(guān)緊要。假設(shè)圖中的頂點(diǎn)個(gè)數(shù)為n，則源點(diǎn)s的編號(hào)為0，終點(diǎn)t的編號(hào)為n-1，并且，對(duì)圖中的任何一條邊(u, v)，頂點(diǎn)u的編號(hào)小于頂點(diǎn)v的編號(hào)。,設(shè)s, s1, s2, , sp, t是從s到t的一條最短路徑，從源點(diǎn)s開始，設(shè)從s到下一段的頂點(diǎn)s1已經(jīng)求出，則問題轉(zhuǎn)化為求從s1到t的最短路徑，顯然s1, s2, , sp, t一定構(gòu)成一條從s1到t的最短路徑，如若不然，設(shè)s1, r1, r2, , rq, t是一條從s1到t的最短路徑，則s, s1, r1, r2, , rq, t將是一條從s到t的路徑且比s, s1, s2, , sp

17、, t的路徑長度要短，從而導(dǎo)致矛盾。所以，多段圖的最短路徑問題滿足最優(yōu)性原理。,證明多段圖問題滿足最優(yōu)性原理,對(duì)多段圖的邊(u, v)，用cuv表示邊上的權(quán)值，將從源點(diǎn)s到終點(diǎn)t的最短路徑記為d(s, t)，則從源點(diǎn)0到終點(diǎn)9的最短路徑d(0, 9)由下式確定： d(0,9)=minc01+d(1,9),c02+d(2,9),c03+d(3,9) 這是最后一個(gè)階段的決策，它依賴于d(1,9)、d(2,9)和d(3,9)的計(jì)算結(jié)果，而 d(1,9)=minc14+d(4,9), c15+d(5,9) d(2, 9)=minc24+d(4, 9), c25+d(5, 9), c26+d(6, 9)

18、 d(3, 9)=minc35+d(5, 9), c36+d(6, 9) 這一階段的決策又依賴于d(4, 9)、d(5, 9)和d(6, 9)的計(jì)算結(jié)果：,d(4, 9)=minc47+d(7, 9), c48+d(8, 9) d(5, 9)=minc57+d(7, 9), c58+d(8, 9) d(6, 9)=minc67+d(7, 9), c68+d(8, 9) 這一階段的決策依賴于d(7, 9)和d(8, 9)的計(jì)算，而d(7, 9)和d(8, 9)可以直接獲得（括號(hào)中給出了決策產(chǎn)生的狀態(tài)轉(zhuǎn)移）： d(7, 9)=c797(79) d(8, 9)=c893(89) 再向前推導(dǎo)，有： d

19、(6, 9)=minc67+d(7, 9), c68+d(8, 9)=min6+7, 5+3=8(68) d(5, 9)=minc57+d(7, 9), c58+d(8, 9)=min8+7, 6+3=9(58) d(4, 9)=minc47+d(7, 9), c48+d(8, 9)=min5+7, 6+3=9(48),d(3, 9)=minc35+d(5, 9), c36+d(6, 9)=min4+9, 7+8=13(35) d(2, 9)=minc24+d(4, 9), c25+d(5, 9), c26+d(6, 9)=min6+9, 7+9, 8+8=15(24) d(1, 9)=min

20、c14+d(4, 9), c15+d(5, 9)=min9+9, 8+9=17(15) d(0, 9)=minc01+d(1, 9), c02+d(2, 9), c03+d(3, 9)=min4+17, 2+15, 3+13=16(03) 最后，得到最短路徑為03589，長度為16。,S1：K=4，有： F4(D1)=3，F(xiàn)4(D2)=4，F(xiàn)4(D3)=3 S2: K=3，有： F3(C1)=mind3(C1,D1)+F4(D1),d3(C1,D2)+F4(D2) =min8,10=8 F3(C2)=d3(C2,D1)+F4(D1)=5+3=8 F3(C3)=d3(C3,D3)+F4(D3)=

21、8+3=11 F3(C4)=d3(C4,D3)+F4(D3)=3+3=6 S2: K=2，有： F2(B1)=mind2(B1,C1)+F3(C1),d2(B1,C2)+F3(C2),d2(B1,C3) +F3(C3)=min9,14,14=9 F2(B2)=mind2(B2,c2)+F3(C2),d2(B2,C4)+F3(C4) =min16,10=10 S4：k=1，有： F1( A)=mind1(A,B1)+F2(B1),d1(A,B2)+F2(B2) =min14,13=13 因此由A到E的全過程的最短路徑為 AB2一C4D3E, 最短路程長度為13。,多段圖的最短路徑問題的填表形式。

22、 用一個(gè)數(shù)組costn作為存儲(chǔ)子問題解的表格，costi表示從頂點(diǎn)i到終點(diǎn)n-1的最短路徑，數(shù)組pathn存儲(chǔ)狀態(tài)，pathi表示從頂點(diǎn)i到終點(diǎn)n-1的路徑上頂點(diǎn)i的下一個(gè)頂點(diǎn)。則： costi=mincij+costj (ijn且頂點(diǎn)j是頂點(diǎn)i的鄰接點(diǎn)) (式3.5) pathi=使cij+costj最小的j (式3.6）,算法多段圖的最短路徑 1初始化：數(shù)組costn初始化為最大值，數(shù)組pathn初始化為-1； 2for (i=n-2; i=0; i-) 2.1 對(duì)頂點(diǎn)i的每一個(gè)鄰接點(diǎn)j，根據(jù)式2.5計(jì)算costi; 2.2 根據(jù)式2.6計(jì)算pathi; 3輸出最短路徑長度cost0; 4

23、. 輸出最短路徑經(jīng)過的頂點(diǎn)： 4.1 i=0 4.2 循環(huán)直到pathi=n-1 4.2.1 輸出pathi; 4.2.2 i=pathi;,算法主要由三部分組成：第一部分是初始化部分，其時(shí)間性能為O(n)；第二部分是依次計(jì)算各個(gè)頂點(diǎn)到終點(diǎn)的最短路徑，由兩層嵌套的循環(huán)組成，外層循環(huán)執(zhí)行n-1次，內(nèi)層循環(huán)對(duì)所有出邊進(jìn)行計(jì)算，并且在所有循環(huán)中，每條出邊只計(jì)算一次。假定圖的邊數(shù)為m，則這部分的時(shí)間性能是O(m)；第三部分是輸出最短路徑經(jīng)過的頂點(diǎn)，其時(shí)間性能是O(n)。所以，算法6.2的時(shí)間復(fù)雜性為O(n+m)。,返回,3.2.2 TSP問題,TSP問題是指旅行家要旅行n個(gè)城市，要求各個(gè)城市經(jīng)歷且僅經(jīng)

24、歷一次然后回到出發(fā)城市，并要求所走的路程最短。 各個(gè)城市間的距離可以用代價(jià)矩陣來表示。,設(shè)s, s1, s2, , sp, s是從s出發(fā)的一條路徑長度最短的簡單回路，假設(shè)從s到下一個(gè)城市s1已經(jīng)求出，則問題轉(zhuǎn)化為求從s1到s的最短路徑，顯然s1, s2, , sp, s一定構(gòu)成一條從s1到s的最短路徑。 如若不然，設(shè)s1, r1, r2, , rq, s是一條從s1到s的最短路徑且經(jīng)過n-1個(gè)不同城市，則s, s1, r1, r2, , rq, s將是一條從s出發(fā)的路徑長度最短的簡單回路且比s, s1, s2, , sp, s要短，從而導(dǎo)致矛盾。所以，TSP問題滿足最優(yōu)性原理。,證明TSP問題

25、滿足最優(yōu)性原理,假設(shè)從頂點(diǎn)i出發(fā)，令d( i, V )表示從頂點(diǎn)i 出發(fā)經(jīng)過V 中各個(gè)頂點(diǎn)一次且僅一次，最后回到出發(fā)點(diǎn) i 的最短路徑長度，開始時(shí)，V V i ，于是，TSP問題的動(dòng)態(tài)規(guī)劃函數(shù)為： d( i,V )=mincik+d(k,Vk)(kV ) （式3.7） d(k, )=cki(ki) （式3.8）,這是最后一個(gè)階段的決策，而： d(1, 2, 3)=minc12+d(2, 3), c13+ d(3, 2) d(2, 1, 3)=minc21+d(1, 3), c23+ d(3, 1) d(3, 1, 2)=minc31+d(1, 2), c32+ d(2, 1) 這一階段的決策又

26、依賴于下面的計(jì)算結(jié)果： d(1, 2)= c12+d(2, ) d(2, 3)=c23+d(3, ) d(3, 2)= c32+d(2, ) d(1, 3)= c13+d(3, ) d(2, 1)=c21+d(1, ) d(3, 1)=c31+d(1, ),從城市0出發(fā)經(jīng)城市1、2、3然后回到城市0的最短路徑長度是： d(0,1, 2, 3)=minc01+d(1, 2, 3), c02+d(2, 1, 3), c03+d(3, 1, 2),而下式可以直接獲得（括號(hào)中是該決策引起的狀態(tài)轉(zhuǎn)移）： d(1, )=c10=5(10) d(2, )=c20=6(20) d(3, )=c30=3(30)

27、,再向前倒推，有： d(1, 2)= c12+d(2, )=2+6=8(12) d(1, 3)= c13+d(3, )=3+3=6(13) d(2, 3)= c23+d(3, )=2+3=5(23) d(2, 1)= c21+d(1, )=4+5=9(21) d(3, 1)= c31+d(1, )=7+5=12(31) d(3, 2)= c32+d(2, )=5+6=11(32) 再向前倒退，有： d(1, 2, 3)=minc12+d(2, 3), c13+ d(3, 2)=min2+5, 3+11=7(12) d(2, 1, 3)=minc21+d(1, 3), c23+ d(3, 1)=

28、min4+6, 2+12=10(21),d(3, 1, 2)=minc31+d(1, 2), c32+ d(2, 1)=min7+8, 5+9=14(32) 最后有： d(0, 1, 2, 3)=minc01+ d(1, 2, 3), c02+ d(2, 1, 3), c03+ d(3, 1, 2) =min3+7, 6+10, 7+14=10(01) 所以，從頂點(diǎn)0出發(fā)的TSP問題的最短路徑長度為10，路徑是01230。,假設(shè)n個(gè)頂點(diǎn)用0n-1的數(shù)字編號(hào)，首先生成1n-1個(gè)元素的子集存放在數(shù)組V2n-1中，設(shè)數(shù)組dn2n-1存放迭代結(jié)果，其中dij表示從頂點(diǎn)i經(jīng)過子集Vj中的頂點(diǎn)一次且僅一次

29、，最后回到出發(fā)點(diǎn)0的最短路徑長度。,動(dòng)態(tài)規(guī)劃法求解TSP問題的填表過程,算法TSP問題 1for (i=1; in; i+) /初始化第0列 di0=ci0; 2for (j=1; j2n-1-1; j+) for (i=1; in; i+) /依次進(jìn)行第i次迭代 if (子集Vj中不包含i) 對(duì)Vj中的每個(gè)元素k，計(jì)算dij=min(cik+dkj-1); 3對(duì)V2n-1-1中每一個(gè)元素k，計(jì)算d02n-1-1=min(c0k+dk2n-1-2); 4輸出最短路徑長度d02n-1-1;,顯然，算法的時(shí)間復(fù)雜性為O(2n)。和蠻力法相比，動(dòng)態(tài)規(guī)劃法求解TSP問題，把原來的時(shí)間復(fù)雜性是O(n!)

30、的排列問題，轉(zhuǎn)化為組合問題，從而降低了算法的時(shí)間復(fù)雜性，但它仍需要指數(shù)時(shí)間。,設(shè)頂點(diǎn)之間的代價(jià)存放在數(shù)組cnn中，動(dòng)態(tài)規(guī)劃法求解TSP問題的算法如下：,返回,3.3 組合問題中的動(dòng)態(tài)規(guī)劃法,3.3.1 0 / 1背包問題,3.3.2 最長公共子序列問題,返回,3.3.1 0 / 1背包問題,在0/1背包問題中，物品i或者被裝入背包，或者不被裝入背包，設(shè)xi表示物品i裝入背包的情況，則當(dāng)xi=0時(shí)，表示物品i沒有被裝入背包，xi=1時(shí)，表示物品i被裝入背包。根據(jù)問題的要求，有如下約束條件和目標(biāo)函數(shù)：,（式3.9）,（式3.10）,于是，問題歸結(jié)為尋找一個(gè)滿足約束條件式3.9，并使目標(biāo)函數(shù)式3.1

31、0達(dá)到最大的解向量X=(x1, x2, , xn)。,證明0/1背包問題滿足最優(yōu)性原理。 設(shè)(x1, x2, , xn)是所給0/1背包問題的一個(gè)最優(yōu)解，則( x2, , xn)是下面一個(gè)子問題的最優(yōu)解：,如若不然，設(shè)(y2, , yn)是上述子問題的一個(gè)最優(yōu)解，則 因此， 這說明(x1, y2, , yn)是所給0/1背包問題比(x1, x2, , xn)更優(yōu)的解，從而導(dǎo)致矛盾。,0/1背包問題可以看作是決策一個(gè)序列(x1, x2, , xn)，對(duì)任一變量xi的決策是決定xi=1還是xi=0。在對(duì)xi-1決策后，已確定了(x1, , xi-1)，在決策xi時(shí)，問題處于下列兩種狀態(tài)之一： （1

32、）背包容量不足以裝入物品i，則xi=0，背包不增加價(jià)值； （2）背包容量可以裝入物品i，則xi=1，背包的價(jià)值增加了vi 這兩種情況下背包價(jià)值的最大者應(yīng)該是對(duì)xi決策后的背包價(jià)值。,的最優(yōu)值為V(i，j)，即V(i，j)是背包容量為j （1jC） ，可選擇物品為i，i+1，n時(shí)0-1背包問題的最優(yōu)值。由0-1背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計(jì)算V(i，j)的遞歸式（動(dòng)態(tài)規(guī)劃函數(shù)）如下。 V(i, 0)= V(0, j)=0 （式3.11）,（式3.12）,設(shè)所給0-1背包問題的子問題,式3.11表明：把前面i個(gè)物品裝入容量為0的背包和把0個(gè)物品裝入容量為j的背包，得到的價(jià)值均為0。式3.12

33、的第一個(gè)式子表明：如果第i個(gè)物品的重量大于背包的容量，則裝入前i個(gè)物品得到的最大價(jià)值和裝入前i-1個(gè)物品得到的最大價(jià)值是相同的，即物品i不能裝入背包；第二個(gè)式子表明：如果第i個(gè)物品的重量小于背包的容量，則會(huì)有以下兩種情況： （1）如果把第i個(gè)物品裝入背包，則背包中物品的價(jià)值等于把前i-1個(gè)物品裝入容量為j-wi的背包中的價(jià)值加上第i個(gè)物品的價(jià)值vi； （2）如果第i個(gè)物品沒有裝入背包，則背包中物品的價(jià)值就等于把前i-1個(gè)物品裝入容量為j的背包中所取得的價(jià)值。 顯然，取二者中價(jià)值較大者作為把前i個(gè)物品裝入容量為j的背包中的最優(yōu)解。,根據(jù)動(dòng)態(tài)規(guī)劃函數(shù)，用一個(gè)(n+1)(C+1)的二維表V，Vij表

34、示把前i個(gè)物品裝入容量為j的背包中獲得的最大價(jià)值。,例如，有5個(gè)物品，其重量分別是2, 2, 6, 5, 4，價(jià)值分別為 6, 3, 5, 4, 6，背包的容量為10。,按下述方法來劃分階段：第一階段，只裝入前1個(gè)物品，確定在各種情況下的背包能夠得到的最大價(jià)值；第二階段，只裝入前2個(gè)物品，確定在各種情況下的背包能夠得到的最大價(jià)值；依此類推，直到第n個(gè)階段。最后，V(n,C)便是在容量為C的背包中裝入n個(gè)物品時(shí)取得的最大價(jià)值。為了確定裝入背包的具體物品，從V(n,C)的值向前推，如果V(n,C)V(n-1,C)，表明第n個(gè)物品被裝入背包，前n-1個(gè)物品被裝入容量為C-wn的背包中；否則，第n個(gè)物

35、品沒有被裝入背包，前n-1個(gè)物品被裝入容量為C的背包中。依此類推，直到確定第1個(gè)物品是否被裝入背包中為止。由此，得到如下函數(shù)：,（式3.13）,設(shè)n個(gè)物品的重量存儲(chǔ)在數(shù)組wn中，價(jià)值存儲(chǔ)在數(shù)組vn中，背包容量為C，數(shù)組Vn+1C+1存放迭代結(jié)果，其中Vij表示前i個(gè)物品裝入容量為j的背包中獲得的最大價(jià)值，數(shù)組xn存儲(chǔ)裝入背包的物品，動(dòng)態(tài)規(guī)劃法求解0/1背包問題的算法如下：,算法0/1背包問題 int KnapSack(int n, int w , int v ) for (i=0; i0; i-) if (VijVi-1j) xi=1; j=j-wi; else xi=0; return Vn

36、C; /返回背包取得的最大價(jià)值 ,在算法中，第一個(gè)for循環(huán)的時(shí)間性能是O(n)，第二個(gè)for循環(huán)的時(shí)間性能是O(C)，第三個(gè)循環(huán)是兩層嵌套的for循環(huán)，其時(shí)間性能是O(nC)，第四個(gè)for循環(huán)的時(shí)間性能是O(n)，所以，算法6.3的時(shí)間復(fù)雜性為O(nC)。,返回,3.3.2 最長公共子序列問題,對(duì)給定序列X=(x1, x2, xm)和序列Z=(z1, z2, zk)，Z是X的子序列當(dāng)且僅當(dāng)存在一個(gè)嚴(yán)格遞增下標(biāo)序列(i1, i2, ik)，使得對(duì)于所有j=1, 2, , k，有zj=xij（1ijm）。 給定兩個(gè)序列X和Y，當(dāng)另一個(gè)序列Z既是X的子序列又是Y的子序列時(shí)，稱Z是序列X和Y的公共子

37、序列。最長公共子序列問題就是在序列X和Y的公共子序列中查找長度最長的公共子序列。,證明最長公共子序列問題滿足最優(yōu)性原理。 設(shè)序列X=x1, x2, xm和Y=y1, y2, yn的最長公共子序列為Z=z1, z2, zk，記Xk為序列X中前k個(gè)連續(xù)字符組成的子序列，Yk為序列Y中前k個(gè)連續(xù)字符組成的子序列，Zk為序列Z中前k個(gè)連續(xù)字符組成的子序列，顯然有下式成立： （1）若xm=yn，則zk=xm=yn，且Zk-1是Xm-1和Yn-1的最長公共子序列； （2）若xmyn且zkxm，則Z是Xm-1和Y的最長公共子序列； （3）若xmyn且zkyn，則Z是X和Yn-1的最長公共子序列。 可見，兩個(gè)

38、序列的最長公共子序列包含了這兩個(gè)序列的前綴序列的最長公共子序列。,要找出序列X=x1, x2, xm和Y=y1, y2, yn的最長公共子序列，可按下述遞推方式計(jì)算：當(dāng)xm=yn時(shí)，找出Xm-1和Yn-1的最長公共子序列，然后在其尾部加上xm即可得到X和Y的最長公共子序列；當(dāng)xmyn時(shí)，必須求解兩個(gè)子問題：找出Xm-1和Y的最長公共子序列以及Xm和Yn-1的最長公共子序列，這兩個(gè)公共子序列中的較長者即為X和Y的最長公共子序列。用Lij表示子序列Xi和Yj的最長公共子序列的長度，可得如下動(dòng)態(tài)規(guī)劃函數(shù)： L00=Li0=L0j=0(1im,1jn) （式3.14） （式3.15）,由此，把序列X=

39、x1, x2, xm和Y=y1, y2, yn的最長公共子序列的搜索分為m個(gè)階段，第1階段，按照式3.15計(jì)算X1和Yj的最長公共子序列長度L1j（1jn），第2階段，按照式3.15計(jì)算X2和Yj的最長公共子序列長度L2j（1jn），依此類推，最后在第m階段，計(jì)算Xm和Yj的最長公共子序列長度Lmj（1jn），則Lmn就是序列Xm和Yn的最長公共子序列的長度。,為了得到序列Xm和Yn具體的最長公共子序列，設(shè)二維表Sm+1n+1，其中Sij表示在計(jì)算Lij的過程中的搜索狀態(tài)，并且有：,（式3.16）,若Sij=1，表明ai=bj，則下一個(gè)搜索方向是Si-1j-1；若Sij=2，表明aibj且Li

40、j-1Li-1j，則下一個(gè)搜索方向是Sij-1；若Sij=3，表明aibj且Lij-1Li-1j，則下一個(gè)搜索方向是Si-1j。,(a) 長度矩陣L (b) 狀態(tài)矩陣S,例：序列X=(a, b, c, b, d, b)，Y=(a, c, b, b, a, b, d, b, b)，建立兩個(gè)(m+1)(n+1)的二維表L和表S，分別存放搜索過程中得到的子序列的長度和狀態(tài)。,算法最長公共子序列問題 int CommonOrder(int m, int n, int x , int y , int z ) for (j=0; j=Li-1j) Lij=Lij-1; Sij=2; else Lij=Li

41、-1j; Sij=3; i=m; j=n; k=Lmn; for (i0 ,第一個(gè)for循環(huán)的時(shí)間性能是O(n)； 第二個(gè)for循環(huán)的時(shí)間性能是O(m)； 第三個(gè)循環(huán)是兩層嵌套的for循環(huán)，其時(shí)間性能是O(mn)； 第四個(gè)for循環(huán)的時(shí)間性能是O(k)，而kminm, n，所以，算法6.4的時(shí)間復(fù)雜性是O(mn)。,返回,設(shè)r1, r2, , rn是n個(gè)記錄的集合，其查找概率分別是p1, p2, , pn，最優(yōu)二叉查找樹（Optimal Binary Search Trees）是以這n個(gè)記錄構(gòu)成的二叉查找樹中具有最少平均比較次數(shù)的二叉查找樹，即 最小，其中pi是記錄ri的查找概率，ci是在二叉查找樹中查找ri的比較次數(shù)。,最優(yōu)二叉查找樹,3.4 查找問題中的動(dòng)態(tài)規(guī)劃法,返回,例如，集合A, B, C, D的查找概率是0.1, 0.2, 0.4, 0.3， (a)的平均比較次數(shù)是0.110.22+0.43+0.34=2.9， (b)的平均比較次數(shù)是0.120.21+0.42+0.33=2.1， (c)的平均比較次數(shù)是0