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

1、12 學(xué)習(xí)要點(diǎn)學(xué)習(xí)要點(diǎn): :理解動(dòng)態(tài)規(guī)劃算法的概念理解動(dòng)態(tài)規(guī)劃算法的概念掌握動(dòng)態(tài)規(guī)劃算法的基本要素掌握動(dòng)態(tài)規(guī)劃算法的基本要素（1）最優(yōu)子結(jié)構(gòu)性質(zhì)）最優(yōu)子結(jié)構(gòu)性質(zhì)（2）重疊子問題性質(zhì)）重疊子問題性質(zhì)掌握設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的步驟掌握設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的步驟(1)找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。(2)遞歸地定義最優(yōu)值。遞歸地定義最優(yōu)值。(3)以自底向上的方式計(jì)算出最優(yōu)值。以自底向上的方式計(jì)算出最優(yōu)值。(4)根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。3通過應(yīng)用范例學(xué)習(xí)動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)策略通過應(yīng)用范例學(xué)習(xí)動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)策略（1）

2、斐波那契數(shù)列；）斐波那契數(shù)列；（2）0-1背包問題；背包問題；（3）矩陣連乘問題；）矩陣連乘問題；（4）最長公共子序列；）最長公共子序列；（5）最優(yōu)二分檢索樹；）最優(yōu)二分檢索樹；（6）裝配線調(diào)度問題；）裝配線調(diào)度問題；（7）凸多邊形最優(yōu)三角剖分；）凸多邊形最優(yōu)三角剖分；（8）最大子段和問題。）最大子段和問題。4動(dòng)態(tài)規(guī)劃（動(dòng)態(tài)規(guī)劃（Dynamic Programming）n1957年，年，Richard Bellman創(chuàng)造了這個(gè)名字創(chuàng)造了這個(gè)名字n 該方法利用該方法利用表格表格技術(shù)，用技術(shù)，用多項(xiàng)式復(fù)雜度多項(xiàng)式復(fù)雜度代替代替指數(shù)復(fù)雜度。指數(shù)復(fù)雜度。n典型應(yīng)用是組合優(yōu)化問題，求解典型應(yīng)用是組合優(yōu)化

3、問題，求解最優(yōu)值和最優(yōu)最優(yōu)值和最優(yōu)解解。5n動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個(gè)子問題解成若干個(gè)子問題nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=6n但是經(jīng)分解得到的子問題往往但是經(jīng)分解得到的子問題往往不是互相獨(dú)立的不是互相獨(dú)立的。不同子問題的。不同子問題的數(shù)目常常只有多項(xiàng)式量級。在用分治法求解時(shí)，有些子問題被數(shù)目常常只有多項(xiàng)式量級。在用分治法求解時(shí)，有些子問題被重復(fù)計(jì)算了許多次。重復(fù)計(jì)算了許多次。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(

4、n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)7n如果能夠如果能夠保存已解決的子問題的答案保存已解決的子問題的答案，而在需要時(shí)再找出已求，而在需要時(shí)再找出已求得的答案，就可以避免大量重復(fù)計(jì)算，從而得到多項(xiàng)式時(shí)間算得的答案，就可以避免大量重復(fù)計(jì)算，從而得到多項(xiàng)式時(shí)間算法。法。n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n)8學(xué)習(xí)內(nèi)容學(xué)習(xí)內(nèi)容3.1 用表代替遞歸用表代替遞歸3.2 0-1背包問題背

5、包問題3.3 矩陣鏈乘問題矩陣鏈乘問題3.4 動(dòng)態(tài)規(guī)劃算法的基本要素動(dòng)態(tài)規(guī)劃算法的基本要素3.5 備忘錄方法備忘錄方法3.6 裝配線調(diào)度問題裝配線調(diào)度問題3.7 最長公共子序列問題最長公共子序列問題3.8 最優(yōu)二分檢索樹最優(yōu)二分檢索樹3.9 凸多邊形的最優(yōu)三角剖分凸多邊形的最優(yōu)三角剖分93.1 用表代替遞歸用表代替遞歸1. 動(dòng)態(tài)規(guī)劃與分治法比較動(dòng)態(tài)規(guī)劃與分治法比較2.動(dòng)態(tài)規(guī)劃基本步驟動(dòng)態(tài)規(guī)劃基本步驟103.1 用表代替遞歸用表代替遞歸【例例1】有一對兔子，從第三個(gè)月起每個(gè)月都有一對兔子，從第三個(gè)月起每個(gè)月都生一對小兔子，然后小兔子長到三個(gè)月時(shí)也生一對小兔子，然后小兔子長到三個(gè)月時(shí)也生一對小兔子

6、，生一對小兔子，假設(shè)所有兔子都成活假設(shè)所有兔子都成活。問每。問每個(gè)月的兔子總數(shù)有多少對？個(gè)月的兔子總數(shù)有多少對？ 1，1，2，3，5，8，13，21，以上是以上是Fibonacci數(shù)列中的數(shù)字，而數(shù)列中的數(shù)字，而Fibonacci數(shù)列也稱為數(shù)列也稱為“兔子序列兔子序列”，早在，早在1202年的年的算盤書算盤書中就有記載。中就有記載。113.1 用表代替遞歸用表代替遞歸【例例1】Fibonacci數(shù)列數(shù)列用分治法得到如下算法：用分治法得到如下算法： int Fbnc(int n) if(n=3),解此遞歸方程得解此遞歸方程得 T(n)=(3/2)n) “壞壞”算法算法原因：存在大量地重復(fù)計(jì)算。原

7、因：存在大量地重復(fù)計(jì)算。12斐波那契數(shù)列的遞歸調(diào)用樹斐波那契數(shù)列的遞歸調(diào)用樹Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(4)Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(5)133.1 用表代替遞歸用表代替遞歸n若采用動(dòng)態(tài)規(guī)劃方法，依次把這些數(shù)都計(jì)算并保存起來，若采用動(dòng)態(tài)規(guī)劃方法，依次把這些數(shù)都計(jì)算并保存起來，則每次計(jì)算都用前面已得到的結(jié)果而則每次計(jì)算都用前面已得到的結(jié)果而不必重復(fù)計(jì)算不必重復(fù)計(jì)算，這，這個(gè)算法的時(shí)間復(fù)雜度將是個(gè)算法的時(shí)間復(fù)雜度將是O(n)的。的。int Fbnc1(int n) int f100

8、0=0 f0=1;f1=1; for(i=2;imax then maxt return max22【例例2 2】0-1背包問題背包問題n動(dòng)態(tài)規(guī)劃法求最優(yōu)值是利用一個(gè)表格，以動(dòng)態(tài)規(guī)劃法求最優(yōu)值是利用一個(gè)表格，以自底向上的方式計(jì)算最優(yōu)解值。自底向上的方式計(jì)算最優(yōu)解值。n物品個(gè)數(shù)物品個(gè)數(shù)n，背包容量，背包容量W作為輸入，并將作為輸入，并將ci,w存儲(chǔ)在表格存儲(chǔ)在表格c0.n,0.W中，中，以行為主以行為主序序從左到右計(jì)算表從左到右計(jì)算表c中的元素。中的元素?？疾煲粋€(gè)考察一個(gè)0-10-1背包問題的實(shí)例如下：背包問題的實(shí)例如下：n=5n=5，W=10W=10，w=2,2,6,5,4w=2,2,6,5,

9、4，v=6,3,5,4,6v=6,3,5,4,6【例例2 2】0-1背包問題背包問題Ci,w012345678910000000000000100666666666200669999999300669999111114400669991011131450066991212151515n=5，W=10，w=2,2,6,5,4，v=6,3,5,4,624【例例2 2】0-1背包問題背包問題n(3)(3)計(jì)算計(jì)算0-10-1背包問題最優(yōu)值背包問題最優(yōu)值nKnapSack-DP(n,W)n1 for w0 to W /1-2初始化工作初始化工作n2 do c0,w=0n3 for i1 to n /按

10、行填寫子問題最優(yōu)值按行填寫子問題最優(yōu)值n4 do ci,0=0 n5 for w1 to W25【例例2 2】0-1背包問題背包問題n6 do if wici-1,wn8 then ci,wvi+ci-1,w-win9 else ci,wci-1,wn10 else ci,wci-1,w算法復(fù)雜度分析：算法復(fù)雜度分析：算法需要算法需要O(nw)計(jì)算時(shí)間。當(dāng)背包容量計(jì)算時(shí)間。當(dāng)背包容量w很很大時(shí)，算法需要的計(jì)算時(shí)間較多。大時(shí)，算法需要的計(jì)算時(shí)間較多。Ci,w01234567800000000001006666666200669999930066999911已知已知0-1背包問題如下：背包問題如下

11、：n=3，W=8，w=2,2,6，v=6,3,5，求解該實(shí)例的最優(yōu)值和最優(yōu)解。，求解該實(shí)例的最優(yōu)值和最優(yōu)解。【例例2 2】0-1背包問題背包問題27【例例2 2】0-1背包問題背包問題(4)根據(jù)計(jì)算結(jié)果，構(gòu)造問題的最優(yōu)解根據(jù)計(jì)算結(jié)果，構(gòu)造問題的最優(yōu)解OUTPUT-SACK(c,w)n for in downto 2n do if ci,w=ci-1,wn then xi0n else xi1n ww-win x1c1,w?1:0n return x28矩陣鏈乘矩陣鏈乘(matrix-chain multiplication)問題問題1. 兩個(gè)矩陣相乘兩個(gè)矩陣相乘2.矩陣鏈乘問題矩陣鏈乘問題3.

12、動(dòng)態(tài)規(guī)劃解決方案動(dòng)態(tài)規(guī)劃解決方案29矩陣鏈乘問題矩陣鏈乘問題1.兩個(gè)矩陣相乘兩個(gè)矩陣相乘708566924385162 978856243162 B A【計(jì)算計(jì)算】若若A是一個(gè)是一個(gè)pq矩陣，矩陣，B是一個(gè)是一個(gè)qr矩陣，則矩陣，則其乘積其乘積C=AB是一個(gè)是一個(gè)pr矩陣，總共需要矩陣，總共需要pqr次次數(shù)乘。數(shù)乘。30矩陣鏈乘問題矩陣鏈乘問題u設(shè)有四個(gè)矩陣設(shè)有四個(gè)矩陣 ，它們的維數(shù)分別是：，它們的維數(shù)分別是：計(jì)算計(jì)算A A* *B B* *C C* *D D總共有五種結(jié)合的方式總共有五種結(jié)合的方式u每種結(jié)合方式所需要的乘法次數(shù)分別為：每種結(jié)合方式所需要的乘法次數(shù)分別為：u你會(huì)選擇哪種結(jié)合方式

13、完成計(jì)算？你會(huì)選擇哪種結(jié)合方式完成計(jì)算？DCBA , , ,5 1A 1 4B 4 3C 3 5D )(DCAB)(DBCA)(DBCA)(CDBA)(CDAB52, 105, 180, 155, 1002.2.矩陣鏈乘問題矩陣鏈乘問題312.2.矩陣鏈乘問題矩陣鏈乘問題找出計(jì)算找出計(jì)算n n個(gè)矩陣相乘的計(jì)算量最小的乘積順序。個(gè)矩陣相乘的計(jì)算量最小的乘積順序。【尋找依據(jù)尋找依據(jù)】矩陣相乘是可結(jié)合的，不同結(jié)合方式產(chǎn)生相同的矩陣相乘是可結(jié)合的，不同結(jié)合方式產(chǎn)生相同的乘積結(jié)果，但計(jì)算量是不同的。乘積結(jié)果，但計(jì)算量是不同的。矩陣鏈乘問題矩陣鏈乘問題32【例例3 3】矩陣鏈乘問題矩陣鏈乘問題2.2.矩陣

14、鏈乘問題矩陣鏈乘問題 【問題描述問題描述】 給定給定n n個(gè)矩陣個(gè)矩陣A A1 1,A,A2 2,A,An n，其中其中A Ai i與與A Ai+1i+1是可乘的，是可乘的，i=1i=1，22，n-1n-1。如何。如何確定計(jì)算矩陣連乘積的計(jì)算次序，使得依此次確定計(jì)算矩陣連乘積的計(jì)算次序，使得依此次序計(jì)算矩陣連乘積需要的序計(jì)算矩陣連乘積需要的數(shù)乘次數(shù)最少數(shù)乘次數(shù)最少。u窮舉法窮舉法：列舉出所有可能的計(jì)算次序，并計(jì)算出列舉出所有可能的計(jì)算次序，并計(jì)算出每一種計(jì)算次序相應(yīng)需要的數(shù)乘次數(shù)，從中找出一每一種計(jì)算次序相應(yīng)需要的數(shù)乘次數(shù)，從中找出一種數(shù)乘次數(shù)最少的計(jì)算次序。種數(shù)乘次數(shù)最少的計(jì)算次序。 33【

15、結(jié)論結(jié)論】矩陣鏈乘計(jì)算次序問題具有矩陣鏈乘計(jì)算次序問題具有最優(yōu)子結(jié)構(gòu)最優(yōu)子結(jié)構(gòu)性質(zhì)性質(zhì)。（1）分析最優(yōu)解的結(jié)構(gòu)矩陣鏈乘問題矩陣鏈乘問題3.動(dòng)態(tài)規(guī)劃解決方案動(dòng)態(tài)規(guī)劃解決方案將矩陣連乘積將矩陣連乘積 簡記為簡記為Ai:j ，這里，這里ij 設(shè)最優(yōu)計(jì)算次序是在矩陣設(shè)最優(yōu)計(jì)算次序是在矩陣Ak和和Ak+1之間將矩陣之間將矩陣鏈斷開，鏈斷開，ikj，則其相應(yīng)完全加括號(hào)方式為，則其相應(yīng)完全加括號(hào)方式為).)(.(211jkkkiiAAAAAAjiiAAA.134矩陣鏈乘問題矩陣鏈乘問題3.動(dòng)態(tài)規(guī)劃解決方案動(dòng)態(tài)規(guī)劃解決方案（2）建立遞歸關(guān)系設(shè)計(jì)算設(shè)計(jì)算Ai:j，1ijn，所需要的最少數(shù)乘，所需要的最少數(shù)乘次數(shù)

16、次數(shù)mi,j，則，則n個(gè)矩陣連乘問題的最優(yōu)值為個(gè)矩陣連乘問題的最優(yōu)值為m1,n。 當(dāng)當(dāng)i=j時(shí)，時(shí)，Ai:j=Ai，因此，因此，mi,i=0，i=1,2,n。35（2）建立遞歸關(guān)系jkipppjkmkimjim1, 1,這里 的維數(shù)為 iAiipp1當(dāng)當(dāng)ij時(shí)時(shí)，矩陣鏈乘問題矩陣鏈乘問題3.動(dòng)態(tài)規(guī)劃解決方案動(dòng)態(tài)規(guī)劃解決方案jipppjkmkimjijimjki, 1,min0,1jki K 的位置只有的位置只有 j-i 種種可能可能36遞歸實(shí)現(xiàn)遞歸實(shí)現(xiàn) RecurMatrix(p,i,j)n if i=jn then return 0n uRecurMatrix(p,i,i)+RecurMat

17、rix(p,i+1,j)+pi-1*pi*pjnFor ki+1 to j n do n t=RecurMatrix(p,i,k)+RecurMatrix(p,k+1,j)+pi-1*pk*pjn if tu n then u=t nreturn u 37（3）計(jì)算最優(yōu)值）計(jì)算最優(yōu)值在遞歸計(jì)算時(shí)，在遞歸計(jì)算時(shí)，許多子問題被重復(fù)計(jì)算多次許多子問題被重復(fù)計(jì)算多次。這也是該問題可用。這也是該問題可用動(dòng)態(tài)規(guī)劃算法求解的又一顯著特征。動(dòng)態(tài)規(guī)劃算法求解的又一顯著特征。 重疊子問題重疊子問題是使用動(dòng)態(tài)規(guī)劃的另一個(gè)要素。是使用動(dòng)態(tài)規(guī)劃的另一個(gè)要素。矩陣鏈乘問題矩陣鏈乘問題3.動(dòng)態(tài)規(guī)劃解決方案動(dòng)態(tài)規(guī)劃解決方案3

18、8（3）計(jì)算最優(yōu)值）計(jì)算最優(yōu)值n以矩陣維數(shù)以矩陣維數(shù)p=作為輸入作為輸入 n按照按照矩陣鏈長度增加的方式矩陣鏈長度增加的方式，填充最，填充最優(yōu)值表格優(yōu)值表格m1.n,1.n，同時(shí)利用輔，同時(shí)利用輔助表格助表格s1.n,1.n存儲(chǔ)矩陣鏈乘的存儲(chǔ)矩陣鏈乘的最優(yōu)斷開位置最優(yōu)斷開位置k。矩陣鏈乘問題矩陣鏈乘問題3.動(dòng)態(tài)規(guī)劃解決方案動(dòng)態(tài)規(guī)劃解決方案39（3）計(jì)算最優(yōu)值）計(jì)算最優(yōu)值n【計(jì)算舉例計(jì)算舉例】已知矩陣大小如表，計(jì)算已知矩陣大小如表，計(jì)算A1*A2*A3*A4*A5所需的最小乘法次數(shù)和對應(yīng)所需的最小乘法次數(shù)和對應(yīng)的計(jì)算次序（即加括號(hào)方式）。的計(jì)算次序（即加括號(hào)方式）。A1A2A3A4A535577

19、44668jipppjkmkimjijimjki, 1,min0,1jkiMi, j123451020304050（3）計(jì)算最優(yōu)值）計(jì)算最優(yōu)值已知：已知：P0=3;P1=5;P2=7;P3=4;P4=6;P5=8189140168260261405492416192105Si, j1234510210322043330543340（3）計(jì)算最優(yōu)值）計(jì)算最優(yōu)值42（3）計(jì)算最優(yōu)值計(jì)算最優(yōu)值 MatrixChain(p) nlengthp-1 for i1 to n do mi,i0 for l2 to n /鏈長度控制鏈長度控制 do for i1 to n-l+1 /i從從1到到n-1 do

20、ji+l-1 /j從從2到到n mi,j /表中數(shù)據(jù)賦初值表中數(shù)據(jù)賦初值 for ki to j-1 /k表示所有可能的斷開位置表示所有可能的斷開位置 do qmik+mk+1j+pi-1pkpj if q0時(shí)時(shí)， bj=bj-1+aj， 否則否則， bj=aj。（2 2）建立遞歸方程）建立遞歸方程bj=maxbj-1+aj, aj, 1jn 最大子段和問題的動(dòng)態(tài)規(guī)劃算法最大子段和問題的動(dòng)態(tài)規(guī)劃算法-例：例：an+111-2-2-4-5130154326bn+10015432601 i j0 sum besti bestj00 j j j j j j j j j j j j-212112112

21、2374201320245156求求a=（-2，11，-4，13，-5，-2）的最大子段和。的最大子段和。an+111-2-2-4-5130154326bn+100154326 j j j j j j j j j j j j-2117201315（3 3）計(jì)算最優(yōu)值）計(jì)算最優(yōu)值據(jù)此，可設(shè)計(jì)出求最大子段和的動(dòng)態(tài)規(guī)劃算法如下：據(jù)此，可設(shè)計(jì)出求最大子段和的動(dòng)態(tài)規(guī)劃算法如下：int MaxSum（int n, int *a） int sum=0,b=0,i=0,besti=0,bestj=0; for (int j=1; j0) b+= aj; else b=aj;i=j; if (b sum) su

22、m=b; besti=i; bestj=j; return sum; 算法復(fù)雜性分析：算法復(fù)雜性分析： 時(shí)間復(fù)雜性時(shí)間復(fù)雜性T(n)=O(n) 空間復(fù)雜性空間復(fù)雜性S(n)=O(1)遞歸方程：遞歸方程： 當(dāng)當(dāng)bj-10時(shí)時(shí)， bj=bj-1+aj， 否則否則， bj=aj。50【例【例4】例如，已知序列例如，已知序列X=AX=A，B B，C C，B B，D D，B, AB, A則下面的哪些序列是它的子序列？則下面的哪些序列是它的子序列？1.Z= 2.Z=B,C,D,B 3.Z=A,D,C1.Z= 2.Z=B,C,D,B 3.Z=A,D,C4.Z=A,D,B 5. Z=B,B,B 6.Z=X4.

23、Z=A,D,B 5. Z=B,B,B 6.Z=X另有一序列另有一序列YB,C,D,B,A給定給定2 2個(gè)序列個(gè)序列X=xX=x1 1,x,x2 2, ,x,xm m 和和Y=yY=y1 1,y,y2 2, ,y,yn n ，找出，找出X X和和Y Y的最長公共子的最長公共子序列。序列。 51設(shè)序列設(shè)序列X=x1,x2,xm和和Y=y1,y2,yn的最長公共子序列為的最長公共子序列為Z=z1,z2,zk ，則，則由此可見，由此可見，2個(gè)序列的最長公共子序列包含了個(gè)序列的最長公共子序列包含了這這2個(gè)序列的前綴的最長公共子序列。因此，個(gè)序列的前綴的最長公共子序列。因此，最長公共子序列問題具有最長公共

24、子序列問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)。 (1)(1)若若xm=yn，則，則zk=xm=yn，且，且Zk-1是是Xm-1和和Yn-1的最長公共子的最長公共子序列。序列。(2)(2)若若xmyn且且zkxm，則，則Z是是Xm-1和和Y Y的最長公共子序列。的最長公共子序列。(3)(3)若若xm myn n且且zk kyn n，則，則Z是是X和和Yn-1n-1的最長公共子序列。的最長公共子序列。52 由最長公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建由最長公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關(guān)系。立子問題最優(yōu)值的遞歸關(guān)系。用用lij記錄兩序列的最長公共子序列的長度。記錄兩序列的最長公共子序

25、列的長度。其中，其中， Xi=x1,x2,xiYj=y1,y2,yj。當(dāng)當(dāng)i=0或或j=0時(shí)，空序列是時(shí)，空序列是Xi和和Yj的最長公共子的最長公共子序列。故此時(shí)序列。故此時(shí)lij=0。其它情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸其它情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下：關(guān)系如下：jijiyxjiyxjijijiljiljiljil; 0,; 0,0, 01,1max1 11054【例例】給定兩個(gè)序列給定兩個(gè)序列X XA,B,C,B A,B,C,B Y=B,D,C,A,BY=B,D,C,A,B。求求X X和和Y Y的最長公共子序列。的最長公共子序列。jijiyxjiyxjijijiljilji

26、ljil; 0,; 0,0, 01,1max1 110【例例4】X Y01 B2 D3 C4 A5 B00000001 A00 00 112 B0 1111 23 C011 2 224 B0 1122 356LCSLength(X,Y) mlengthX nlengthY for i 1 to m do li,0 0 for j 1 to n do l0,j 0 for i 1 to m do for j 1 to n do if xi=yj then li,j li-1,j-1+1 bi,j “” else if li-1,j=li,j-1 then li,jli-1,j bi,j“” el

27、se li,j li,j-1 bi,j “” return l and b由于在所考慮由于在所考慮的子問題空間中，的子問題空間中，總共有總共有(mn)個(gè)個(gè)不同的子問題。不同的子問題。由于每個(gè)數(shù)組元由于每個(gè)數(shù)組元素的計(jì)算時(shí)間為素的計(jì)算時(shí)間為O(1)，因此時(shí)間，因此時(shí)間復(fù)雜度為復(fù)雜度為O(mn)。 57構(gòu)造最長公共子序列構(gòu)造最長公共子序列LCS(b,x,i,j) if i=0 or j=0 then return if bI,j=“” then LCS(b,X,i-1,j-1) output xi else if bI,j=“” then LCS(b,X,i-1,j) else LCS(b,X,i

28、,j-1)583.4 動(dòng)態(tài)規(guī)劃算法的基本要素問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)。性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)。利用問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，以利用問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，以自底向上自底向上的方的方式遞歸地從子問題的最優(yōu)解逐步構(gòu)造出整個(gè)問式遞歸地從子問題的最優(yōu)解逐步構(gòu)造出整個(gè)問題的最優(yōu)解。題的最優(yōu)解。最優(yōu)子結(jié)構(gòu)是問題能用動(dòng)態(tài)規(guī)劃算法求解的前最優(yōu)子結(jié)構(gòu)是問題能用動(dòng)態(tài)規(guī)劃算法求解的前提。提。593.4 動(dòng)態(tài)規(guī)劃算法的基本要素動(dòng)態(tài)規(guī)劃算法的基本要素（1）原問題的最優(yōu)解中，利用了多少個(gè)子問題？）原問題的最優(yōu)解中，利用了多少個(gè)子問題？（2）決定最優(yōu)解

29、中使用哪些子問題需做多少次）決定最優(yōu)解中使用哪些子問題需做多少次決策？決策？在具體問題分析過程中，解決兩個(gè)問題：在具體問題分析過程中，解決兩個(gè)問題：由此，動(dòng)態(tài)規(guī)劃算法的運(yùn)行時(shí)間取決于兩個(gè)因素由此，動(dòng)態(tài)規(guī)劃算法的運(yùn)行時(shí)間取決于兩個(gè)因素的乘積：的乘積：所有子問題的數(shù)目以及對于每個(gè)子問題所有子問題的數(shù)目以及對于每個(gè)子問題需要做多少次決策。需要做多少次決策。60遞歸算法求解問題時(shí)，每次產(chǎn)生的子問題并不遞歸算法求解問題時(shí)，每次產(chǎn)生的子問題并不總是新問題這種性質(zhì)稱為總是新問題這種性質(zhì)稱為子問題的重疊性質(zhì)。子問題的重疊性質(zhì)。動(dòng)態(tài)規(guī)劃算法，對每一個(gè)子問題只解一次，而動(dòng)態(tài)規(guī)劃算法，對每一個(gè)子問題只解一次，而后將

30、其解保存在一個(gè)表格中。后將其解保存在一個(gè)表格中。3.4 動(dòng)態(tài)規(guī)劃算法的基本要素動(dòng)態(tài)規(guī)劃算法的基本要素61用動(dòng)態(tài)規(guī)劃算法只需要多項(xiàng)式時(shí)間，從而獲得用動(dòng)態(tài)規(guī)劃算法只需要多項(xiàng)式時(shí)間，從而獲得較高的解題效率。較高的解題效率。 623.5 備忘錄（備忘錄（memorization)方法方法備忘錄方法的控制結(jié)構(gòu)與直接遞歸方法的控制備忘錄方法的控制結(jié)構(gòu)與直接遞歸方法的控制結(jié)構(gòu)相同，即結(jié)構(gòu)相同，即自頂向下自頂向下的計(jì)算方式。的計(jì)算方式。區(qū)別在于備忘錄方法為每個(gè)解過的子問題建立區(qū)別在于備忘錄方法為每個(gè)解過的子問題建立了備忘錄（即將子問題的解存放在表格中），了備忘錄（即將子問題的解存放在表格中），以備需要時(shí)查看，

31、以備需要時(shí)查看，避免了相同子問題的重復(fù)求避免了相同子問題的重復(fù)求解。解。 633.5 備忘錄方法備忘錄方法計(jì)算斐波那契數(shù)的備忘錄方法如下：計(jì)算斐波那契數(shù)的備忘錄方法如下：nint f1000=0; /賦特殊值賦特殊值nint Memorization-f(int n)n int t;n if (fn!=0) return fn; /判斷是否已經(jīng)遞歸計(jì)算過判斷是否已經(jīng)遞歸計(jì)算過n if (n=0) t=1;n if(n=1) t=1;n if(n1) t=Memorization-f(n-1)+Memorization-f(n-2); / 遞歸計(jì)算遞歸計(jì)算n return fn=t;n【練習(xí)】最

32、大子段和問題【問題定義問題定義】對于給定序列對于給定序列a1,a2,a3an,a1,a2,a3an,尋找尋找它的某個(gè)連續(xù)子段，使得其和最大。它的某個(gè)連續(xù)子段，使得其和最大。當(dāng)所給數(shù)字均為負(fù)數(shù)時(shí)定義子段和為當(dāng)所給數(shù)字均為負(fù)數(shù)時(shí)定義子段和為0 0。即求函數(shù)即求函數(shù) f(i,j)=max0,sum(ai.j)f(i,j)=max0,sum(ai.j)的最大的最大值。值?！締栴}實(shí)例問題實(shí)例2 2】已知序列已知序列a=-2a=-2，1111，-4-4，1313，-5-5，-2-2，求其最大子段和。，求其最大子段和。【問題實(shí)例問題實(shí)例1 1】已知序列已知序列a=4a=4，-3-3，5 5，-2-2，-1-

33、1，2 2，6 6，-2-2，求其最大子段和。，求其最大子段和。653.5 備忘錄方法備忘錄方法n矩陣鏈乘問題的備忘錄方法：矩陣鏈乘問題的備忘錄方法：P65n0-1背包問題的備忘錄方法：背包問題的備忘錄方法：P69備忘錄方法有如下特點(diǎn)：備忘錄方法有如下特點(diǎn)： 1它是一種對自然問題求解的機(jī)械轉(zhuǎn)換；它是一種對自然問題求解的機(jī)械轉(zhuǎn)換； 2方法自身可以確定子問題的順序；方法自身可以確定子問題的順序； 3可能不需要計(jì)算所有子問題的解。可能不需要計(jì)算所有子問題的解。673.6 裝配線調(diào)度問題裝配線調(diào)度問題【例例5】n某公司生產(chǎn)汽車過程中使用兩條裝配線。每條裝配某公司生產(chǎn)汽車過程中使用兩條裝配線。每條裝配線

34、有線有n個(gè)站點(diǎn)，完成零件裝配。我們用個(gè)站點(diǎn)，完成零件裝配。我們用Sij表示第表示第i條條裝配線上第裝配線上第j個(gè)站點(diǎn)個(gè)站點(diǎn)(i=1,2；j=1,2,3,n),兩條裝配兩條裝配線上對應(yīng)站點(diǎn)的功能相同，但需要的裝配時(shí)間不同。線上對應(yīng)站點(diǎn)的功能相同，但需要的裝配時(shí)間不同。用用bij表示在表示在Sij處所需裝配時(shí)間，處所需裝配時(shí)間，ei表示進(jìn)入裝配線表示進(jìn)入裝配線i的進(jìn)入時(shí)間，的進(jìn)入時(shí)間，oi表示退出裝配線表示退出裝配線i的時(shí)間。的時(shí)間。tij表示離表示離開裝配線開裝配線i的轉(zhuǎn)移時(shí)間的轉(zhuǎn)移時(shí)間(i=1,2;j=1,2,3,n)。n問題是決定通過哪些站點(diǎn)完成一輛汽車的裝配，問題是決定通過哪些站點(diǎn)完成一輛

35、汽車的裝配，使得裝配時(shí)間達(dá)到最小。使得裝配時(shí)間達(dá)到最小。68【例例5】裝配線調(diào)度問題裝配線調(diào)度問題(assembly-line scheduling problem)n使用窮舉法來解決該問題，需要考察使用窮舉法來解決該問題，需要考察2n個(gè)可個(gè)可能路線，復(fù)雜度太大。能路線，復(fù)雜度太大。69【例例5】裝配線調(diào)度問題裝配線調(diào)度問題n1. 分析問題的最優(yōu)子結(jié)構(gòu)分析問題的最優(yōu)子結(jié)構(gòu)n考慮一個(gè)底盤從開始點(diǎn)到通過站點(diǎn)考慮一個(gè)底盤從開始點(diǎn)到通過站點(diǎn)S1j的最快方的最快方式，它一定通過裝配線式，它一定通過裝配線1或或2的站點(diǎn)的站點(diǎn)Sij-1,即或者即或者通過站點(diǎn)通過站點(diǎn)S1j-1并直接通過站點(diǎn)并直接通過站點(diǎn)S1

36、j，或者通過站，或者通過站點(diǎn)點(diǎn)S2j-1并從裝配線并從裝配線2轉(zhuǎn)移到裝配線轉(zhuǎn)移到裝配線1，然后通過，然后通過站點(diǎn)站點(diǎn)S1j。n由對稱性可得通過站點(diǎn)由對稱性可得通過站點(diǎn)S2j的最快方式。的最快方式。從而，要找通過站點(diǎn)從而，要找通過站點(diǎn)Sij的最快方式，就要找子的最快方式，就要找子問題通過站點(diǎn)問題通過站點(diǎn)Sij-1的最快方式。的最快方式。70【例例5】裝配線調(diào)度問題裝配線調(diào)度問題n2遞歸定義問題最優(yōu)值遞歸定義問題最優(yōu)值nfij表示從開始點(diǎn)到通過站點(diǎn)表示從開始點(diǎn)到通過站點(diǎn)Sij的最快時(shí)間，的最快時(shí)間，f*表示底盤從開始點(diǎn)經(jīng)過工廠所有最優(yōu)站點(diǎn)到表示底盤從開始點(diǎn)經(jīng)過工廠所有最優(yōu)站點(diǎn)到輸出的最快時(shí)間，則輸

37、出的最快時(shí)間，則 f*=minf1n+o1,f2n+o22 1, 1min1 2 1, 1min1 21122222211211111112jbtjfbjfjbejfjbtjfbjfjbejfjjjjjj【例例5】裝配線調(diào)度問題裝配線調(diào)度問題n用用lij表示裝配線號(hào)，其值為表示裝配線號(hào)，其值為1或或2，表示最快通過，表示最快通過Sij的站點(diǎn)的站點(diǎn)j-1所在所在的裝配線。其中，的裝配線。其中，j=2,3,4,n。7172【例例5】裝配線調(diào)度問題裝配線調(diào)度問題n3.計(jì)算問題的最優(yōu)裝配時(shí)間計(jì)算問題的最優(yōu)裝配時(shí)間j123456b1j793484t1j23134t2j21221b2j856457i12e

38、i24oi32【例例5】裝配線調(diào)度問題裝配線調(diào)度問題j123456f1j91820243235f2j121622253037j123456L1j112112L2j21212274【例例5】裝配線調(diào)度問題裝配線調(diào)度問題nFastest-way(b,t,e,o,n)n f11e1+b11n f21e2+b21n for j 2 to nn do if f1j-1+b1j=f2j-1+t2j-1+b1j n/對裝配線對裝配線1的第的第j個(gè)站點(diǎn)賦值個(gè)站點(diǎn)賦值n then f1j=f1j-1+b1jn l1j=1n else f1j= f2j-1+t2j-1+b1jn l1j=2 【例例5】裝配線調(diào)度問

39、題裝配線調(diào)度問題nif f2j-1+b2j=f1j-1+t1j-1+b2j /對裝配線對裝配線2的第的第j個(gè)站點(diǎn)賦值個(gè)站點(diǎn)賦值n then f2j=f2j-1+b2jn l2j=2n else f2j= f1j-1+t1j-1+b2jn l2j=1 【例例5】裝配線調(diào)度問題裝配線調(diào)度問題nif f1n+o1=f2n+o2n then f*=f1n+o1 /f*最快通過裝配線最快通過裝配線的時(shí)間的時(shí)間n L*=1 /L*最快通過站點(diǎn)最快通過站點(diǎn)n所在的所在的裝配線裝配線n else f*=f2n+o2n L*=277【例例5】裝配線調(diào)度問題裝配線調(diào)度問題n4. 構(gòu)造問題的最優(yōu)解構(gòu)造問題的最優(yōu)解n

40、用用lij表示裝配線號(hào)其值為表示裝配線號(hào)其值為1或或2，表示最快通，表示最快通過過Sij的站點(diǎn)的站點(diǎn)j-1所在的裝配線。這里所在的裝配線。這里j=2,3,4,n。n用用L*表示最快通過站點(diǎn)表示最快通過站點(diǎn)n所在的裝配線。所在的裝配線。nOutput-station(L,i,j)n if j=0 then return n Output-station(L,lij-1,j-1)n print “l(fā)ine”i“,station”j78【作業(yè)作業(yè)】3. A=“xzyzzyx” Y“zxyyzxz” 用動(dòng)態(tài)規(guī)劃法求解用動(dòng)態(tài)規(guī)劃法求解LCS。4. 已知裝配線調(diào)度問題的各參數(shù)如下表所示，已知裝配線調(diào)度問題

41、的各參數(shù)如下表所示，請給出該問題的解。請給出該問題的解。 j1234567b1j7934845t1j231342t2j212213b2j8564576i12ei23oi32【作業(yè)作業(yè)3答案之一答案之一】Y A01 x2 z3 y4 z5 z6 y7 x0000000001 z00 11 1 1 112 x0 111111 23 y011 222 224 y011 222 335 z01 22 3 3336 x0 112333 47 z01 22 3 444803.8最優(yōu)二分檢索樹（最優(yōu)二分檢索樹（BST）【例例6】n給定給定n個(gè)關(guān)鍵字組成的個(gè)關(guān)鍵字組成的有序有序序列序列S=,利用這些關(guān)鍵字建立

42、一棵二分檢索樹。其中，利用這些關(guān)鍵字建立一棵二分檢索樹。其中，每個(gè)關(guān)鍵字每個(gè)關(guān)鍵字si存在相應(yīng)的檢索概率為存在相應(yīng)的檢索概率為pi，另設(shè)，另設(shè)n+1個(gè)虛擬外部結(jié)點(diǎn)個(gè)虛擬外部結(jié)點(diǎn)e0(所有小于所有小于s1的值的值)，e1, en(所有大于所有大于sn的值的值),表示不在表示不在S中的那些值，每中的那些值，每個(gè)外部結(jié)點(diǎn)的檢索概率是個(gè)外部結(jié)點(diǎn)的檢索概率是qi。n對于給定的概率集合，我們想要構(gòu)造一棵具有對于給定的概率集合，我們想要構(gòu)造一棵具有最最小期望檢索開銷小期望檢索開銷的二分檢索樹，并稱之為最優(yōu)二的二分檢索樹，并稱之為最優(yōu)二分檢索樹。分檢索樹。n最小期望開銷最小期望開銷即能夠使得在所有查找中所訪問

43、的即能夠使得在所有查找中所訪問的結(jié)點(diǎn)總數(shù)達(dá)到最小。結(jié)點(diǎn)總數(shù)達(dá)到最小。81n查找成功與不成功的概率n二分檢索樹的期望開銷n有 個(gè)節(jié)點(diǎn)的二叉樹的個(gè)數(shù)為：n窮舉搜索法的時(shí)間復(fù)雜度為指數(shù)級110niniiiqpniiiTniiiTniiiTniiiTqdpkqdpkTE0101)(depth)(depth1) 1)(depth() 1)(depth() incost search(n)/4(2/3nn0e1e2e3e4e5e1s2s3s4s5s822.80 Total0.40 0.10 3 0.20 0.05 3 0.20 0.05 3 0.20 0.05 3 0.30 0.10 2 0.15 0.0

44、5 2 0.60 0.20 2 0.20 0.10 1 0.15 0.05 2 0.10 0.10 0 0.30 0.15 1 oncontributiy probabilit depth node54321 054321eeeeeesssss0e1e2e3e4e5e1s2s3s4s5s83（1）刻畫最優(yōu)二分檢索樹的子結(jié)構(gòu)）刻畫最優(yōu)二分檢索樹的子結(jié)構(gòu)n如果一棵最優(yōu)二分檢索樹T的子樹T包括si,sj,那么它的子樹T一定也是最優(yōu)的，且以si,sj為內(nèi)部結(jié)點(diǎn)，以ei-1,ej為外部結(jié)點(diǎn)。n給定關(guān)鍵字si,sj，假定其中關(guān)鍵字sk為包含這些關(guān)鍵字的最優(yōu)子樹的根，根sk的左子樹一定包含關(guān)鍵字si,sk-

45、1以及ei-1,ek-1；右子樹一定包含關(guān)鍵字sk+1,sj以及ek,ej。n所以只要我們檢查所有候選根結(jié)點(diǎn)所有候選根結(jié)點(diǎn)sk(ikj)，就能決定包含關(guān)鍵字si,sk-1以及sk+1,sj的所有最優(yōu)二分檢索樹。84（2）遞歸定義）遞歸定義BST最優(yōu)值最優(yōu)值n設(shè)ri,j為在關(guān)鍵字si,sj的最優(yōu)二分檢索樹中查找的期望開銷，其中i1,i-1jn。jilljillqpjiw1),(n問題的目標(biāo)是計(jì)算r1,n。nj=i-1時(shí)，ri,i-1=qi-1nji時(shí)，選擇關(guān)鍵字sk為最優(yōu)二分檢索樹的根，根sk的左子樹包含關(guān)鍵字si,sk-1以及ei-1,ek-1；右子樹包含關(guān)鍵字sk+1,sj以及ek,ej。n

46、 ri,j=ri,k-1+rk+1,j+w(i,j)n ，即以sk為根的子樹中的概率之和85（2）遞歸定義）遞歸定義BST最優(yōu)值最優(yōu)值ijqp)w(i,ji- j qjiw其中，ijjiwjkrkiri-jqjirjjijkii 11),( ),(, 1 1,min1 ,11n綜上，遞歸定義式為：綜上，遞歸定義式為：另定義另定義rooti,j存儲(chǔ)下標(biāo)存儲(chǔ)下標(biāo)k，這個(gè)，這個(gè)k使得使得sk為關(guān)鍵為關(guān)鍵字字si,sj構(gòu)成的最優(yōu)二分檢索樹的根。構(gòu)成的最優(yōu)二分檢索樹的根。86（3）計(jì)算）計(jì)算BST的最優(yōu)值的最優(yōu)值n【例】已知檢索序列n=3, S=blue,course,fly p=,q=,請構(gòu)造最優(yōu)二分

47、檢索樹。87（3）計(jì)算）計(jì)算BST的最優(yōu)值的最優(yōu)值nOptimal_bst(p,q,n) nfor i1 to n+1 /邊界條件邊界條件n do ri,i-1qi-1n wi,i-1qi-1 nfor l1 to n /控制序列長度控制序列長度n do for i1 to n-l+1n do ji+l-1n ri,jn wi,jwi,j-1+pj+qj 88（3）計(jì)算）計(jì)算BST的最優(yōu)值的最優(yōu)值n for ki to j /檢查所有可能根結(jié)點(diǎn)檢查所有可能根結(jié)點(diǎn)n do tri,k-1+rk+1,j+wi,jn if tri,jn then ri,jtn rooti,jknreturn roo

48、t and r 89（4）構(gòu)造）構(gòu)造BST的最優(yōu)解的最優(yōu)解n由rooti,j中記錄的下標(biāo)來構(gòu)造最優(yōu)解root1234511212322342244524555ji90nConstruct-opt-subtree(i,j,k,dir,root)n if i=jn then trooti,jn print st is dir child of skn construct-opt-subtree(i,t-1,t,left,root)n construct-opt-subtree(t+1,j,t,right,root)nConstruct-optimal-bst(root,1,n)n kroot1,n

49、n print sk is the rootn construct-opt-subtree(1,k-1,k,left,root)n construct-opt-subtree(k+1,n,k,right,root)913.9【例【例7】用多邊形頂點(diǎn)的逆時(shí)針序列表示凸多邊形，即P=v0,v1,vn-1表示具有n條邊的凸多邊形。若vi與vj是多邊形上不相鄰的2個(gè)頂點(diǎn)，則線段vivj稱為多邊形的一條弦。弦將多邊形分割成2個(gè)多邊形vi,vi+1,vj和vj,vj+1,vi。多邊形的三角剖分多邊形的三角剖分是將多邊形分割成互不相交 的三角形的弦的集合T。92【例例7】n多邊形的最優(yōu)三角剖分多邊形的最優(yōu)三

50、角剖分：給定凸多邊形P，以及定義在由多邊形的邊和弦組成的三角形上的權(quán)函數(shù)權(quán)函數(shù)w。要求確定該凸多邊形的三角剖分，使得該三角剖分中諸三角形上權(quán)之和為最小權(quán)之和為最小。93一個(gè)表達(dá)式的完全加括號(hào)方式相應(yīng)于一棵完全二叉樹，稱為表達(dá)式的語法樹。例如，完全加括號(hào)的矩陣連乘積(A1(A2A3)(A4(A5A6)所相應(yīng)的語法樹如圖 (a)所示。凸多邊形v0,v1,vn-1的三角剖分也可以用語法樹表示。例如，圖 (b)中凸多邊形的三角剖分可用圖 (a)所示的語法樹表示。 矩陣連乘積中的每個(gè)矩陣Ai對應(yīng)于凸(n+1)邊形中的一條邊vi-1vi。三角剖分中的一條弦vivj，ij，對應(yīng)于矩陣連乘積Ai+1:j。94

51、凸多邊形的最優(yōu)三角剖分與矩陣連乘凸多邊形的最優(yōu)三角剖分與矩陣連乘積問題積問題n矩陣連乘積的最優(yōu)計(jì)算次序問題是凸多邊形最矩陣連乘積的最優(yōu)計(jì)算次序問題是凸多邊形最優(yōu)三角剖分問題的一個(gè)特殊情形。優(yōu)三角剖分問題的一個(gè)特殊情形。n對于給定的矩陣鏈A1A2.An，定義一個(gè)與之相應(yīng)的凸(n+1)邊形P=v0,v1,vn-1,vn,使得矩陣Ai與凸多邊形的邊vi-1vi一一對應(yīng)。若矩陣Ai的維數(shù)為pi-1pi,i=1,2,.n,則定義三角形vivjvk上的權(quán)函數(shù)值為w(vivjvk)=pipjpk。依此權(quán)函數(shù)定義，凸多邊形P的最優(yōu)三角剖分對應(yīng)矩陣鏈A1A2.An最優(yōu)加括號(hào)方式。95凸多邊形的最優(yōu)三角剖分問題有

52、最優(yōu)子結(jié)構(gòu)性質(zhì)。事實(shí)上，若凸(n+1)邊形P=v0,v1,vn-1的最優(yōu)三角剖分T包含三角形v0vkvn，1kn-1，則T的權(quán)為3個(gè)部分權(quán)的和：三角形v0vkvn的權(quán)，子多邊形v0,v1,vk和vk,vk+1,vn的權(quán)之和。可以斷言，由T所確定的這2個(gè)子多邊形的三角剖分也是最優(yōu)的。因?yàn)槿粲衯0,v1,vk或vk,vk+1,vn的更小權(quán)的三角剖分將導(dǎo)致T不是最優(yōu)三角剖分的矛盾。 96定義tij，1ijn為凸子多邊形vi-1,vi,v 的最優(yōu)三角剖分所對應(yīng)的權(quán)函數(shù)值，即其最優(yōu)值。為方便起見，設(shè)退化的多邊形vi-1,vi具有權(quán)值0。據(jù)此定義，要計(jì)算的凸(n+1)邊形P的最優(yōu)權(quán)值為t1n。jijivv

53、vwjktkitjitjkijki)(1min01tij的值可以利用最優(yōu)子結(jié)構(gòu)性質(zhì)遞歸地計(jì)算。當(dāng)j-i1時(shí)，凸子多邊形至少有3個(gè)頂點(diǎn)。由最優(yōu)子結(jié)構(gòu)性質(zhì)，tij的值應(yīng)為tik的值加上tk+1j的值，再加上三角形vi-1vkvj的權(quán)值，其中ikj-1。由于在計(jì)算時(shí)還不知道k的確切位置，而k的所有可能位置只有j-i個(gè)，因此可以在這j-i個(gè)位置中選出使tij值達(dá)到最小的位置。由此，tij可遞歸地定義為：97構(gòu)造最優(yōu)解n利用輔助表s1.n，1.n存儲(chǔ)哪個(gè)k值使得計(jì)算ti,j時(shí)達(dá)到最優(yōu)。98例題例題已知凸五邊形已知凸五邊形P=v0,v1,v2,v3,v4,各頂點(diǎn)的權(quán)值各頂點(diǎn)的權(quán)值分別為分別為2，3，4，5

54、，6。定義三角形定義三角形vivjvk上上的權(quán)函數(shù)值為的權(quán)函數(shù)值為w(vivjvk)=vivjvk,試求該多邊形的試求該多邊形的最優(yōu)三角剖分。最優(yōu)三角剖分。99 總結(jié)總結(jié)理解動(dòng)態(tài)規(guī)劃算法的概念理解動(dòng)態(tài)規(guī)劃算法的概念掌握動(dòng)態(tài)規(guī)劃算法的基本要素掌握動(dòng)態(tài)規(guī)劃算法的基本要素（1）最優(yōu)子結(jié)構(gòu)性質(zhì)）最優(yōu)子結(jié)構(gòu)性質(zhì)（2）重疊子問題性質(zhì)）重疊子問題性質(zhì)掌握設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的步驟掌握設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的步驟(1)找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。(2)遞歸地定義最優(yōu)值。遞歸地定義最優(yōu)值。(3)以自底向上的方式計(jì)算出最優(yōu)值。以自底向上的方式計(jì)算出最優(yōu)值。(4)根據(jù)計(jì)算最優(yōu)值時(shí)得

55、到的信息，構(gòu)造最優(yōu)解。根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。100通過應(yīng)用范例學(xué)習(xí)動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)策略通過應(yīng)用范例學(xué)習(xí)動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)策略（1）斐波那契數(shù)列；）斐波那契數(shù)列；（2）0-1背包問題；背包問題；（3）矩陣連乘問題；）矩陣連乘問題；（4）最長公共子序列；）最長公共子序列；（5）裝配線調(diào)度問題）裝配線調(diào)度問題；（6）最優(yōu)二分檢索樹；）最優(yōu)二分檢索樹；（7）凸多邊形最優(yōu)三角剖分。）凸多邊形最優(yōu)三角剖分?！揪毩?xí)練習(xí)】n1.采用動(dòng)態(tài)規(guī)劃策略求解問題的顯著特征是滿采用動(dòng)態(tài)規(guī)劃策略求解問題的顯著特征是滿足最優(yōu)性原理，其含義是足最優(yōu)性原理，其含義是_。nA.當(dāng)前所出的決策不會(huì)影響后面的決策當(dāng)前所

56、出的決策不會(huì)影響后面的決策 B.原問題的最優(yōu)解包含其子問題的最優(yōu)解原問題的最優(yōu)解包含其子問題的最優(yōu)解 C.問題可以找到最優(yōu)解，但利用貪心法不能找問題可以找到最優(yōu)解，但利用貪心法不能找到最優(yōu)解到最優(yōu)解D.每次決策必須是當(dāng)前看來最優(yōu)決策才可以找每次決策必須是當(dāng)前看來最優(yōu)決策才可以找到最優(yōu)解到最優(yōu)解【練習(xí)練習(xí)】n2.利用動(dòng)態(tài)規(guī)劃方法求解每對結(jié)點(diǎn)之間的最短路徑問利用動(dòng)態(tài)規(guī)劃方法求解每對結(jié)點(diǎn)之間的最短路徑問題題(all pairs shortest path problem)時(shí)，設(shè)有向圖時(shí)，設(shè)有向圖G=共有共有n個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)編號(hào)個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)編號(hào)1n，設(shè)，設(shè)C是是G的的成本鄰接矩陣，成本鄰接矩陣，Dk(i

57、，j)即為圖即為圖G中結(jié)點(diǎn)中結(jié)點(diǎn)i到到j(luò)并且不經(jīng)并且不經(jīng)過編號(hào)比過編號(hào)比k還大的結(jié)點(diǎn)的最短路徑的長度（還大的結(jié)點(diǎn)的最短路徑的長度（Dn(i，j)即即為圖為圖G中結(jié)點(diǎn)中結(jié)點(diǎn)i到到j(luò)的最短路徑長度），則求解該問題的最短路徑長度），則求解該問題的遞推關(guān)系式為的遞推關(guān)系式為_。nA.Dk(i，j)=Dk-1(i，j)+C(i，j)B.Dk(i，j)=minDk-1(i，j)，Dk-1(i，j)+C(i，j)C.Dk(i，j)=Dk-1(i，k)+Dk-1(k，j)D.Dk(i，j)=minDk-1(i，j)，Dk-1(i，k)+Dk-1(k，j)【練習(xí)練習(xí)】n3.對于求取兩個(gè)長度為對于求取兩個(gè)長度為n

58、的最長公共子序列問的最長公共子序列問題，利用題，利用（1）策略可以有效地避免最長公共策略可以有效地避免最長公共子序列重復(fù)計(jì)算，得到時(shí)間復(fù)雜度為子序列重復(fù)計(jì)算，得到時(shí)間復(fù)雜度為O(n2)的的正確算法，串正確算法，串和和的最長公共子序列的長度為的最長公共子序列的長度為（2）。nA分治法分治法 B貪心法貪心法 C動(dòng)態(tài)規(guī)劃方法動(dòng)態(tài)規(guī)劃方法 D分支分支-限界限界nA3 B4 C5 D6【練習(xí)練習(xí)】n4.以下的算法設(shè)計(jì)方法中，以下的算法設(shè)計(jì)方法中， 以獲取問題最以獲取問題最優(yōu)解為目標(biāo)。優(yōu)解為目標(biāo)。nA. 回溯方法回溯方法 B. 分治方法分治方法nC. 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃 D. 遞推遞推【練習(xí)練習(xí)】5.用動(dòng)態(tài)

59、規(guī)劃求解矩陣鏈乘問題用動(dòng)態(tài)規(guī)劃求解矩陣鏈乘問題M1*M2*M3*M4,其中其中M1(20*5)、M2（5*35）、）、M3（35*4）、）、M4（4*25），則最優(yōu)計(jì)算次序），則最優(yōu)計(jì)算次序?yàn)椋椋?）。）?！揪毩?xí)練習(xí)】6.用動(dòng)態(tài)規(guī)劃方法求解用動(dòng)態(tài)規(guī)劃方法求解0/1背包問題時(shí)，將背包問題時(shí)，將“用前用前i個(gè)物品來裝容量是個(gè)物品來裝容量是X的背包的背包”的的0/1背背包問題記為包問題記為KNAP(1,i,X),設(shè)設(shè)fi(X)是是KNAP(1,i,X)最優(yōu)解的效益值，第最優(yōu)解的效益值，第j個(gè)物品的個(gè)物品的重量和放入背包后取得效益值分別為重量和放入背包后取得效益值分別為wj和和pj(j=1n)。則依次求解。則依次求解f0(X)、f1(X)、.、fn(X)的過程中使用的遞推關(guān)系式為的過程中使用的遞推關(guān)系式為 _（6）_ 。lA. fA. fi i(X)=minf(X)=minfi-1i-1(X),f(X),fi-1i-1(X)+pi (X)+pi lB .