第3章動態(tài)規(guī)劃法

1、算法設計與分析1第三章動態(tài)規(guī)劃學習要點學習要點理解動態(tài)規(guī)劃算法的概念。掌握動態(tài)規(guī)劃算法的基本要素 （1）最優(yōu)子結構性質 （2）重疊子問題性質理解動態(tài)規(guī)劃算法與貪心算法的差異掌握設計動態(tài)規(guī)劃算法的步驟。通過下面的應用范例學習動態(tài)規(guī)劃算法設計策略（1）最短路徑（2）矩陣連乘（3）凸多邊形最優(yōu)三角剖分（4）最長公共子序列算法設計與分析2算法設計與分析3問題的分解 n將待求解問題分解為若干子問題，通過子問題的解得到原問題的解，這是問題求解的有效途徑。但是如何實施分解？n分治策略的基本思想是將規(guī)模為n的問題分解為k個規(guī)模較小的子問題，各子問題相互獨立但與原問題求解策略相同。并不是所有問題都可以這樣處理。

2、n問題分解的另一個途徑是將求解過程分解為若干階段（級），依次求解每個階段即得到原問題的解。通過分解得到的各子階段不要求相互獨立，但希望它們具有相同類型，而且前一階段的輸出可以作為下一階段的輸入。這種策略特別適合求解具有某種最優(yōu)性質的問題。n貪心法屬于這類求解策略：對問題P(n)，其求解過程中各貪心選擇步驟構成決策序列D=。Di的最優(yōu)性僅依賴于D1,D2,.Di-1。貪心法不保證決策序列D最后求出解的最優(yōu)性。算法設計與分析4動態(tài)規(guī)劃 n動態(tài)規(guī)劃也是一個分階段判定決策過程，其問題求解策略的基礎是決策過程的最優(yōu)原理：為達到某問題的最優(yōu)目標T，需要依次作出決策序列D=。如果D是最優(yōu)的，則對任意i(1i

3、k)，決策子序列Di+1,Dk也是最優(yōu)的，即當前決策的最優(yōu)性取決于其后續(xù)決策序列的是否最優(yōu)。由此追溯至目標，再由最終目標決策向上回溯，導出決策序列 D=，因此動態(tài)規(guī)劃方法可以保證問題求解是全局最優(yōu)的。n也可以這樣理解：如果求最優(yōu)解的問題可以劃分成若干段（級），那么最后求得的最優(yōu)解是由各個部分解所組成，而這些部分解一定是對應階段的最優(yōu)解。算法設計與分析5最短路徑 n給定簡單有向連通賦權圖G=，w(i,j)是G中邊的權。頂點集V可以劃分為k+1個兩兩不交的子集Vi，i =0,1,2,.k。其中V0=s，Vk=t。對G中任一邊，存在Vi、Vi+1，使得u屬于Vi，v屬于Vi+1，其中0ik。稱G為k

4、段圖，s點為起點，t為終點。n在G中求s出發(fā)到t的最短路徑。這里最短是指s到t的路徑上各邊權的和最小。 算法設計與分析6一個多段圖例子 記D(u,v)是G中起點為u,終點為v的最短路徑，C(u,v)是該路徑上各邊權的和。設D(s,t)= ，vir屬于Vr（r=1,2.k-1），則D(vi1,t)= 是從vi1出發(fā)到t的最短路徑，D(vi2,t)= 是從vi2出發(fā)到t的最短路徑等等。設u屬于Vi，有：C(u,t)=minw(u,v)+C(v,t) (4.1) vVi+1 階段4: C(7,t)=w(7,t)=8，C(8,t)=w(8,t)=4階段3: C(4,t)=minw(4,7)+C(7,t

5、), w(4,8)+C(8,t)=12 C(5,t)=minw(5,7)+C(7,t), w(5,8)+C(8,t)=10 C(6,t)=minw(6,7)+C(7,t), w(6,8)+C(8,t)=8階段2: C(1,t)=minw(1,4)+C(4,t), w(1,5)+C(5,t)=19 C(2,t)=minw(2,4)+C(4,t), w(2,5)+C(5,t), w(2,6)+C(6,t)=17 C(3,t)=minw(3,5)+C(5,t), w(3,6)+C(6,t)=13階段1: C(s,t)=minw(s,1)+C(1,t), w(s,2)+C(2,t), w(s,3)+C

6、(3,t)=16沿求解中帶下劃線的項回溯，得最短路徑解：D(s,t)= 算法設計與分析7問題解決關鍵n求解過程中起到關鍵作用的是公式(4.1)，它給出了求該問題最優(yōu)解的基本性質：原始問題最優(yōu)解與子問題的最優(yōu)解存在遞歸關系，稱這種關系為問題的最優(yōu)子結構。最優(yōu)子結構。最優(yōu)子結構為構造求解問題的最優(yōu)決策序列提供了重要線索，它提示可以自底向上的方式逐次由子問題最優(yōu)解構造原始問題的最優(yōu)解。n公式(4.1)還有一個重要特征：由給出的自頂向下的遞歸分解中，每次產(chǎn)生的子問題求解的關鍵（例如，求C(v,t)）與原問題是類似的，只是在相對較小的子問題空間中考慮問題的解，因此子問題與原始問題存在相似性相似性。而且這

7、些子問題的解在不同的上一級問題中都需要用到，這種特征可以稱為子問題重疊子問題重疊。 算法設計與分析8n采用鄰接矩陣表示圖G，其中wij為G中邊的權，如果不是G的邊, 則wij=。G的節(jié)點集V=0,1,2,n，其中V0=0是起始點集，Vk=n是終點集，V0,V1,Vk中各子集非空、兩兩不交。設V1=1，2，.r1，V2= r1+1，r1+2， r2，Vk-1= rk-2+1，rk-2+2，. (n-1)。n【算法3-1】MultiStage_Graph S1: 初始化：j=n-1；對i=0,1,n，ci=0； / ci為節(jié)點i到終點n的最短路徑長S2: 求節(jié)點r，使得wjr+cr=minwji+

8、ci|是G的邊; /按照V0,V1,Vk對節(jié)點的標記，ji。S3: cj=wjr+cr, Dj=r; / Dj=r 表示邊是從j出發(fā)到n的最短路徑上第1條邊 S4: j=j-1;S5: 如果j0則轉S2;S6: 輸出從源點0出發(fā)的最短路徑長c0 ；p0=0, pk=n;S7: 對j=1,2,k，pj=Dpj-1; /最短路徑Path=算法設計與分析9MultiStage_Graph算法復雜度nG用鄰接矩陣表示，對于S2到S5的主循環(huán)執(zhí)行n次。為求滿足wjr+cr=minwji+ci|是G的邊的r，最多要求n-1次比較。因此時間復雜性為O(n2)。除輸入G，輸出P外，要求附加存儲空間c、D。n如

9、果G采用鄰接表表示，求滿足最小性的節(jié)點r僅對屬于G的邊訪問一次，此算法的時間復雜性應該為O(n+e)（e為G的邊數(shù)）。n一般地，為避免遞歸過程中的重復計算，每個子問題首次處理時將結果保存以備查。在上面的過程中，每一次求得的cj都必須記錄下來。 算法設計與分析10從源點往后推n算法4-1完全是從匯點往前推，實際上我們也可以用同樣的思想，從源點出發(fā)往后推。 階段1: C(s,1)=w(s,1)=4， C(s,2)=w(s,2)=2, C(s,3)=w(s,3)=3階段2: C(s,4)=minw(1,4)+C(s,1), w(2,4)+C(s,2)=min14,8= 8C(s,5)=minw(1,

10、5)+C(s,1), w(2,5)+C(s,2), w(3,5)+C(s,3) =min13,9,6= 6C(s,6)=minw(2,6)+C(s,2), w(3,6)+C(s,3)=min12,11= 11階段3: C(s,7)=minw(4,7)+C(s,4), w(5,7)+C(s,5), w(6,7)+C(s,6) =min12,15,16= 12C(s,8)=minw(4,8)+C(s,4), w(5,8)+C(s,5), w(6,8)+C(s,6) =min16,12,15= 12階段4: C(s,t)=minw(7,t)+C(s,7), w(8,t)+C(s,8)=min20,1

11、6= 16算法設計與分析11MultiStage_Graph2() /*用用Ck來記錄到達每一個結點的最短距離來記錄到達每一個結點的最短距離, m是劃分的段數(shù)是劃分的段數(shù),Vk表表示到達了哪一段示到達了哪一段 */ C01=0; for (k=1;k=m;k+) for( i=1; i=Vk中結點的數(shù)目中結點的數(shù)目;i+) /*本循環(huán)求第本循環(huán)求第K段中所有頂點到段中所有頂點到S的最短路徑的最短路徑*/ current=MAX; /*對于對于K段中的一個點段中的一個點i，求出，求出K-1段中所有的點到它的距離，記錄下段中所有的點到它的距離，記錄下從原點出發(fā)最短的那一個從原點出發(fā)最短的那一個*/

12、 for(j=1;j=Vk-1中結點的數(shù)目中結點的數(shù)目;j+) r =d(Vki,Vk-1j)+Ck-1j; if (r current) rec=j; current= r ; Cki=current; 將結點將結點Vki指向結點結點指向結點結點Vk-1rec; 從從T到到S沿沿VK逆向輸出；逆向輸出； 算法設計與分析12圖中任意兩點間的最短距離n如果上面的圖不是分段圖，仍然可以用此方法來求圖中任意兩點間的最短路徑，這就是大名鼎鼎的Floyd算法。程序段如下： n for (k=1;k=vtxnum;k+) for (i=1; i=vtxnum;i+) for (j=1; j=vtxnum;

13、j+) if (lengthik+lengthkjlengthij) lengthij=lengthik+lengthkj; pathi,j=pathi,k+pathk,j; 算法設計與分析13矩陣連乘問題n給定n個矩陣：A1, A2, , An，其中Ai與Ai+1是可乘的。確定一種連乘的順序，使得矩陣連乘的計算量為最小。n設A和B分別是pq和qr的兩個矩陣，則乘積C=AB為pr的矩陣，計算量為pqr次數(shù)乘。n但是對于多于2個以上的矩陣連乘，連乘的順序卻非常重要，因為不同的順序的總計算量將會有很大的差別。算法設計與分析14不同計算順序的差別n設矩陣A1, A2和A3分別為10100, 1005

14、和550的矩陣，現(xiàn)要計算A1A2A3 。n若按(A1A2)A3)來計算，則需要的數(shù)乘次數(shù)為101005 + 10550 = 7500n若按(A1(A2 A3)來計算，則需要的數(shù)乘次數(shù)為100 5 50+ 1010050 = 75000n后一種計算順序的計算量竟是前者的10倍！n所以，求多個矩陣的連乘積時，計算的結合順序是十分重要的。算法設計與分析15不同計算順序的數(shù)量n設n個矩陣的連乘積有P(n)個不同的計算順序。n先在第k個和第k+1個矩陣之間將原矩陣序列分成兩個矩陣子序列，k=1,n；再分別對兩個子序列完全加括號，最后對結果加括號，便得到原序列的一種完全加括號方式。n由此可得出關于P(n)

15、的遞歸式：P(n) = n = 1n1P(k) P(nk) n1k=1 n解此遞歸方程可得P(n) = C(n1)，其中C(n) = 1n+12n n= (4n/n3/2)n所以P(n)隨n的增長呈指數(shù)增長。因而窮舉搜索法不是有效的算法。算法設計與分析16分解最優(yōu)解的結構n將矩陣連乘積AiAi+1Aj記為Ai: j。n若A1: n 的一個最優(yōu)解是在矩陣Ak和Ak+1處斷開的，即A1: n = (A1: k Ak+1: n)，則A1: k和Ak+1: n也分別是最優(yōu)解。n事實上，若A1: k的一個計算次序所需計算量更少的話，則用此計算次序替換原來的次序，則得到A1: n一個更少的計算量，這是一個

16、矛盾。同理Ak+1: n也是最優(yōu)解。n最優(yōu)子結構性質：最優(yōu)解的子結構也最優(yōu)的。最優(yōu)子結構性質：最優(yōu)解的子結構也最優(yōu)的。算法設計與分析17建立遞歸關系n令mij , 1i, jn，為計算Ai, j 的最少數(shù)乘次數(shù)，則原問題為m1n。n當i = j時，Ai, j為單一矩陣， mij = 0；n當ij時，利用最優(yōu)子結構性質有： mij = minmik + mk+1j + pi1pkpjikj其中矩陣Ai (1in)的維數(shù)為pi1pi。n根據(jù)此遞歸式就可以直接用遞歸程序來實現(xiàn)。算法設計與分析18直接遞歸的時間復雜性n根據(jù)前面的遞歸式不難得出的時間復雜性為 n1(T(k) + T(nk) + 1) k

17、=1 T(n) n1 = (n 1) +(T(k) + T(nk) k=1 n1 n1 = (n-1) +T(k) + T(nk) k=1 k=1 n可用數(shù)學歸納法證明T(n)2n1 = (2n)。 n直接遞歸算法的時間復雜性隨n的指數(shù)增長。 n1 = n + 2T(k) k=1 算法設計與分析19直接遞歸中有大量重復計算n直接遞歸中有大量重復計算，如A1: 4計算中：1: 41: 12: 41: 23: 41: 34: 42: 23: 42: 34: 41:12: 23: 34: 41: 12: 31: 23: 33: 34: 42: 23: 32: 23: 31: 12: 2圖中紅框標出的

18、都是重復計算。算法設計與分析20消除重復的計算n要消除重復計算，可在計算過程中保存已解決的子問題的答案。這樣，每個子問題只計算一次，而在后面需要時只要簡單查一下，從而避免重復計算。n計算方式可依據(jù)遞歸式自底向上地進行。n注意到在此問題中，不同的有序對 (i, j)就對應不同的子問題，因此不同的子問題個數(shù)最多只有Cn2+ n = (n2)個。n這樣便可以得到多項式時間的算法。算法設計與分析21自底向上的計算n例如對于A1A2A3A4，依據(jù)遞歸式以自底向上的方式計算出各個子問題，其過程如下：m11m22m33m44m12m23m34m13m24m14其中mii = 0mii+1 = pi1pipi

19、+1mij = minikj mik+mk+1j+pi1pkpj例如： m13 = min m11+m23+p0p1p3m12+m33+p0p2p3算法設計與分析22消除重復的矩陣連乘算法nInt MatrixChain(int *p, int n, int *m, int *s)n for (int i = 1; i = n; i+) mii = 0; n /將對角線元素賦值為零，即單個矩陣計算量為0n for (int r = 2; r = n; r+) /r為連續(xù)相乘矩陣的個數(shù)n for (int i = 1; i = n r +1; i+) n int j = i + r 1;n(5)

20、 mij = mi+1j + pi1*pi*pj;n /計算Ai, j = Ai: i Ai+1: jn sij = i; /記下斷點in(7) for (int k = i + 1; k j; k+) n int t = mik + mk+1j + pi1*pk*pj; n /對ikj, 逐個計算Ai, j = Ai: k Ak+1: jn if (t mij) mij = t; sij = k;n /記下較小的mij及相應的斷點k nnreturn(m1n);第(5)步與第(7)步能否合在一起?能。此處分開是為了給mij賦初值。算法設計與分析23MatrixChain的運行舉例 設要計算矩

21、陣連乘積A1A2A3A4A5A6，其維數(shù)分別為3035, 3515, 155, 510, 1020, 2025, 即p0=30, p1=35, p2=15, p3=5, p4=10, p5=20, p6=25。 MatrixChain用矩陣mij, sij存放子問題Ai: j的最小計算量以及相應的斷點。123456 1 2 3 4 5 6mij1234561 2 3 4 5 6sijMatrixChain將如下面紅色箭頭所示的過程逐個計算子問題Ai: j：執(zhí)行for (int i = 1; i = n; i+) mii = 0后將對角線元素全部置零，即子問題Aii = 0。000000當r=2

22、，執(zhí)行第(5)句完成了相鄰矩陣Aii+1=pi1*pi*pj 的計算，并在sij中添入了相應的斷點。其中的第(7)句因為j = i+1(k=i+1)而被跳過去了，實際并沒有執(zhí)行。1575026257501000500012345當r=3，i=1時，執(zhí)行第(5)句計算A1:12:3， m13 = m23 + p0*p1*p3 = 2625 +30*35*5 = 787578751執(zhí)行第(7)句計算A1:23:3， t = m12 + m33 + p0*p2*p3 = 15750+0+35*15*5 = 183757875，所以m13不變，斷點仍為1。當r=3，i=2時，執(zhí)行第(5)句計算A2:2

23、3:4，m24 = m34 + p1*p2*p4 = 750 +35*15*10 = 600060002執(zhí)行第(7)句計算A2:34:4， t = m23+m44+ p1*p3*p4 = 2625+0+35*5*10 = 43756000，所以m24改為4375，斷點改為3。43753當r=3，i=3時，執(zhí)行第(5)句計算A3:34:5，m35 = m45 + p2*p3*p5 = 1000 +15*5*20 = 250025003執(zhí)行第(7)句計算A3:45:5， t = m34+m55+ p2*p4*p5 = 750+0+15*10*20 = 37502500，所以m35仍為2500，斷點

24、仍為3。當r=3，i=4時，執(zhí)行第(5)句計算A4:45:6，m46 = m56 + p3*p4*p6 = 5000 +5*10*25 = 625062504執(zhí)行第(7)句計算A4:56:6， t = m45+m66+ p3*p5*p6 = 1000+0+5*20*25 = 35006250，所以m46改為3500，斷點改為5。35005類似的，當r=4、5、6時，可以計算出相應的mij及其相應的斷點sij，如下圖中所示：937537125353753118753105003151253由m16=15125可知這6個矩陣連乘積的最小運算次數(shù)為15125。由s16 = 3可知A1: 6的最優(yōu)計算

25、次序為A1: 3 A4: 6；由s13=1可知A1: 3的最優(yōu)計算次序為A1: 1 A2: 3；由s46=5可知A4: 6的最優(yōu)計算次序為A4: 5 A6: 6；因此最優(yōu)計算次序為：(A1(A2A3)(A4A5)A6)。算法設計與分析24MatrixChain的時間復雜性n算法MatrixChain的主要計算取決于程序中對r、i和k的三重循環(huán)。循環(huán)體內(nèi)的計算量為O(1)，1 r、i、kn，三重循環(huán)的總次數(shù)為O(n3)。因此該算法時間復雜性的上界為O(n3)，比直接遞歸算法要有效得多。算法使用空間顯然為O(n2)。n這種算法稱為動態(tài)規(guī)劃。算法設計與分析25動態(tài)規(guī)劃的基本思想n將原問題分解為若干個

26、子問題，先求子問題的解，然后從這些子問題的解得到原問題的解。n這些子問題的解往往不是相互獨立的。在求解的過程中，許多子問題的解被反復地使用。為了避免重復計算，動態(tài)規(guī)劃算法采用了填表來保存子問題解的方法。n在算法中用表格來保存已經(jīng)求解的子問題的解，在算法中用表格來保存已經(jīng)求解的子問題的解，無論它是否會被用到。當以后遇到該子問題時無論它是否會被用到。當以后遇到該子問題時即可查表取出其解，避免了重復計算。即可查表取出其解，避免了重復計算。算法設計與分析26動態(tài)規(guī)劃的基本要素n最優(yōu)子結構：問題的最優(yōu)解是由其子問題的最優(yōu)解所構成的。n重疊子問題：子問題之間并非相互獨立的，而是彼此有重疊的。最優(yōu)子結構性質

27、使我們能夠以自底向上的方式遞歸地從子結構的最優(yōu)解構造出問題的最優(yōu)解。因為子問題重疊，所以存在著重復計算。這樣就可以用填表保存子問題解的方法來提高效率。27動態(tài)規(guī)劃與貪心算法的比較n相同點： 都具有最優(yōu)子結構性質。n不同點： 貪心算法具有貪心選擇性質；動態(tài)規(guī)劃算法具有子問題重疊性，子問題空間??； 動態(tài)規(guī)劃算法通常以自底向上自底向上的方式解各子問題；貪心算法則通常以自頂向下自頂向下的方式進行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。n可用貪心算法時，動態(tài)規(guī)劃方法可能不適用；n可用動態(tài)規(guī)劃方法時，貪心算法可能不適用。算法設計與分析28動態(tài)規(guī)劃的基本方法n動

28、態(tài)規(guī)劃通?？梢园匆韵聨讉€步驟進行：n(1)找出最優(yōu)解的性質，并刻畫其結構特征；n(2)遞歸地定義最優(yōu)值；n(3)以自底向上的方式計算出各子結構的最優(yōu)值并添入表格中保存；n(4)根據(jù)計算最優(yōu)值時得到的信息，構造最優(yōu)解。n步驟13是動態(tài)規(guī)劃算法的基本步驟。若需要最優(yōu)解，則必須執(zhí)行第4步，為此還需要在第為此還需要在第3步中記錄構造最優(yōu)解所必需的信息步中記錄構造最優(yōu)解所必需的信息。算法設計與分析29凸多邊形最優(yōu)三角剖分n凸多邊形的三角剖分是將一個凸多邊形分割成互不相交的三角形的弦的集合T。n下面是一個凸7邊形的2個不同的三角剖分：v0v1v2v3v4v5v6v0v1v2v3v4v5v6n在凸多邊形的一

29、個三角剖分T中，各弦互不相交，且T已達到最大，即任何一條不在T中的弦必與T中某弦相交。n在有n個頂點的凸多邊形的三角剖分中，恰有n3條弦和n2個三角形。n凸多邊形的最優(yōu)三角剖分問題：給定凸多邊形P=v0, v1, vn1 ，以及定義在由凸多邊形的邊和弦組成的三角形上的權函數(shù)w。要求確定該凸多邊形的一個三角剖分，使得該剖分中諸三角形上權之和為最小。n可定義三角形上各種各樣的權函數(shù)w。n例如w(vivjvk) = |vivj| + |vjvk| + |vkvi|，其中|vivj|是點vi到vj的歐氏距離。相應于此權函數(shù)的最優(yōu)三角剖分即為最小弦長三角剖分。算法設計與分析30三角剖分與矩陣連乘積同構n

30、三角剖分問題和矩陣連乘積問題都對應于一個完全二叉樹，也稱為表達式的語法樹。0123A1A44A2A3A5A6(A1(A2A3)(A4(A5A6)所對應的二叉樹v1v0v2v3v4v5v6012A13A2A3A44A5A6凸多邊形v0v1v2v3v4v5v6一個三角剖分所對應的二叉樹nn個矩陣連乘積計算順序同構于n個葉子的完全二叉樹，凸(n+1)邊形三角剖分同構于n個葉子的完全二叉樹，所以n個矩陣連乘積的計算順序問題同構于凸(n+1)邊形的三角剖分問題。n事實上，矩陣連乘積最優(yōu)計算順序問題相當于是凸多邊形最優(yōu)三角剖分問題中一種特殊定義的權函數(shù)的情形。算法設計與分析31最優(yōu)子結構性質n能應用動態(tài)規(guī)

31、劃求解的問題應具有最優(yōu)子結構性質。凸多邊形最優(yōu)三角剖分問題具有最優(yōu)子結構性質。n事實上，若凸(n+1)邊形P=v0, v1, vn的一個最優(yōu)三角剖分T包含了三角形v0vkvn，1kn，則T的權為三角形v0vkvn、多邊形v0, v1, vk 和多邊形vk, vk+1, vn的權之和。顯然這兩個子多邊形的三角剖分也是最優(yōu)的。n因為，其中若有一個子多邊形的三角剖分不是最優(yōu)的將導致T不是最優(yōu)三角剖分的矛盾。算法設計與分析32最優(yōu)三角剖分的遞歸結構n定義tij, 1ijn, 為子多邊形vi1, vi, vj的最優(yōu)三角剖分所對應的權函數(shù)值，并為方便起見，設退化的多邊形vi1, vi的權值為0。n于是凸(

32、n+1)邊形的最優(yōu)三角剖分為t1nn易知，tij可遞歸定義為n當i = j時，為退化多邊形vi1, vi，tij = 0；n當ij時，利用最優(yōu)子結構性質有： tij = mintik + tk+1j + w(vi1vkvj)ikj與矩陣連乘積問題相對比： mij = minmik + mk+1j + pi1pkpjikjn顯然，矩陣連乘積的最優(yōu)計算順序與凸多邊形最優(yōu)三角剖分具有完全相同的遞歸結構。算法設計與分析33最優(yōu)三角剖分的算法n由于凸多邊形最優(yōu)三角剖分與矩陣連乘積的最優(yōu)計算順序具有完全相同的遞歸結構，其區(qū)別僅在于權函數(shù)的不同，所以只需要修改求矩陣連乘積的最優(yōu)計算順序的算法中的權函數(shù)計算便

33、可得到凸多邊形最優(yōu)三角剖分的算法。n顯然該算法的時間復雜性也是O(n3)。nVoid MinWeightTriangulation(int n, Type *t, int *s)n for (int i = 1; i = n; i+) tii = 0; n for (int r = 2; r = n; r+) n for (int i = 1; i = n r +1; i+) n int j = i + r 1;n tij = ti+1j + w(i1, i, j);n sij = i; n for (int k = i + 1; k j; k+) n int u = tik + tk+1j

34、+ w(i1, k, j); n if (u tij) tij = u; sij = k;n /程序中紅色的部分為改動的地方算法設計與分析34最長公共子序列n給定序列A=，B=。如果存在A的子序列A1=(i1i2ir)和B的子序列B1=(j1j2jr)，使得aik=bjk(k=1,2,.r)，則稱C=A1=B1為序列A、B的一個公共子序列。nA,B的長度最大公共子序列稱為A,B的最長公共子序列。n例如：A=，B=，C1=是A、B的一個公共子序列，但不是最長子序列。C2=和C3=都是A、B的最長子序列。n注意：這里的子序列對于原序列而言不一定是連續(xù)的。 算法設計與分析35求最長公共子序列n對A=

35、，B= 求序列A、B的最長公共子序列的最直接方法是對A的所有子序列逐個檢查是否為B的子序列，并且在檢查過程中記錄最長子序列。nA的每個子序列對應下標集1,2,.n的一個子集，因此遍歷所有A的不同子序列要求的時間復雜性為O(2n)。n顯然這不是一個有效的方法。算法設計與分析36最長公共子序列性質n對長度為n的序列S=，記Sr= (r=n，Sn=S)。n如果C=是A、B的一個最長公共子序列，則C必為如下三種情況之一：1） 如果an=bm，則cr= an=bm ，即Cr-1是An-1和Bm-1的最長公共子序列；2） 如果anbm且cr an，則C是An-1和B的最長公共子序列；3） 如果anbm且c

36、r bm，則C是A和Bm-1的最長公共子序列；n即兩個序列的最長公共子序列包含了這兩個序列前綴的最長公共子序列。 算法設計與分析37最長公共子序列的遞歸結構n以LCS(A,B)表示序列A、B的最長公共子序列，求LCS(A,B)的遞歸結構如下： 其他或者cba0j0i)B,LCS(A),B,maxLCS(Ac)B,A(LCS)B,A(LCSji1 - jij1i1j1ijin表示空，|表示在子序列尾部添加一個元素。n計算A、B的最長公共子序列可能要求計算A、Bm-1的公共最長子序列或者An-1、B的公共最長子序列，而這兩個子問題又都包含求An-1、Bm-1的公共最長子序列。n以len(i,j)表

37、示LCS(Ai,Bj)的長度有： 算法設計與分析38求最長公共子串長度的算法int LCSlength(char *a,char *b,int *len,int *flag)/a、b是輸入字符串，輸出數(shù)組是輸入字符串，輸出數(shù)組len的元素的元素lenij記錄記錄len(i,j)，/數(shù)組數(shù)組flag在求在求a、b的最長公共子序列時作為標志使用。的最長公共子序列時作為標志使用。/flagij=0：表示：表示LCS(ai,bj)= LCS(ai-1,bj-1)|ai，ai=bj;/ flagij=1：表示：表示LCS(ai,bj)= LCS(ai-1,bj);/ flagij=-1:表示表示LCS(

38、ai,bj)= LCS(ai,bj-1);n=strlen(a); m=strlen(b);for(i=1;i=n;i+) leni0=0; for(i=1;i=m;i+) len0i=0;for(i=1;i=n;i+) for(j=1;j=lenij-1) lenij=leni-1j; flagij=1; else lenij=lenij-1; flagij=-1; return(lennm);算法設計與分析39求最長公共子串的算法n根據(jù)根據(jù)LCSlength()輸出的標志數(shù)組輸出的標志數(shù)組flag和最長公共子串的和最長公共子串的長度值長度值lennm，按照公式可以得到子字符串，按照公式可以

39、得到子字符串a(chǎn)i、bj的最的最長公共子串長公共子串c：n求求c=LCS(ai,bj) void LCS0(int i,int j,char *a,int k,int *flag,chr *c)/k是當前最長公共子串長度，數(shù)組是當前最長公共子串長度，數(shù)組flag由由LCSlength()得到得到if (i= =0)|(j= =0) return; if (flagij= =0) LCS0(i-1,j-1,a,k-1,flag,c); ck-1=ai; else if (flagij= =1) LCS0(i-1,j,a,k,flag,c); else LCS0(i,j-1,a,k,flag,c);

40、算法設計與分析40LCS算法運行舉例設A=d,b,a,d,b，B=b,a,b,d LCS用矩陣lenij,flagij存放子問題Ai與Bj 的最長公共子串長度和相應的標志012345 0 1 2 3 4 12345 1 2 3 4 lenijflagijLCSlength將如下面紅色箭頭所示的過程逐個計算子問題執(zhí)行for(i=0;i=m;i+) leni0=0; for(i=0;i=m;i+) len0i=0;后完成初始化如下：0000000000當i=1，依次比較A1與Bj及l(fā)en0j與len1j-1，填入len1j與flag1j的值如下： A1B1且len01=len10， len11=l

41、en01=0; flag11=1;01 A1B2且len02=len11， len12=len02=0; flag12=1;010 A1B3且len03=len12， len13=len03=0; flag13=1;1 A1=B4 ， len14=len03+1=1; flag14=0;10當i=2，依次比較A2與Bj及l(fā)en1j與len2j-1，填入len2j與flag2j的值如下： A2=B1 ， len21=len10+1=1; flag21=0;10 A2B2 且len12len21; len22=len21=1; flag22= -1;1-1 A2=B3; len23=len12+1

42、=1; flag23= 0;10 A2B4且len14bk時，k=k+1,bk=ai當aibk時，k不變，更新b1:k若aib1,則b1=ai;否則找到j,滿足bj-1aibj，修改bj=ai;n用bi記錄以ai,0in為結尾元素的最長遞增子序列的長度，則序列a的遞增最長子序列的長度為 。n遞歸定義bi為： 算法設計與分析47max0ibni100max0kbibbiakaik作業(yè)：n3-1 設計一個O(n2)時間的算法，找出由n個數(shù)組成的序列的最長單調遞增子序列。n3-5 給定n種物品和一背包。物品i的重量是wi，體積是bi，其價值為vi，背包的容量為c，容積為d。問應如何選擇裝入背包中的物

43、品，使得裝入背包中物品的總價值最大？在選擇裝入背包的物品時，對每種物品i只有兩種選擇，即裝入或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i。試設計一個解此問題的動態(tài)規(guī)劃算法，并分析算法的計算復雜性。算法設計與分析48算法設計與分析49多邊形游戲(自學)n有一個n邊形，每個頂點被賦予一整數(shù)值，每條邊上被賦予一個運算符“+”或“-”。n游戲的第1步，將一條邊刪去；n隨后的n1步按以下方式操作：n(1)選擇一條邊e及其所連接的兩個頂點v1和v2；n(2) 用一個新頂點取代邊e以及頂點v1和v2，賦予新頂點的值為頂點v1和v2的值通過邊e上的運算所得到的值。n最后所有的邊被刪去，所剩頂點的值即為得分算法設計與分析50多邊形游戲的表達n設所有的邊依次從1到n編號，按順時針序列為op1, v1, op2, v2, , opn, vn 其中opi為邊i上的運算符，vi為頂點i上的值。n將多邊形中始于頂點i (1in)，長度為j 的順時針鏈vi, opi+1, , vi+j1表示為p(i, j)。n若鏈p(i, j)最后一次合并在opi+s(1sj1)處發(fā)生，則被分割為兩個子鏈p(i, s)和p(i+s, js