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

1、動(dòng)態(tài)規(guī)劃n歷史不會(huì)重演26.1 引言F(n) = 1if n = 0 or 1F(n-1) + F(n-2)if n 1n012345678910F(n)1123581321345589遞歸算法的偽代碼:F(n)1if n=0 or n=1 then return 12else return F(n-1) + F(n-2)n考慮Fibonacci序列F(n)3計(jì)算F(7)F7F6F5F5F4F3F3F2F1F0F2F1F0F1F2F1F0F2F1F0F2F1F0F4F4F3F3F3F2F1F0F2F1F0F2F1F0F1F1F1F14計(jì)算F(7)計(jì)算計(jì)算F(2)重復(fù)8次!F7F6F5F5F4F

2、3F3F2F1F0F2F1F0F1F2F1F0F2F1F0F2F1F0F4F4F3F3F3F2F1F0F2F1F0F2F1F0F1F1F1F15The execution of F(7)計(jì)算計(jì)算 F(3) 重復(fù)重復(fù) 5 次次!F7F6F5F5F4F3F3F2F1F0F2F1F0F1F2F1F0F2F1F0F2F1F0F4F4F3F3F3F2F1F0F2F1F0F2F1F0F1F1F1F16計(jì)算 F(7)多次重復(fù)計(jì)算多次重復(fù)計(jì)算!如何避免如何避免?F7F6F5F5F4F3F3F2F1F0F2F1F0F1F2F1F0F2F1F0F2F1F0F4F4F3F3F3F2F1F0F2F1F0F2F1F0F

3、1F1F1F17改進(jìn)的想法n備忘錄 當(dāng) F1(i)被計(jì)算后,保存它的值 當(dāng)再次計(jì)算F1(i)時(shí),只需要從內(nèi)存中取出即可F1(n)1 if vn 0 then2 vn F1(n-1)+F1(n-2)3 return vnMain()1 v0 = v1 12 for i 2 to n do3 vi = -14 output F1(n)8再計(jì)算F(7)11-1-1-1-1-1-1v0v1v2v3v4v5v6v7F7F6F5F5F4F3F3F2F1F0F2F1F0F1F2F1F0F2F1F0F2F1F0F4F4F3F3F3F2F1F0F2F1F0F2F1F0F1F1F1F1F(i)=Fi9再計(jì)算F(7

4、)11-1-1-1-1-1-1v0v1v2v3v4v5v6v7F7F6F5F5F4F3F3F2F1F0F2F1F0F1F2F1F0F2F1F0F2F1F0F4F4F3F3F3F2F1F0F2F1F0F2F1F0F1F1F1F110再計(jì)算F(7)112-1-1-1-1-1v0v1v2v3v4v5v6v7F7F6F5F5F4F3F3F2F1F0F2F1F0F1F2F1F0F2F1F0F2F1F0F4F4F3F3F3F2F1F0F2F1F0F2F1F0F1F1F1F111再計(jì)算F(7)112-1-1-1-1-1v0v1v2v3v4v5v6v7F7F6F5F5F4F3F3F2F1F0F2F1F0F1F

5、2F1F0F2F1F0F2F1F0F4F4F3F3F3F2F1F0F2F1F0F2F1F0F1F1F1F112再計(jì)算F(7)1123-1-1-1-1v0v1v2v3v4v5v6v7F7F6F5F5F4F3F3F2F1F0F2F1F0F1F2F1F0F2F1F0F2F1F0F4F4F3F3F3F2F1F0F2F1F0F2F1F0F1F1F1F113再計(jì)算F(7)1123-1-1-1-1v0v1v2v3v4v5v6v7F7F6F5F5F4F3F3F2F1F0F2F1F0F1F2F1F0F2F1F0F2F1F0F4F4F3F3F3F2F1F0F2F1F0F2F1F0F1F1F1F114F1F0再計(jì)算

6、F(7)11235-1-1-1v0v1v2v3v4v5v6v7F7F6F5F5F4F3F3F2F1F0F2F1F2F1F0F2F1F0F2F1F0F4F4F3F3F3F2F1F0F2F1F0F2F1F0F1F1F1F115F1F0F2F1F0F1再計(jì)算F(7)11235-1-1-1F7F6F5F5F4F3F3F2F1F0F2F1F2F1F0F2F1F0F4F4F3F3F3F2F1F0F2F1F0F2F1F0F1F1F1v0v1v2v3v4v5v6v716F1F0F2F1F0F1再計(jì)算F(7)112358-1-1F7F6F5F5F4F3F3F2F1F0F2F1F2F1F0F2F1F0F4F4F3

7、F3F3F2F1F0F2F1F0F2F1F0F1F1F1v0v1v2v3v4v5v6v717F1F0F2F1F0F2F1F0F2F1F0F3F1F1再計(jì)算F(7)112358-1-1F7F6F5F5F4F3F3F2F1F0F2F1F4F4F3F3F2F1F0F2F1F0F2F1F0F1F1v0v1v2v3v4v5v6v718F1F0F2F1F0F2F1F0F2F1F0F3F1F1再計(jì)算F(7)11235813-1F7F6F5F5F4F3F3F2F1F0F2F1F4F4F3F3F2F1F0F2F1F0F2F1F0F1F1v0v1v2v3v4v5v6v719F1F0F2F1F0F2F1F0F2F1

8、F0F3F3F3F2F1F0F2F1F0F2F1F0F1F1F1F1再計(jì)算F(7)11235813-1F7F6F5F5F4F3F3F2F1F0F2F1F4F4v0v1v2v3v4v5v6v720F1F2F1F0F2F1F0F2F1F0F4F3F3F3F2F1F0F2F1F0F2F1F0F1F1F1F1再計(jì)算F(7)1123581321F7F6F5F5F4F3F3F2F1F0F2F0F1F4v0v1v2v3v4v5v6v721新的實(shí)現(xiàn)節(jié)約了新的實(shí)現(xiàn)節(jié)約了大量的時(shí)間大量的時(shí)間我們能夠做得更好嗎?n注意到n使用備忘錄雖然可以減少重復(fù)計(jì)算,但是仍然需要函數(shù)調(diào)用以及參數(shù),這些會(huì)浪費(fèi)許多時(shí)間 .n事實(shí)上,

9、計(jì)算F(i),我們只需要計(jì)算F(i-1) & F(i-2)n改進(jìn)的想法n以自底向上的方式,即由簡(jiǎn)單到復(fù)雜開(kāi)始計(jì)算n依次計(jì)算F(2) (已知F(0)=F(1)=1), F(3), F(4)F2(n)1 F0 12 F1 13 for i 2 to n do4 Fi Fi-1 + Fi-25 return Fn22遞歸 vs 動(dòng)態(tài)規(guī)劃遞歸:F(n)1if n=0 or n=1 then return 12else return F(n-1) + F(n-2)動(dòng)態(tài)規(guī)劃:F2(n)1 F0 12 F1 13 for i 2 to n do4Fi Fi-1 + Fi-25 return Fn太慢

10、太慢!有效!時(shí)間復(fù)雜度僅為O(n)23方法的總結(jié)n寫(xiě)出一個(gè)遞歸公式,這個(gè)公式給出了問(wèn)題與其子問(wèn)題的解之間的關(guān)系nE.g. F(n) = F(n-1) + F(n-2).n用表(通常用數(shù)組)記錄子問(wèn)題的解,以便保存和以后的檢索 以從最簡(jiǎn)單問(wèn)題的解填起,以自底向上的方式填表n這就保證了,當(dāng)我們求解一個(gè)子問(wèn)題的時(shí)候,所有與子相關(guān)的子子問(wèn)題,都可以從表中直接取用,而不必重新計(jì)算由于20世紀(jì)40年代末期,還沒(méi)有出現(xiàn)計(jì)算,這個(gè)動(dòng)態(tài)填表的方法稱為動(dòng)態(tài)規(guī)劃246.2 動(dòng)態(tài)規(guī)劃n動(dòng)態(tài)規(guī)劃算法常用來(lái)求解最優(yōu)化問(wèn)題，設(shè)計(jì)一個(gè)動(dòng)態(tài)規(guī)劃算法通常有以下四個(gè)步驟n找出最優(yōu)解的結(jié)構(gòu)； n遞歸定義一個(gè)最優(yōu)解的值； n以自底向上

11、的方式（從最簡(jiǎn)單問(wèn)題開(kāi)始入手）計(jì)算出最優(yōu)解的值；1.根據(jù)計(jì)算最優(yōu)解的值的信息，構(gòu)造一個(gè)最優(yōu)解。256.2裝配線調(diào)度問(wèn)題裝配線調(diào)度問(wèn)題 n問(wèn)題描述n有兩條裝配線，每一條裝配線上有n個(gè)裝配點(diǎn)，將裝配線i上的第j個(gè)裝配點(diǎn)記為Sij ，設(shè)在該裝配點(diǎn)的裝配時(shí)間為aij。假設(shè)要裝配一輛汽車(chē)，將汽車(chē)底盤(pán)從進(jìn)廠點(diǎn)送入裝配線i(1或2)，需要時(shí)間ei。在裝配點(diǎn)裝配后，如果汽車(chē)傳送到同一條裝配線的裝配點(diǎn)進(jìn)行裝配，則傳送不需要時(shí)間。如果汽車(chē)從裝配點(diǎn)傳送到另一條裝配線進(jìn)行裝配，則需要傳送時(shí)間tij 。汽車(chē)在裝配點(diǎn)Sij裝配后，將汽車(chē)成品從裝配線上取下來(lái)，需要花費(fèi)時(shí)間xi 。裝配線調(diào)度問(wèn)題是如何確定每一個(gè)裝配點(diǎn)的裝配需

12、要在哪條線上進(jìn)行，使得當(dāng)汽車(chē)成品出來(lái)時(shí)，花費(fèi)的總時(shí)間最少。值得注意的是兩條裝配線的第個(gè)裝配點(diǎn)都裝配同樣的汽車(chē)部件，只是裝配效率不一樣。 26Ende1e2a11a12a13a21a22a23a1n-1a1na2n-1a2nx1x2t1n-1t2n-1BeginLine 1Line 2t11t21t12t22S11S12S13S1n-1S1nS21S22S23S2n-1S2n27一個(gè)辦法n枚舉法n在選擇裝配點(diǎn)時(shí),枚舉所有可能的選擇n計(jì)算每條裝配路線所需要的時(shí)間,然后選擇最好的n缺點(diǎn):n共有2n條裝配路線n當(dāng) n很大時(shí),實(shí)際上變得不可行100111 if choosing line 1 at st

13、ep j (= n)1234n0 if choosing line 2 at step j (= 3)281. 最優(yōu)解的結(jié)構(gòu)n考慮從進(jìn)廠到裝配點(diǎn) S1j可能的最快路線n如果j = 1:確定花多長(zhǎng)時(shí)間到 S11n如果 j 2, 到達(dá)S1j有兩個(gè)選擇:n過(guò) S1j-1, 然后到S1jn過(guò)S2j-1, 然后到 S1jn定理6.1:假定最快裝配路線過(guò)S1j-1 然后到S1j,則該路線中從進(jìn)廠到裝配點(diǎn) S1j-1的路線一定是最快的n如果最快裝配路線過(guò)S1j-2 ,則有同樣的結(jié)論29Optimal Substructuren一般性一般性:從進(jìn)廠到裝配點(diǎn)S1j的最短路線問(wèn)題的最優(yōu)解中一定包含了從進(jìn)廠到裝配點(diǎn)

14、S1j-1or S2j-1的最短路線子問(wèn)題的最優(yōu)解.n這就是最優(yōu)子結(jié)構(gòu)性質(zhì),它是一個(gè)問(wèn)題能夠用動(dòng)態(tài)規(guī)劃求解的標(biāo)志n我們可以利用這個(gè)性質(zhì)由子問(wèn)題的最優(yōu)解構(gòu)造出問(wèn)題的最優(yōu)解302. A Recursive Solution (cont.)n令fij =從進(jìn)廠到裝配點(diǎn)Sij的最快裝配時(shí)間n令 f * 表示問(wèn)題的最優(yōu)解,則n當(dāng)j = 1時(shí) f11 = e1 + a11 f21 = e2 + a21f * = min( f1n+x1 , f2n+x2 )312. 遞歸方法n計(jì)算 fij( j = 2, 3, ,n, and i = 1, 2)n從進(jìn)廠到裝配點(diǎn)S1j的最短路線,只有兩種情況:n要么經(jīng)過(guò)S1

15、j-1然后直接到S1j,即 f1j = f1j - 1 + a1jn要么經(jīng)過(guò)S2j-1然后傳送到裝配線S1j, 此時(shí)有 f1j = f2j -1 + t2j-1 + a1j因此,可以選擇最小的,即f1j = min(f1j - 1 + a1j, f2j -1 + t2j-1 + a1j)a1j-1a1j-1a2j-1t2j-1S1jS1j-1S2j-132n可以得到遞歸方程n例如, n=5:n如果按照遞歸的方式至頂向下求解,則計(jì)算量為指數(shù)級(jí)1 if) 1 1 , 1min(1 if 1 1 if) 1 1 , 1min(1 if 1 2112222212211111jjajtjfjajfjea

16、jfjjajtjfjajfjeajff1jf2j12345f15f25f14f24f13f232 times4 timesf12f22f11f21333. 計(jì)算最優(yōu)解n當(dāng) j 2, fij的值只依賴 f1j 1 和 f2j - 1的值n計(jì)算 fij的值n按照 j增加的順利n自底向上的方法n首先找子問(wèn)題的最優(yōu)解n利用子問(wèn)題的解獲得原問(wèn)題的解f1jf2j12345increasing j34構(gòu)造最優(yōu)解n為了構(gòu)造最優(yōu)解的值，我們需要知道每個(gè)站是在那條線上裝配的，令nlij 表示裝配點(diǎn)Sij( j = 2, 3, , n)的前一個(gè)裝配點(diǎn)(j - 1)的裝配線號(hào)(1, 2) nl* 表示出廠時(shí)，最快裝配

17、路線中裝配點(diǎn)n所在的裝配線號(hào)l1jl2j2345increasing j35Step 3: 計(jì)算最快裝配時(shí)間及路線DPFastestWay(a, t, e, x, n)1 f11 e1 + a11; f21 e2 + a212 for j 2 to n do3 if f1j - 1 + a1j f2 j - 1 + t2j-1 + a1j then4 f1j f1j - 1 + a1j5 l1j 16 else f1j f2 j - 1 + t2j-1 + a1j 7 l1j 28 if f2j - 1 + a2j f1j - 1 + t1j-1 + a2j then9 f2j f2j - 1

18、 + a2j 10 l2j 211 else f2 j f1j - 1 + t1j-1+ a2j then 12 l2j 113 if f1n + x1f2n + x2 then14 f* f1n + x115 l* 116 else f* f2n + x2 17 l* 2Running time: (n)36For example24327944885475233421213612BeginEnd123456jf1jf2jf *=389121816202224253230353723456jl1jl2jl *=12111112222374. 構(gòu)造最優(yōu)解PrintStations(l, n)1

19、 i l* 2 print “l(fā)ine ” i “, station ” n3 for j n downto 2 do4 i lij5 print “l(fā)ine ” i “, station ” j - 1line 1, station 6line 2, station 5line 2, station 4line 1, station 3line 2, station 223456jl1jl2jl *=12111112222line 1, station 13824327944885475233421213612BeginEnd最快裝配時(shí)間：f *=38紅線箭頭表示最快裝配路線396.3矩陣鏈

20、乘法問(wèn)題矩陣鏈乘法問(wèn)題 n問(wèn)題描述 給定n個(gè)矩陣 A1, A2, . . . , An ，矩陣Ai（ i = 1, 2, . . . , n ）的維數(shù)為 pi-1 pi, 問(wèn)如何對(duì)乘積A1 A2.An 家括號(hào)使得標(biāo)量乘法次數(shù)最小. A1 A2 Ai Ai+1 An p0 p1 p1 p2 pi-1 pi pi pi+1 pn-1 pn 矩陣乘積可以加括號(hào)，指的是矩陣的乘積是可以完全括號(hào)化的，即要么是單一的矩陣要么是兩個(gè)完全括號(hào)化的矩陣相乘之后再加上括號(hào)而形成的。 . 40n例如，矩陣乘積 A1 A2 A3 A4 有5種完全加括號(hào)的方式: (A1 (A2 (A3 A4) , (A1 (A2 A3

21、) A4) , (A1 A2) (A3 A4) , (A1 (A2 A3) A4) , (A1 A2) A3) A4). 前面我們介紹過(guò)，兩個(gè)矩陣A(pq)和B(qr)的乘積，其計(jì)算量(即標(biāo)量乘法次數(shù))為pqr41例如n考慮 A1, A2, A3 ，其維數(shù)分別為10100, 1005, 和 550則1. (A1A2) A3): A1A2 = 101005 = 5,000 (105) (A1 A2) A3) = 10550 = 2,500總共7,500次標(biāo)量乘法次數(shù)2. (A1 (A2A3): A2A3 = 100550 = 25,000 (10050) (A1 (A2 A3) = 101005

22、0 = 50,000總共 75,000次標(biāo)量乘法次數(shù)一個(gè)數(shù)量級(jí)差別!42加括號(hào)的方式數(shù)n令P(n)表示 n個(gè)矩陣鏈加括號(hào)的方式數(shù)。假設(shè)我們?cè)诘?k個(gè)矩陣和第 (k + 1)個(gè)矩陣(k = 1, 2, . . . , n -1)斷開(kāi)，則兩個(gè)子矩陣鏈可以分別加括號(hào)，從而可以得到如下遞歸方程2 if)()(1 if1)(11nknPkPnnPnk上述遞歸方程的解為 (2n).431. 最優(yōu)加括號(hào)的結(jié)構(gòu)n令A(yù)ij = Ai Ai+1 Aj, i jn對(duì)于 i j: Aij = Ai Ai+1 Aj = Ai Ai+1 Ak Ak+1 Aj = Aik Ak+1j n定理定理6.2 假設(shè)Aij的一種最優(yōu)

23、完全括號(hào)化方式是把乘積在Ak 和 Ak+1 (i k j)之間分開(kāi)，則其中子問(wèn)題Aik和Ak+1j的加括號(hào)的方式也一定是最優(yōu)的。44最優(yōu)子結(jié)構(gòu)證明：我們可以用反證法來(lái)證明這個(gè)結(jié)論。假設(shè)子問(wèn)題Ak 和 Ak+1的加括號(hào)方式不是最優(yōu)的，則說(shuō)明對(duì)子問(wèn)題Ak 和 Ak+1分別有一種更優(yōu)的加括號(hào)方式，它分別使得計(jì)算Ak 和 Ak+1的乘法次數(shù)更少，將該種加括號(hào)方式分別替換原來(lái)對(duì)子問(wèn)題Ak 和 Ak+1的加括號(hào)方式，則子問(wèn)題可得到一種新的加括號(hào)方式，它比原來(lái)最優(yōu)加括號(hào)方式的乘法次數(shù)更少，顯然矛盾。n這表明問(wèn)題最優(yōu)解里包含的子問(wèn)題的解一定也是最優(yōu)的。從而我們可以由子問(wèn)題的最優(yōu)解得到原問(wèn)題的最優(yōu)解452. 遞

24、歸方程n子問(wèn)題: 確定Aij = Ai Ai+1 Aj (1 i j n)的最小標(biāo)量乘法次數(shù)n令mi, j 表示計(jì)算 Aij 所需要的最小標(biāo)量乘法次數(shù)n則原問(wèn)題(A1.n)的最小乘法次數(shù)為 m1, n46 一個(gè)遞歸解 (續(xù))n遞歸地定義m:ni = j: Aii = Ai mi, i = 0, for i = 1, 2, , nni j: 假設(shè)Aij的完全括號(hào)化是把乘積從Ak和Ak+1之間分開(kāi), i k j: Aij = Aik Ak+1jmi, j = mi, k + mk+1, j + pi-1pkpjAikAk+1jAikAk+1j47一個(gè)遞歸解 (續(xù))n考慮子問(wèn)題的括號(hào)化 對(duì)1 i j

25、 n Aij = Ai Ai+1 Aj = Aik Ak+1j i k jnmi, j =要計(jì)算乘積Aij需要的最少乘法次數(shù)mi, j = mi, k + mk+1, j + pi-1pkpj計(jì)算Aik需要的最少乘法次數(shù)計(jì)算AikAkj需要的最少乘法次數(shù)計(jì)算Ak+1j需要的最少乘法次數(shù)mi, kmk+1,jpi-1pkpj48一個(gè)遞歸解 (續(xù))mi, j = mi, k + mk+1, j + pi-1pk pjn我們不知道k的值n對(duì)k有ji種可能的值: k = i, i+1, , j-1n對(duì)乘積Ai Ai+1 Aj括號(hào)化的最小代價(jià)為:. if, 1,min, if0,1jipppjkmkim

26、jijimjkijki49構(gòu)造最優(yōu)解n對(duì)上述解法的附加說(shuō)明: nsi, j = 我們把乘積Ai Ai+1 Aj劃分以便得到最優(yōu)括號(hào)化的劃分點(diǎn)k的值50計(jì)算最優(yōu)代價(jià)我們得到多少的子問(wèn)題?n對(duì)1 i j n將Aij括號(hào)化n對(duì)每個(gè)i和j都有一個(gè)問(wèn)題n一個(gè)遞歸算法可能在其遞歸樹(shù)的不同分支里多次碰到同一個(gè)子問(wèn)題 重疊的子問(wèn)題n通過(guò)輔助表自下而上逼近來(lái)計(jì)算解 (n2). if, 1,min, if0,1jipppjkmkimjijimjkijki51計(jì)算最優(yōu)代價(jià)(續(xù))n我們?nèi)绾翁顚?xiě)表m1.n, 1.n和s1.n, 1.n呢?n確定用來(lái)計(jì)算mi, j的輔助表的入口(?)nmi, j = 計(jì)算j i 1個(gè)矩陣

27、乘法的花費(fèi)nmi, j 只依賴于少于j i 1個(gè)的矩陣相乘的花費(fèi) Aij = Aik Ak+1jn填寫(xiě)m以便它可以和解決的問(wèn)題增長(zhǎng)的長(zhǎng)度相符合52計(jì)算最優(yōu)代價(jià)(續(xù))nLength = 0: i = j, i = 1, 2, , nnLength = 1: j = i + 1, i = 1, 2, , n-11123n23nfirstsecond自底向上計(jì)算每一行,在每一行中又從左到右計(jì)算在一個(gè)類(lèi)似矩陣s中我們保存k的值(?)m1, n給出了該問(wèn)題的最優(yōu)解ij53DPMatrixChain(p)DPMatrixChain(p)1 for i 1 to n do2 mi, i 03 for c 2

28、 to n do 4 for i 1 to n c + 1 do5 j i +c 1 6 mi, j 7 for k i to j 1 do8 q mi, k + mk+1, j + pi-1pkpj9 if q mi, j then10 mi, j q; si, j k11 return m and s運(yùn)行時(shí)間: (n3)對(duì)一個(gè)具體的 mi, j, 查找k的所有可能的情況并選擇最小花費(fèi)的那種情況54例子: min mi, k + mk+1, j + pi-1 pk pj m2, 2 + m3, 5 + p1p2p5m2, 3 + m4, 5 + p1p3p5m2, 4 + m5, 5 + p

29、1p4p511236236ij4545m2, 5 = min nmi, j的值只依賴于先前已計(jì)算得到的值k = 2k = 3k = 455例子:計(jì)算 A1A2A3 nA1: 10100 (p0p1)nA2: 1005 (p1p2)nA3: 550 (p2p3)mi, i = 0 對(duì) i = 1, 2, 3m1, 2 = m1, 1 + m2, 2 + p0p1p2 (A1A2) = 0 + 0 + 101005 = 5,000m2, 3 = m2, 2 + m3, 3 + p1p2p3 (A2A3) = 0 + 0 + 100550 = 25,000 m1,1 + m2,3 + p0p1p3

30、= 75,000 (A1(A2A3) m1,2 +m3, 3 + p0p2p3 = 7,500 (A1A2)A3)0001122335000125000275002m1,3 = min56構(gòu)建最優(yōu)解n保存對(duì)每個(gè)子問(wèn)題的最佳選擇nsi, j =通過(guò)把乘積 Ai.j從Ak和Ak+1之間分開(kāi)得到最佳括號(hào)化的k的值ns1, n確定整個(gè)A1.n的乘積n最終的矩陣乘積將在k = s1,n處被劃分A1.n = A1.s1, n As1, n+1.nn對(duì)每個(gè)遞歸的子乘積找出可以得到一個(gè)最優(yōu)括號(hào)化的k的值57構(gòu)建最優(yōu)解(續(xù))nsi, j =通過(guò)把乘積Ai Ai+1 Aj從Ak和Ak+1之間分開(kāi)得到最佳括號(hào)化的k

31、的值33355-3334-333-12-1-11236236ij4545s1,n=3 A1.6 = A1.3 A4.6s1,3=1 A1.3 = A1.1 A2.3s4,6=5 A4.6 = A4.5 A6.6A1.n = A1.s1, n As1, n+1.n58構(gòu)建最優(yōu)解(續(xù))33355-3334-333-12-1-11236236ij4545PrintParens(s, i, j)1 if i = j then print “Ai”2 else print “(”3 PrintParens(s, i, si, j)4 PrintParens(s, si, j + 1, j)5 print

32、 “)”59Example: A1 A633355-3334-333-12-1-11236236ij4545PrintOPTParens(s, i, j)1 if i = j then print “A”i2 else print “(”3 PrintOPTParens(s, i, si, j)4 PrintOPTParens(s, si, j + 1, j)5 print “)”P(pán)OP(s, 1, 6)s1, 6 = 3i = 1, j = 6 “(“ POP (s, 1, 3) s1, 3 = 1i = 1, j = 3 “(“ POP(s, 1, 1) “A1”P(pán)OP(s, 2, 3)

33、s2, 3 = 2i = 2, j = 3 “(“ POP (s, 2, 2) “A2” POP (s, 3, 3) “A3”“)” “)” (A4A5)A6)A1(A2A3)(s1.6, 1.6606.4 最長(zhǎng)公共子序列n一個(gè)給定序列的子序列是在該序列中刪去若干元素后得到的序列。n給定兩個(gè)序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時(shí)，稱Z是序列X和Y的公共子序列。n最長(zhǎng)公共子序列:公共子序列中長(zhǎng)度最長(zhǎng)的子序列。n最長(zhǎng)公共子序列問(wèn)題 給定兩個(gè)序列X=x1,x2,xm和Y=y1,y2, yn，找出X和Y的一個(gè)最長(zhǎng)公共子序列。n例如: X = A, B, C, B, D, A, B X的

34、子序列:n所有X的子集(集合中元素按原來(lái)在X中的順序排列) A, B, D, B, C, D, B, 等等.61例子X(jué) = A, B, C, B, D, A, B X = A, B, C, B, D, A, BY = B, D, C, A, B, A Y = B, D, C, A, B, AnB, C, B, A和B, D, A, B都是X和Y 的最長(zhǎng)公共子序列(長(zhǎng)度為4) n但是,B, C, A就不是X和Y的最長(zhǎng)公共子序列62窮舉法n對(duì)于每一個(gè)Xm的子序列,驗(yàn)證它是否是Yn的子序列.nXm有2m個(gè)子序列n每個(gè)子序列需要(n)的時(shí)間來(lái)驗(yàn)證它是否是Yn的子序列.n從Yn的第一個(gè)字母開(kāi)始掃描下去,

35、如果不是則從第二個(gè)開(kāi)始n運(yùn)行時(shí)間: (n2m)63n給定一個(gè)序列Xm = x1, x2, , xm,我們定義Xm的第i個(gè)前綴為:Xi = x1, x2, , xi i = 0, 1, 2, , mnci, j為序列Xi = x1, x2, , xi和Yj = y1, y2, , yj的最長(zhǎng)公共子序列的長(zhǎng)度.64n最優(yōu)子結(jié)構(gòu)性質(zhì)： 設(shè)序列Xm=x1,x2,xm和Yn=y1,y2,yn的一個(gè)最長(zhǎng)公共子序列為Zk=z1,z2,zk，則1.若xm=yn，則zk=xm=yn，且Zk-1是Xm-1和Yn-1的最長(zhǎng)公共子序列。2.若xmyn，且zkxm，則Zk是Xm-1和Yn的最長(zhǎng)公共子序列。3.若xmyn

36、，且zk yn ，則Zk是Xm和Yn-1的最長(zhǎng)公共子序列。65遞歸方程第1種情況: xi = yj例如: Xi = A, B, D, EYj = Z, B, En把xi=yj 添加到Xi-1和Yj-1最長(zhǎng)共同子序列中.n一定可以找到Xi-1和Yj-1的最長(zhǎng)共同子序列 一個(gè)問(wèn)題的最優(yōu)解一定包含了子問(wèn)題的最優(yōu)解. and 0, if)1, 1max(, and 0, if1 1, 1, 0or 0 if0,jijiyxjijicjicyxjijicjijic66遞歸解法第2種情況: xi yj例子: Xi = A, B, D, GYj = Z, B, Dn需要解決兩個(gè)問(wèn)題n找到 Xi-1和Yj的一

37、個(gè)最長(zhǎng)共同子序列: Xi-1 = A, B, D,Yj = Z, B, Dn找到一個(gè)Xi和Yj-1的一個(gè)最長(zhǎng)共同子序列: Xi = A, B, D, G, Yj-1 = Z, Bn一個(gè)問(wèn)題的最優(yōu)解一定包含了子問(wèn)題的最優(yōu)解ci, j = max ci - 1, j, ci, j-1 67重疊子問(wèn)題n找Xm和Yn的最長(zhǎng)共同子序列n我們可能需要在Xm和Yn-1中找最長(zhǎng)共同子序列,或者是在Xm-1和Yn中.n上面的問(wèn)題都有一個(gè)在Xm-1和Yn-1中找最長(zhǎng)共同子序列的子問(wèn)題.n子問(wèn)題又有子子問(wèn)題68計(jì)算最長(zhǎng)共同子序列的長(zhǎng)度0如果i = 0或者j = 0ci, j = ci-1, j-1 + 1如果 xi

38、 = yjmax(ci, j-1, ci-1, j)如果 xi yj00000000000yj:xmy1y2ynx1x2xiji012nm120firstsecond69附加信息 0 如果i, j = 0ci, j = ci-1, j-1 + 1 如果 xi = yj max(ci, j-1, ci-1, j) 如果 xi yj00000000000yj:DACFABxiji012nm120矩陣 bi, j:n它告訴我們要獲得最優(yōu)結(jié)果應(yīng)該如何選擇n如果 xi = yjbi, j = “ ”n如果 ci - 1, j ci, j-1bi, j = “ ”否則bi, j = “ ”33CDb &a

39、mp; c:ci,j-1ci-1,j70DPLCSLength(X, Y, m, n)1 for i 1 to m do ci, 0 02 for j 0 to n do c0, j 03 for i 1 to m do4 for j 1 to n do5 if xi = yj then6 ci, j ci - 1, j - 1 + 17 bi, j “ ”8 else if ci - 1, j ci, j - 1 then9 ci, j ci - 1, j10 bi, j “”11 else ci, j ci, j - 112 bi, j “”13 return c and b運(yùn)行時(shí)間: (

40、nm)71例子X(jué) = B, D, C, A, B, AY = A, B, C, B, D, A 0 當(dāng)i=0或者j=0ci, j = ci-1, j-1 + 1 當(dāng) xi = yj max(ci, j-1, ci-1, j) 當(dāng)xi yj0126345yjBDACAB51203467DABxiCBAB00000000000000000 11 1 1111 2211 2222 1122 331 222331232 3 4 1223 44如果 xi = yj bi, j = “ ”如果 ci - 1, jci, j-1bi, j = “ ”否則bi, j = “ ”72找出最長(zhǎng)共同子序列n從bm,

41、 n開(kāi)始并跟著箭頭走.n當(dāng)我們?cè)赽i, j中碰到 “ ” xi = yj 是最長(zhǎng)共同子序列中的一個(gè)元素0126345yjBDACAB51203467DABxiCBAB00000000000000000 11 1 1111 2211 2222 1122 331 222331232 3 4 1223 4473找出最長(zhǎng)共同子序列PrintLCS(b, X, i, j)1 if i = 0 or j = 0 then return 02 if bi, j = then3 PrintLCS (b, X, i - 1, j - 1)4 print xi5 else if bi, j = then6 Pri

42、ntLCS(b, X, i - 1, j)7 else PrintLCS(b, X, i, j - 1)746.5 背包問(wèn)題n0-1背包問(wèn)題背包問(wèn)題n一個(gè)小偷在洗劫一家商店時(shí)找到了n個(gè)物品:其中第i個(gè)物品價(jià)值vi并且重wi(vi, wi都是整數(shù))n小偷的背包只能承受W的重量n物品要么被帶走要么留下n帶那些物品可以在指定的重量下達(dá)到價(jià)值最大呢?n可帶碎片的背包問(wèn)題可帶碎片的背包問(wèn)題n與上述基本相同n小偷可以帶走一個(gè)物品的一部分 750-1背包問(wèn)題n小偷有一個(gè)可承受W的背包n有n件物品: 第i個(gè)物品價(jià)值vi 且重win目標(biāo): n找到xi使得對(duì)于所有的xi = 0, 1, i = 1, 2, .,

43、n wixi W 并且 xivi 最大76最優(yōu)子結(jié)構(gòu)n考慮最多重W的物品且價(jià)值最高n如果我們把j物品從背包中拿出來(lái) 剩下的裝載一定是取自n-1個(gè)物品使得不超過(guò)載重量W wj并且所裝物品價(jià)值最高的裝載770-1背包問(wèn)題的動(dòng)態(tài)規(guī)劃nVi, w 考慮前i件物品所能獲得的最高價(jià)值,其中w是背包的承受力n第1種情況:物品i的重量wiw,即小偷不拿物品i Vi, w = Vi - 1, w78DPKnapsack(S, W)1 for w 0 to w1 - 1 do V1, w 02 for w w1 to W do V1, w v13 for i 2 to n do4 for w 0 to W do5

44、 if wi w then6 Vi, w Vi-1, w7 bi, w 8 else if Vi-1, w Vi-1, w-wi + vi then9 Vi, w Vi-1, w 10 bi, w 11 else12 Vi, w Vi-1, w-wi + vi13 bi, w 14 return V and b運(yùn)行時(shí)間: (nW)790-1背包問(wèn)題的動(dòng)態(tài)規(guī)劃000000000000000000:n1w - wiWi-10firstVi, w = max vi + Vi - 1, w-wi, Vi - 1, w 帶走物品i不帶走物品iiwsecond80Vi, w = max vi + Vi -

45、 1, w-wi, Vi - 1, w 0000000000物品重量?jī)r(jià)值12122110332042150123451234W = 5012121212101222222210122230321015253037V1, 1 = V1, 2 = V1, 3 = V1, 4 = V1, 5 = V2, 1= V2, 2= V2, 3= V2, 4= V2, 5= V3, 1= V3, 2= V3, 3= V3, 4= V4, 5= V4, 1= V4, 2= V4, 3= V4, 4= V4, 5= max12+0, 0 = 12max12+0, 0 = 12max12+0, 0 = 12max1

46、2+0, 0 = 12max10+0, 0 = 10max10+0, 12 = 12max10+12, 12 = 22max10+12, 12 = 22max10+12, 12 = 22V(2,1) = 10V(2,2) = 12max20+0, 22=22max20+10,22=30max20+12,22=32P3,1 = 10max15+0, 12 = 15max15+10, 22=25max15+12, 30=30max15+22, 32=370V0, 1 = 0例子wi81構(gòu)造最優(yōu)解法000000000001234512340121212121012222222101222303210

47、152530370n從 Vn, W開(kāi)始n當(dāng)往左上走物品i被帶走n當(dāng)直往上走物品i未被帶走物品4物品2物品182子問(wèn)題的重復(fù)000000000000000000:n1Wi-10Vi, w = max vi + Vi - 1, w-wi, Vi - 1, w iw例如: 所有用灰色表示的子問(wèn)題都取決于Vi-1, w子問(wèn)題的重復(fù)100101108108681006282861001623823816510000000000000111111111例子: n=5, p=6,3,5,4,6, w=2,2,6,5,4, W=10846.6 最優(yōu)二叉搜索樹(shù)n問(wèn)題 給定序列 K = ，其中n個(gè)關(guān)鍵字互不相同，

48、且都已排好序 (k1 k2 kn), 并且有 n + 1 個(gè)“虛擬”的關(guān)鍵字 d0, d1, d2, ., dn 我們希望從這些關(guān)鍵字中建立一棵二叉搜索樹(shù)。對(duì)于每個(gè)關(guān)鍵字 ki, 搜索的概率為 pi 。 對(duì)于每個(gè) di, 相應(yīng)的搜索概率為 qi 。 假設(shè)一個(gè)搜索的實(shí)際花費(fèi)為二叉樹(shù)的節(jié)點(diǎn)數(shù), i.e., 在 T 中找到的節(jié)點(diǎn)的深度為 +1。從而在 T 中所做的一次搜索所花費(fèi)的預(yù)期成本為 給定一個(gè)概率的集合, 我們的目標(biāo)是構(gòu)造一棵二叉搜索樹(shù)T，使得 E(T) 為最小。inidinikqlplTEii01) 1() 1()(85Example i012345pi0.150.10.050.10.2qi

49、0.050.10.05 0.05 0.050.1d0k2k1k4k3k5d1d2d3d4d5d0k2k1k5k4d1d2d3d4d5k3E(T)= 2.80E(T)= 2.7586nodedepthprobabilitycontributionk110.150.3k200.10.1k320.050.15k410.10.2k520.20.6d020.050.15d120.10.3d230.050.2d330.050.2d430.050.2d530.10.4E(T)=2.887預(yù)期的搜索成本niiiTniiiTniniiiiTniniiiiTniiiTniiiTqdpkqqdppkqdpkTE01

50、001101)(d)(d1 )(d)(d ) 1)(d() 1)(d( in cost search 101niiniiqp88窮舉搜索n給定一個(gè)概率集，我們的目標(biāo)是構(gòu)造一棵二叉搜索樹(shù)，使得其預(yù)期搜索成本達(dá)到最小。我們稱這樣的樹(shù)為 最優(yōu)二叉搜索樹(shù)最優(yōu)二叉搜索樹(shù).n將一棵具有n個(gè)節(jié)點(diǎn)的二叉樹(shù)的節(jié)點(diǎn)關(guān)鍵字記為 k1, k2, ., kn 以構(gòu)造一棵二叉搜索樹(shù)，然后加上虛擬關(guān)鍵字作為葉子。n對(duì)于每個(gè)節(jié)點(diǎn), 賦予關(guān)鍵字，并計(jì)算預(yù)期的搜索成本。n這種搜索的代價(jià)太大!89最優(yōu)二叉搜索樹(shù)的結(jié)構(gòu)n考慮二叉搜索樹(shù)的子樹(shù)。 它包含的關(guān)鍵字必須在一個(gè)連續(xù)的范圍 ki, ., kj中，其中1ijn. 另外，一個(gè)包含關(guān)

51、鍵字 ki, ., kj 的子樹(shù)也必須包括虛擬關(guān)鍵字di-1, ., dj作為葉子。n最優(yōu)子結(jié)構(gòu)性質(zhì): 如果最優(yōu)二叉搜索樹(shù) T 有一棵子樹(shù) T 包含關(guān)鍵字 ki, ., kj, 那么子樹(shù) T必須也是最優(yōu)的，對(duì)于帶關(guān)鍵字 ki, ., kj 和虛擬關(guān)鍵字 di-1, ., dj的子問(wèn)題而言?？梢詰?yīng)用通常的剪切-粘貼技巧。 如果有一棵子樹(shù)T的預(yù)期成本低于子樹(shù) T,那么我們可以從T中剪下T并連到 T中，從而存在一棵二叉搜索樹(shù)的預(yù)期成本小于T, 這與 T是最優(yōu)的矛盾。90最優(yōu)子結(jié)構(gòu)性質(zhì)nki, ,kj中的一個(gè)關(guān)鍵字，記為 kr, 其中 i r j, 必須是一棵最優(yōu)子樹(shù)的根.n kr 的左子樹(shù)包括 ki

52、,.,kr1.nkr 的右子樹(shù)包括kr+1, .,kj.n為了找到一棵最優(yōu)的 BST:n考察所有候選的樹(shù)根 kr , for i r jn確定所有包含 ki,.,kr1 和 kr+1,.,kj的最佳 BSTs。krkikr-1kr+1kj91遞歸方程n找出最優(yōu) BST包含ki,.,kj, 其中i 1, j n, j i1. 當(dāng) j = i1, 樹(shù)只含有 di-1.n定義 ei, j =對(duì)于 ki,.,kj 和虛擬節(jié)點(diǎn) di-1, ., dj，最優(yōu) BST 的期望搜索成本nIf j = i1, then ei, j = qi-1.nIf j i,n選出樹(shù)根 kr, 對(duì)于某個(gè)r， i r j .n

53、遞歸地構(gòu)造一棵最優(yōu) BSTs n對(duì)ki,.,kr1 構(gòu)造左子樹(shù)n對(duì)kr+1,.,kj 構(gòu)造右子樹(shù)92遞歸方程n當(dāng)最優(yōu)的子樹(shù)成為一個(gè)結(jié)點(diǎn)的子樹(shù)時(shí):n每個(gè)原來(lái)在最優(yōu)子樹(shù)中結(jié)點(diǎn)的深度加1.n期望搜索費(fèi)用增加n如果 kr 是一棵由ki,.,kj 組成的最優(yōu)BST的根 :nei, j = pr + (ei, r1 + w(i, r1)+(er+1, j + w(r+1, j) = ei, r1 + er+1, j + w(i, j).n但是，我們還不知道 kr. 因此,(because w(i, j)=w(i,r1) + pr + w(r + 1, j)., 1 1,min, 1,1jijiwjreri

54、eijqjiejriijilljillqpjiw1),(93構(gòu)造最優(yōu)解對(duì)于每個(gè)子問(wèn)題 (i,j), 存儲(chǔ):n期望搜索成本組成的表格 e1 .n+1 , 0 .nn只使用入口 ei, j , 其中 j i1.nrooti, j = 由 ki,.,kj組成的子樹(shù)的根，其中 1 i j n.nw1.n+1, 0.n = 所有節(jié)點(diǎn)的概率和nwi, i1 = qi-1 for 1 i n.nwi, j = wi, j-1 + pj+ qj for 1 i j n.94DPOptimalBST(p, q, n)1 for i 1 to n + 1 do2 ei, i 1 qi-13 wi, i 1 qi-

55、14 for c 1 to n do5 for i 1 to nc + 1 do6 j i + c17 ei, j 8 wi, j wi, j1 + pj+qj9 for r i to j do10 t ei, r1 + er + 1, j + wi, j 11 if t ei, j then12 ei, j t13 rooti, j r14 return e and rootRunning time: (n3)952.752.01.30.90.50.11.751.20.60.30.051.250.70.250.050.90.40.050.450.10.0510236125ij45342.752.01.30.90.50.11.751.20.60.30.