1、12 學習要點學習要點:理解動態規劃算法的概念。掌握動態規劃算法的基本要素（1）最優子結構性質（2）重疊子問題性質掌握設計動態規劃算法的步驟。(1)找出最優解的性質，并刻劃其結構特征。(2)遞歸地定義最優值。(3)以自底向上的方式計算出最優值。(4)根據計算最優值時得到的信息，構造最優解。3通過應用范例學習動態規劃算法設計策略。（1）矩陣連乘問題；（2）最長公共子序列；（3）最大子段和（4）凸多邊形最優三角剖分；（5）多邊形游戲； （6）圖像壓縮；（7）電路布線；（8）流水作業調度；（9）背包問題；（10）最優二叉搜索樹。4n動態規劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問

2、題nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=5n但是經分解得到的子問題往往不是互相獨立的。不同子問題的數目常常只有多項式量級。在用分治法求解時，有些子問題被重復計算了許多次。nT(n)=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)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)6n如果能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，就可以避免大量重復計算，從而得到多項式時間算法。n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2

3、n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n)7n找出最優解的性質，并刻劃其結構特征。n遞歸地定義最優值。n以自底向上的方式計算出最優值。n根據計算最優值時得到的信息，構造最優解。8基本原理1、多階段最優化決策：、多階段最優化決策：即由初始狀態開始，通過對中間階段決策的選擇，達到結束狀態。這些決策形成了一個決策序列，同時確定了完成整個過程的一條最優的活動路線。9帶權有向的多段圖 上一階段的狀態下一階段的狀態決策10概念n狀態狀態（State）：表示事物的性質，是描述“動態規劃”中的“單元”的量。亦是每一階段求解過程的出發點。n階段階段

4、（Stage）：階段是一些性質相近，可以同時處理同時處理的狀態集合，或者說，階段只是標識那些處理方法相同、處理順序無關的狀態。n決策決策（Decision）：每個階段做出的某種選擇性的行動，是程序所需要完成的選擇。n狀態轉移方程：狀態轉移方程：是前一個階段的狀態轉移到后一個的狀態的演變規律，是關于兩個相鄰階段狀態變化的方程，是“動態規劃”的中心。設設 fk(i)k階段狀態i的最優權值，即初始狀態至狀態i的最優代價 fk+1(i)=minxk(j)+u(i,j) 11基本原理n最優性原理作為整個過程的最優策略，它滿足：相對前面決策所形成的狀態而言，余下的子策略必然構成“最優子策略”。無后效性原則

5、給定某一階段的狀態，則在這一階段以后過程的發展不受這階段以前各段狀態的影響，所有各階段都確定時，整個過程也就確定了。這個性質意味著過程的歷史只能通過當前的狀態去影響它的未來的發展，這個性質稱為無后效性。12超人的能量項鏈n超人有一串能量項鏈，每棵能量珠Ui的頭部和尾部分別具有能量pi和pi+1,前一能量珠的尾部能量等于后一能量珠的tou部能量，靠相鄰兩棵能量珠聚合為一棵能量珠釋放能量，如能量珠Ui（ pi*pi+1）和能量珠Ui+1（ pi+1*pi+2）可聚合為新能量珠，頭部能量為pi尾部能量為pi+2，釋放能量為pi*pi+1 *pi+2。n已知該項鏈的頭部能量數組為p1n,請計算該項鏈所

6、能釋放的最大能量13n例如：項鏈有四個能量珠，能量數組p 如下：p1=4,p2=5,p3=2,p4=8n則這四顆能量珠頭尾部能量分別為 （4，5）、（5，2）、（2，8）、（8，4）14n（U1 U2） U3） U4 釋放能量為釋放能量為4*5*2+4*2*8+4*8*4=232n（U1 U2） （ U3 U4 ） 釋放能量為釋放能量為4*5*2+2*8*4+4*2*4=136n（U1 （U2 U3） U4 釋放能量為釋放能量為5*2*8+4*5*8+4*8*4=368nU1 （ （U2 U3） U4） 釋放能量為釋放能量為5*2*8+5*8*4+4*5*4=320nU1 （ U2 （ U3

7、U4 ） ） 釋放能量為釋放能量為2*8*4+5*2*4+4*5*4=184lp1=4,p2=5,p3=2,p4=815得到項鏈的最大能量了嗎？n還沒有，因為這僅僅是項鏈在從U4和U1之間斷開的情況，項鏈還有其它三個可能的斷開位置： 從U1和U2之間斷開； 從U2和U3之間斷開； 從U3和U4之間斷開。167.4矩陣矩陣鏈相鏈相乘乘問題：給定問題：給定n個矩陣個矩陣A1,A2,An，其中，其中Ai與與A i+1是可乘的，是可乘的，i=1，2，n-1。如何確定計算矩陣。如何確定計算矩陣連乘積的計算次序，使得依此次序計算矩陣連乘積連乘積的計算次序，使得依此次序計算矩陣連乘積需要的數乘次數最少需要的

8、數乘次數最少17兩個矩陣相乘兩個矩陣相乘 若若A是一個是一個p*q矩陣，矩陣，B是一個是一個q*r矩陣，則其乘矩陣，則其乘積積C=AB是一個是一個p*r矩陣。矩陣。 for(i=1;i=p;i+) for(j=1;j=r;j+) cij=0; for(k=1;k=q;k+)cij+=aik*bkj; 總共需要總共需要pqr次數乘。次數乘。18三個矩陣相乘三個矩陣相乘 現有三個現有三個矩陣矩陣相乘：相乘： D ps = A pq B qr C rs我們知道矩陣相乘滿足結合率，即我們知道矩陣相乘滿足結合率，即(AB)C=A(BC)不同結合方法得到的結果是一樣的，然而計算量卻可不同結合方法得到的結果

9、是一樣的，然而計算量卻可能有很大差別。能有很大差別。19是否讓你吃驚？是否讓你吃驚？如：如： A 505 B 5100 C 10010 按按(AB)C計算，所需乘法次數為：計算，所需乘法次數為： 50 5 100 +50 100 10 =75000按按A(BC）計算，所需乘法次數為：）計算，所需乘法次數為：5 100 10 + 505 10=7500可見如何結合十分影響計算的效率，自然提可見如何結合十分影響計算的效率，自然提出了矩陣鏈相乘的最優計算次序問題出了矩陣鏈相乘的最優計算次序問題20u完全加括號的矩陣連乘積可遞歸地定義為：完全加括號的矩陣連乘積可遞歸地定義為：（1）單個矩陣是完全加括號

10、的；（2）矩陣連乘積 是完全加括號的，則 可 表示為2個完全加括號的矩陣連乘積 和 的乘積并加括號，即AABC)(BCA)(DBCA)(DCAB)(DBCA)(CDBA)(CDAB16000, 10500, 36000, 87500, 34500完全加括號的矩陣連乘積1050A4010B3040C530Du設有四個矩陣設有四個矩陣 ，它們的維數分別是：，它們的維數分別是：DCBA , , ,則有五種完全加括號方式：則有五種完全加括號方式：21矩陣連乘問題n給定給定n n個矩陣個矩陣 ， 其中其中 與與 是可乘是可乘的，的， ?？疾爝@。考察這n n個矩陣的連乘積個矩陣的連乘積 ,.,21nAAA

11、iA1iA1,.,2 , 1ninAAA.21l由于矩陣乘法滿足結合律，所以計算矩陣的連乘由于矩陣乘法滿足結合律，所以計算矩陣的連乘可以有許多不同的計算次序。這種計算次序可以可以有許多不同的計算次序。這種計算次序可以用加括號的方式來確定。用加括號的方式來確定。若一個矩陣連乘積的計算次序完全確定，也就是若一個矩陣連乘積的計算次序完全確定，也就是說該連乘積已完全加括號，則可以依此次序反復調說該連乘積已完全加括號，則可以依此次序反復調用用2 2個矩陣相乘的標準算法計算出矩陣連乘積個矩陣相乘的標準算法計算出矩陣連乘積22矩陣連乘問題問題：給定問題：給定n個矩陣個矩陣A1,A2,An，其中，其中Ai與與

12、A i+1是可乘的，是可乘的，i=1，2，n-1。如何確定計算矩陣。如何確定計算矩陣連乘積的計算次序，使得依此次序計算矩陣連乘積連乘積的計算次序，使得依此次序計算矩陣連乘積需要的數乘次數最少需要的數乘次數最少23矩陣連乘問題u窮舉法窮舉法：列舉出所有可能的計算次序，并計算出每一種計算次序相應需要的數乘次數，從中找出一種數乘次數最少的計算次序。 算法復雜度分析：對于n個矩陣的連乘積，設其不同的計算次序為P(n)。由于每種加括號方式都可以分解為兩個子矩陣的加括號問題：(A1.Ak)(Ak+1An)可以得到關于P(n)的遞推式如下：)/4 ()(11)()(1)(2/ 311nnPnnknPkPnP

13、nnk24矩陣連乘問題u窮舉法窮舉法u動態規劃動態規劃將矩陣連乘積 簡記為Ai:j ，這里ij jiiAAA.1考察計算Ai:j的最優計算次序。設這個計算次序在矩陣Ak-1和Ak之間將矩陣鏈斷開，i kj，則其相應完全加括號方式為).)(.(111jkkkiiAAAAAA計算量：計算量： 的計算量加上的計算量加上 的計算的計算量，再加上量，再加上Ai:k-1和和Ak:j相乘的計算量相乘的計算量Ai).(11kiiAAA).(1jkkAAA25關于計算量關于計算量如：如：A 10100 B 1005 C 550 D 50100 按按(AB)(CD)計算，所需乘法次數為：計算，所需乘法次數為：1、

14、計算、計算AB 所需乘法次數：所需乘法次數：10100 5=50002、計算、計算CD 所需乘法次數：所需乘法次數： 550 100=250003、以上兩個結果矩陣、以上兩個結果矩陣(AB) 105和和(CD)5100再相乘的乘再相乘的乘法次數法次數: 105 100=5000故按故按(AB)(CD)計算，所需乘法次數為：計算，所需乘法次數為：5000+25000+5000=3500026規模為規模為4的情況的情況如：如：A1510 A2104 A346 A4 610 請給出計算請給出計算A1A2A3A4的最優計算次序的最優計算次序1、計算規模為、計算規模為2的子問題的子問題計算計算A1A2

15、所需乘法次數：所需乘法次數：510 4=200計算計算A2A3 所需乘法次數：所需乘法次數：104 6=240計算計算A3A4所需乘法次數：所需乘法次數： 4610=24027A1 510 A2 104 A3 46 A4 610 2、計算規模為、計算規模為3的子問題的子問題(1)計算計算A1A2A3所需乘法次數，有兩種結合方法所需乘法次數，有兩種結合方法: (A1A2)A3和和A1(A2A3),選最好的一種：選最好的一種： (A1A2)A3: 計算量：計算量：320(A1A2)A3: 計算計算A1A2的計算量的計算量+計算計算A1:2乘乘A3的計算量：的計算量：200+5 4 6=320A1(

16、A2A3): 計算計算BC的計算量的計算量+計算計算A1乘乘A2:3的計算量：的計算量：240+5 10 6=54028A1 510 A2 104 A3 46 A4 610 (2)計算計算A2A3A4所需乘法次數，有兩種結合方法所需乘法次數，有兩種結合方法:(A2A3)A4和和A2(A3A4)，選最好的一種：，選最好的一種： 計算計算A2A3的計算量的計算量+計算計算A2:3乘乘A4的計算的計算量：量：240+10 6 10=840A2(A3A4): 計算計算A3A4的計算量的計算量+計算計算A2乘乘A3:4的計算量：的計算量：240+10 4 10=640 A2(A3A4): 計算量：計算量

17、：64029A1 510 A2 104 A3 46 A4 610 3 計算規模為計算規模為4的原問題的原問題A1A2A3A4所需乘法次數，所需乘法次數，有三種結合方法有三種結合方法: ( A1A2A3)A4 、 (A1A2)(A3A4) 、 A1(A2A3A4 ) ，選最好的一種：，選最好的一種： ( A1A2A3)A4: 計算計算A1A2A3的的最小最小計算量計算量+計算計算（A1A2A3）乘）乘A4的計算量：的計算量：320+5 6 10=620(A1A2)(A3A4): 200+240+5 4 10=640A1(A2A3A4 ): 640 +5 10 10=1140( A1A2A3)A4

18、: 計算量：計算量：62030用數組元素用數組元素Cij來存儲來存儲計算計算Ai:j的最少數乘次數的最少數乘次數例例7.1：A1 510 A2 104 A3 46 A4 610 請給出計算請給出計算A1：4的最優計算次序的最優計算次序1、計算規模為、計算規模為2的子問題的子問題計算計算A1：2 所需乘法次數：所需乘法次數：510 4=200計算計算A2：3 所需乘法次數：所需乘法次數：104 6=240計算計算A3：4所需乘法次數：所需乘法次數： 4610=240將計算將計算Ai:j所需最小數乘次數存入數組所需最小數乘次數存入數組cij中中C12=200 C23=240 C34=24031A1

19、 510 A2 104 A3 46 A4 610 2、計算規模為、計算規模為3的子問題的子問題計算計算A1:3所需乘法次數，有兩種結合方法，選最好的所需乘法次數，有兩種結合方法，選最好的一種：一種： (A1:2)A3: 計算計算A1:2的計算量的計算量+計算（計算（A1:2）乘）乘A3的計算量：的計算量：200+5 4 6=320A1(A2:3): 計算計算A2:3的計算量的計算量+計算計算A1乘乘(A2:3)的的計算量：計算量：240+5 10 6=540 C13=32032A1 510 A2 104 A3 46 A4 610 計算計算A2:4所需乘法次數，有兩種結合方法，選最好所需乘法次數

20、，有兩種結合方法，選最好的一種：的一種： 840 (A2:3)A4: 計算計算A2:3的計算量的計算量+計算計算A2:3乘乘A4的計算量：的計算量：240+10 6 10=840A2(A3:4): 計算計算A3:4的計算量的計算量+計算計算A2乘乘(A3:4)的計算量：的計算量：240+10 4 10=640 C24=64033A1 510 A2 104 A3 46 A4 610 3 計算規模為計算規模為4的原問題的原問題A1:4所需乘法次數，有三種所需乘法次數，有三種結合方法，選最好的一種：結合方法，選最好的一種： ( A1:3)A4: 計算計算A1:3的的最小最小計算量計算量+計算（計算（

21、A1:3）乘乘A4的計算量：的計算量：320+5 6 10=620(A1:2)(A3:4): 200+240+5 4 10=640A1(A2:4 ): 640 +5 10 10=1140 C14=62034A1 510 A2 104 A3 46 A4 610 d=1d=2d=3d=4C1:1=0C1:2=200C1:3=320C2:2=0C2:3=240C2:4=640C3:3=0C3:4=240C4:4=035將例7.1中的中間結果存入數組C1:1=0C1:2=200C1:3=320C1:4=620C2:2=0C2:3=240C2:4=640C3:3=0C3:4=240C4:4=0d=1d=

22、2d=3d=436n特征：計算Ai:j的最優次序所包含的計算矩陣子鏈 Ai:k-1和Ak:j的次序也是最優的。舉例舉例n矩陣連乘計算次序問題的最優解包含著其子問題的最優解。這種性質稱為最優子結構性質最優子結構性質。問題的最優子結構性質是該問題可用動態規劃算法求解的顯著特征。分析最優解的結構37建立遞歸關系n設計算設計算Ai:j，1ijn，所需要的最少數乘次，所需要的最少數乘次數數ci,j，則原問題的最優值為，則原問題的最優值為c1,n n當當i=j時，時，Ai:j=Ai，因此，因此，ci,i=0，i=1,2,nn當當ij時，需找到一個分割點時，需找到一個分割點k,在在Ak前斷開：前斷開：(Ai

23、Ak-1)(AkAj),使使Ci,j達到最小達到最小這里 的維數為 1, 1,jkipppjkCkiCjiCiA1iipp38jipppjkCkiCjijiCjki, 1,min0,1jki 的位置只有 種可能kijl可以遞歸地定義可以遞歸地定義Ci,j為：為：39計算最優值n對于1ijn不同的有序對(i,j)對應于不同的子問題。因此，不同子問題的個數最多只有n由此可見，在遞歸計算時，許多子問題被許多子問題被重復計算多次重復計算多次。這也是該問題可用動態規劃算法求解的又一顯著特征。)(22nnn40動態規劃-自底向上進行計算 用動態規劃算法解此問題，可依據其遞歸式以用動態規劃算法解此問題，可依

24、據其遞歸式以自底向上的方式進行計算。在計算過程中，保存已自底向上的方式進行計算。在計算過程中，保存已解決的子問題答案。每個子問題只計算一次，而在解決的子問題答案。每個子問題只計算一次，而在后面需要時只要簡單查一下，從而避免大量的重復后面需要時只要簡單查一下，從而避免大量的重復計算，最終得到多項式時間的算法計算，最終得到多項式時間的算法41課堂練習(1)請給出計算請給出計算M1M2M3M4M5 乘積所需的最少數乘乘積所需的最少數乘次數（即次數（即C15 ） 。（2）請給出一個括號化表達式，使在這種次序下達）請給出一個括號化表達式，使在這種次序下達到乘法的次數最少。到乘法的次數最少。M1M2M3M

25、4M54553366445p1=4,p1=5,p3=3,p4=6,p5=4,p6=542C1:1=060132K=3180K=3C2:2=090132K=3C3:3=07272+3*4*5K=5C4:4=0120C5:5=0p1=4,p2=5,p3=3,p4=6,p5=4,p6=543C1:1=0C1:2=60C2:2=0C2:3=90C3:3=0C3:4=72C4:4=0C4:5=120C5:5=0p1=4,p1=5,p3=3,p4=6,p5=4,p6=544C1:1=0C1:2=60C1:3=132k=3C1:4=180k=3C2:2=0C2:3=90C2:4=132k=3C2:5=207

26、k=3C3:3=0C3:4=72C3:5=132k=5C4:4=0C4:5=120C5:5=02325450132 55 42 :)( , 536056512090 54 32 : )( , 42075351320 53 22 : )(, 3min 52 652543264254326325432pppCCMMMMkpppCCMMMMkpppCCMMMMkCp1=4,p1=5,p3=3,p4=6,p5=4,p6=52605440180 55 41 :5) 4321( , 5372564120132 54 31 : ) 54)(321( , 425253413260 53 21 : ) 543)

27、(21( , 33075542070 52 11 : ) 5432( 1, 2min 51 651641631621pppCCMMMMMkpppCCMMMMMkpppCCMMMMMkpppCCMMMMMkCC1:5=252k=345C1:1=0C1:2=60C1:3=132k=3C1:4=180k=3C1:5=252k=3C2:2=0C2:3=90C2:4=132k=3C2:5=207k=3C3:3=0C3:4=72C3:5=132k=5C4:4=0C4:5=120C5:5=0(M1M2)(M3M4)M5)46用動態規劃法求最優解void MatrixChain(int *p,int n,in

28、t *m,int *s) /m是最優值,s是最優值的斷開點的索引,n為題目所給的矩陣的個數(下面例子中)/矩陣段長度為1,則m中對角線的值為0,表示只有一個矩陣,沒有相乘的.for(int i = 1;i=n;i+) mii = 0; for(int r = 2;r=n;r+)/r表示矩陣的長度(2,3逐漸變長) for(int i = 1;i=n-r+1;i+) /從第i個矩陣Ai開始,長度為r,則矩陣段為(AiAj)int j = i+r-1;/當前矩陣段(AiAj)的起始為Ai,尾為Aj/求(AiAj)中最小的,其實k應該從i開始，但些處先記錄第一個值，k從i+1開始，這樣也可以。/例如

29、對(A2A4),則i=2,j=4,下面一行的m24=m34+p1*p2*p4,即A2(A3A4) mij = mi+1j + pi-1*pi*pj; sij = i;/記錄斷開點的索引47/循環求出(AiAj)中的最小數乘次數 for(int k = i+1 ; kj;k+)/將矩陣段(AiAj)分成左右2部分(左mik,右mk+1j), /再加上左右2部分最后相乘的次數(pi-1 *pk*pj) int t = mik + mk+1j + pi-1 *pk*pj; if(t 0) return mij; if (i = j) return 0; int u = LookupChain(i，i

30、) + LookupChain(i+1，j) + pi-1*pi*pj; sij = i; for (int k = i+1; k j; k+) int t = LookupChain(i，k) + LookupChain(k+1，j) + pi-1*pk*pj; if (t u) u = t; sij = k; mij = u; return u;53子串比較與概率算法子串比較與概率算法54兩個一維事物比較：n 相似 ： LCS算法n n比較 完全相等： 一一對應，概率算法 等 n 相等n 部分相等 ：模式匹配-KMP算法 55n應用：打字比賽（規則，中外區別）n SARS病毒n 文件比較等

31、等 n 兩個一維事物的比較n定義：與子串的區別n算法：窮舉法，動態規劃法n代碼實現：用C56若給定序列X=x1,x2,xm，則另一序列Z=z1,z2,zk，是X的子序列是指存在一個嚴格遞增下標序列i1,i2,ik使得對于所有j=1,2,k有：zj=xij。例如，序列Z=B，C，D，B是序列X=A，B，C，B，D，A，B的子序列，相應的遞增下標序列為2，3，5，7。而子串則要求左右兩元素在母串中為相鄰。給定2個序列X和Y，當另一序列Z既是X的子序列又是Y的子序列時，稱Z是序列X和Y的公共子序列公共子序列。給定2個序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最長公共子序列。 57窮

32、舉法:n若要求兩個序列X，Y的最長公共子序列，n先取得X，Y的所有子序列，并進行一一n比較，共有如下不同的組合：n共要進行不同的比較：2 m+nnnnnnmmmmmCCCCCC2.2.2121nm258設序列X=x1,x2,xm和Y=y1,y2,yn的最長公共子序列為Z=z1,z2,zk ，則(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的最長公共子序列。由此可見，2個序列的最長公共子序列包含了這2個序列的前綴的最長公共子序列。因此，最長公共子

33、序列問題具有最優子結最優子結構性質構性質。 59由最長公共子序列問題的最優子結構性質建立子問題最優值的遞歸關系。用cij記錄序列和的最長公共子序列的長度。其中， Xi=x1,x2,xi；Yj=y1,y2,yj。當i=0或j=0時，空序列是Xi和Yj的最長公共子序列。故此時Cij=0。其它情況下，由最優子結構性質可建立遞歸關系如下：jijiyxjiyxjijijicjicjicjic; 0,; 0,0, 01,1max1 11060由于在所考慮的子問題空間中，總共有(mn)個不同的子問題，因此，用動態規劃算法自底向上地計算最優值能提高算法的效率。 void LCSLength(char x, c

34、har y,int m，int n) /* 計算最長公共子序列的長度 */ int Lmn,i，j; for (i = 0; i = m; i+) Li0 = 0; for (i = 0; i = n; i+) L0i = 0; for (i = 1; i = m; i+) for (j = 1; j = Lij-1) Lij= Li-1j; else Lij= Lij-1; return Lmn;61舉例：填充表格i j012345601d2b3c4b5a6d7bbacdbd62從表中找出最長公共子序列的方法：n（1）從(m,n) 到 (0,0)n（2）若當前格與左邊一格相同，則畫“ ”;n

35、 若當前格與上邊一格相同，則畫“ ”;n 上兩者都不符合，從當前格到左上格畫“ ”n（3）從當前格向箭頭方向前進一格，對此格進行（2）n（4）從(m,n) 到 (0,0)的不同路徑中，“ ”相對應的格的元素構成最長公共子序列。63找出最長公共子序列i j01234560000000010000111d20111122b30112222c40112233b50122233a60122334d70122344bbacdbd（bcbd,bcdb,badb）64求最長公共子序列求最長公共子序列void LCS(char a,int L,int m,int n) /* 求最長公共子序列 */ int i

36、,j,k; char cm; i=m;j=n;k=m; do if(Lij=Li-1j) i-; else if(Lij=Lij-1) j-; else ck=aii; k-;i-;j-; while(i0&j0); printf(“%s”,c+k+1);時間復雜度為：m+n=O(n)65如果只需要計算最長公共子序列的長度，則算法的空間需求可大大減少。事實上，在計算cij時，只用到數組c的第i行和第i-1行。因此，用2行的數組空間就可以計算出最長公共子序列的長度。進一步的分析還可將空間需求減至O(min(m,n)。思考題：如何對程序進行改正，作為思考題。66子串比較：nG等搜索工具的目

37、的是從信息海洋中進行串匹配查找。n最著名的子串匹配算法是KMP算法。nKMP算法利用關鍵詞內部的相似特點，節省了時間復雜度：O（m+n)67概率算法：n我們重點學習概率算法，概率算法是非確定性算法，即每一步是隨機的。n經典問題1：生日問題n 有多少人在一起使得其中至少有兩個人生日相同的機會超過沒有人生日相同的機會。即有相同生日的機會概率超過1/2.n經典問題2：圓周率的計算n 祖沖之等，國外有投針法。68素數的概率判定算法素數的概率判定算法n判定所給自然數n是否是素數？n意義：密碼學，計算機測試等 n素數特點：分布稀疏 10 4 共有1229個。 10 8 共有5761455個。n設(x)為小

38、于或等于x的全部素數個數，則n即： (x) x/ln x1ln/)(limxxxxxxln69定理(Wilson):n(Wilson): n是素數的充要條件是：n（n-1）！ -1 mod nn若p素數，則對于任意的整數a ,p a,應有na p-1 1 mod p70Miller測試n若n是素數，b是正整數，且n b ，則n必然通過以 b 基的 Miller測試。71用多邊形頂點的逆時針序列表示凸多邊形，即P=v0,v1,vn-1表示具有n條邊的凸多邊形。若vi與vj是多邊形上不相鄰的2個頂點，則線段vivj稱為多邊形的一條弦。弦將多邊形分割成2個多邊形vi,vi+1,vj和vj,vj+1,

39、vi。多邊形的三角剖分多邊形的三角剖分是將多邊形分割成互不相交的三角形的弦的集合T。給定凸多邊形P，以及定義在由多邊形的邊和弦組成的三角形上的權函數w。要求確定該凸多邊形的三角剖分，使得即該三角剖分中諸三角形上權之和為最小。 72一個表達式的完全加括號方式相應于一棵完全二叉樹，稱為表達式的語法樹。例如，完全加括號的矩陣連乘積(A1(A2A3)(A4(A5A6)所相應的語法樹如圖 (a)所示。凸多邊形v0,v1,vn-1的三角剖分也可以用語法樹表示。例如，圖 (b)中凸多邊形的三角剖分可用圖 (a)所示的語法樹表示。 矩陣連乘積中的每個矩陣Ai對應于凸(n+1)邊形中的一條邊vi-1vi。三角剖

40、分中的一條弦vivj，ij，對應于矩陣連乘積Ai+1:j。73凸多邊形的最優三角剖分問題有最優子結構性質。事實上，若凸(n+1)邊形P=v0,v1,vn-1的最優三角剖分T包含三角形v0vkvn，1kn-1，則T的權為3個部分權的和：三角形v0vkvn的權，子多邊形v0,v1,vk和vk,vk+1,vn的權之和?？梢詳嘌裕蒚所確定的這2個子多邊形的三角剖分也是最優的。因為若有v0,v1,vk或vk,vk+1,vn的更小權的三角剖分將導致T不是最優三角剖分的矛盾。 74定義tij，1iT(S,b(1)，設是作業集S在機器M2的等待時間為b(1)情況下的一個最優調度。則(1)， (2)， (n)

41、是N的一個調度，且該調度所需的時間為a(1)+T(S,b(1)a(1)+T。這與是N的最優調度矛盾。故TT(S,b(1)。從而T=T(S,b(1)。這就證明了流水作業調度問題具有最優子結構的性質。由流水作業調度問題的最優子結構性質可知，),(min)0 ,(1iinibiNTaNT)0 ,max,(min),(iiiSiatbiSTatST91對遞歸式的深入分析表明，算法可進一步得到簡化。設是作業集S在機器M2的等待時間為t時的任一最優調度。若(1)=i, (2)=j。則由動態規劃遞歸式可得:T(S,t)=ai+T(S-i,bi+maxt-ai,0)=ai+aj+T(S-i,j,tij)其中，

42、,max0 ,max,0 ,maxmax0 ,0 ,maxmaxiijiijijijijijijijijjiijijabaataabbbaatabbbaatabbaatbbt如果作業i和j滿足minbi,ajminbj,ai，則稱作業i和j滿足JohnsonJohnson不等式不等式。92交換作業i和作業j的加工順序，得到作業集S的另一調度，它所需的加工時間為T(S,t)=ai+aj+T(S-i,j,tji)其中，當作業i和j滿足Johnson不等式時，有由此可見當作業i和作業j不滿足Johnson不等式時，交換它們的加工順序后，不增加加工時間。對于流水作業調度問題，必存在最優調度 ，使得作業

43、(i)和(i+1)滿足Johnson不等式。進一步還可以證明，調度滿足Johnson法則當且僅當對任意i2n時，算法需要(n2n)計算時間。 96由m(i,j)的遞歸式容易證明，在一般情況下，對每一個確定的i(1in)，函數m(i,j)是關于變量j的階梯狀單調不減函數。跳躍點是這一類函數的描述特征。在一般情況下，函數m(i,j)由其全部跳躍點唯一確定。如圖所示。對每一個確定的i(1in)，用一個表pi存儲函數m(i，j)的全部跳躍點。表pi可依計算m(i，j)的遞歸式遞歸地由表pi+1計算，初始時pn+1=(0，0)。 97n=3，c=6，w=4，3，2，v=5，2，1。x(0,0)m(4,x

44、)x(2,1)m(4,x-2)+1x(0,0)(2,1)m(3,x)(3,2)xm(3,x-3)+2(5,3)x(0,0)(2,1)m(2,x)(3,2)(5,3)xm(2,x-4)+5(4,5)(6,6)(7,7)(9,8)x(0, 0)(2, 1)m(1,x)(3,2)(5,3)(4,5)(6,6)(7,7)(9,8)x(0,0)(2,1)m(3,x)x(0,0)(2,1)m(2,x)(3,2)(5,3)98函數m(i,j)是由函數m(i+1,j)與函數m(i+1,j-wi)+vi作max運算得到的。因此，函數m(i,j)的全部跳躍點包含于函數m(i+1，j)的跳躍點集pi+1與函數m(i

45、+1，j-wi)+vi的跳躍點集qi+1的并集中。易知，(s,t)qi+1當且僅當wisc且(s-wi,t-vi)pi+1。因此，容易由pi+1確定跳躍點集qi+1如下qi+1=pi+1(wi,vi)=(j+wi,m(i,j)+vi)|(j,m(i,j)pi+1 另一方面，設(a，b)和(c，d)是pi+1qi+1中的2個跳躍點，則當ca且db時，(c，d)受控于(a，b)，從而(c，d)不是pi中的跳躍點。除受控跳躍點外，pi+1qi+1中的其它跳躍點均為pi中的跳躍點。由此可見，在遞歸地由表pi+1計算表pi時，可先由pi+1計算出qi+1，然后合并表pi+1和表qi+1，并清除其中的受控跳躍點得到表pi。99n=5，c=10，w=2，2，6，5，4，v=6，3，5，4，6。初始時p6=(0,0)，(w5,v5)=(4,6)。因此，q6=p6(w5,v5)=(4,6)。p5=(0,0),(4,6)。q5=p5(w4,v4)=(5,4),