[]動(dòng)態(tài)規(guī)劃策略

1、)(),(cos)()(), 1 (cos) 1 (minmin1jfjitifjfjtfiAjAjF1()F3()F4()F5()F2()用函數(shù)用函數(shù)fi(x)表示第表示第i層節(jié)點(diǎn)到底部（假設(shè)是第層節(jié)點(diǎn)到底部（假設(shè)是第N層）的路層）的路徑上數(shù)字和的最大值。徑上數(shù)字和的最大值。顯而易見：顯而易見：f1(9)=9+maxf2(12)+f2(15)問題變成：?jiǎn)栴}變成：f1(9)=?f2(12)=12+maxf3(10)+f3(6)f2(15)=15+maxf3(6)+f3(8)fi(x)=x+maxfi+1(x1)+fi+1(x2)+遞歸公式的終止條件：fN(19)=19fN(7)=7思考：請(qǐng)同學(xué)

2、們手工計(jì)算一下結(jié)果？如何編程？如何編程與數(shù)據(jù)結(jié)構(gòu)有關(guān)：將原始數(shù)塔寫成下面的形式，用表示這個(gè)矩陣用矩陣表示上面的 nxmixgxfyxfygxfiixyi0 ,.,2 , 11110max初始條件： nxmixgxfyxfygxfiixyi0 ,.,2 , 11110max初始條件：n1,2,.,j ,.,2 , 11 1 1max0mijgjfkjifkigjifjk初始條件：1max arg0kjifkigjiajk為了表示方便, 以矩陣加括號(hào)表示矩陣相乘的順序輸入：向量輸入：向量 P = ，n個(gè)矩陣的行數(shù)、列數(shù)個(gè)矩陣的行數(shù)、列數(shù)實(shí)例：實(shí)例： P = A1: 10 100, A2: 100

3、5, A3: 5 50, （1）單個(gè)矩陣是完全加括號(hào)的；）單個(gè)矩陣是完全加括號(hào)的；（2）矩陣連乘積）矩陣連乘積A是完全加括號(hào)的，則是完全加括號(hào)的，則A可可 表示為表示為2個(gè)完全加括號(hào)的矩陣連乘積個(gè)完全加括號(hào)的矩陣連乘積B和和C 的乘積并加括號(hào)，即的乘積并加括號(hào)，即 A=(B)(C) 1050A4010B3040C530D)(DBCA)(DCAB)(DBCA)(CDBA)(CDAB1600010500360008750034500四種加括號(hào)方式四種加括號(hào)方式列舉出所有可能的計(jì)算次序，并計(jì)算出每一種計(jì)算次序列舉出所有可能的計(jì)算次序，并計(jì)算出每一種計(jì)算次序相應(yīng)需要的數(shù)乘次數(shù)，從中找出一種數(shù)乘次數(shù)最少

4、的計(jì)相應(yīng)需要的數(shù)乘次數(shù)，從中找出一種數(shù)乘次數(shù)最少的計(jì)算次序。算次序。)/4()(11)()(1)(2/311nnPnnknPkPnPnnku算法復(fù)雜度分析算法復(fù)雜度分析：對(duì)于對(duì)于n個(gè)矩陣的連乘積，設(shè)其不同的計(jì)算次序?yàn)閭€(gè)矩陣的連乘積，設(shè)其不同的計(jì)算次序?yàn)镻(n)。由于每種加括號(hào)方式都可以分解為兩個(gè)子矩陣的加括號(hào)由于每種加括號(hào)方式都可以分解為兩個(gè)子矩陣的加括號(hào)問題：?jiǎn)栴}：(A1.Ak)(Ak+1An)可以得到關(guān)于可以得到關(guān)于P(n)的遞推的遞推式如下：式如下：將矩陣連乘積將矩陣連乘積 A1A2A3,An簡(jiǎn)記為簡(jiǎn)記為Ai:j,這里這里ij考察計(jì)算考察計(jì)算Ai:j的最優(yōu)計(jì)算次序。設(shè)這個(gè)計(jì)算次序的最優(yōu)計(jì)

5、算次序。設(shè)這個(gè)計(jì)算次序在矩陣在矩陣Ak和和Ak+1之間將矩陣鏈斷開，之間將矩陣鏈斷開，ikj，則其，則其相應(yīng)完全加括號(hào)方式為相應(yīng)完全加括號(hào)方式為).)(.(211jkkkiiAAAAAA計(jì)算量：計(jì)算量：Ai:k的計(jì)算量加上的計(jì)算量加上Ak+1:j的計(jì)算量，的計(jì)算量，再加上再加上Ai:k和和Ak+1:j相乘的計(jì)算量相乘的計(jì)算量u動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃 劃分子問題，確定子問題的邊界，有劃分子問題，確定子問題的邊界，有i和和j確定確定子問題的邊界子問題的邊界jkipppjkmkimjim1, 1,這里 的維數(shù)為 iAiipp1jipppjkmkimjijimjki, 1,min0,1jki 的位置只有 種

6、可能kij 確定優(yōu)化函數(shù)和遞推方程：確定優(yōu)化函數(shù)和遞推方程：設(shè)立標(biāo)記函數(shù)（決策函數(shù)）設(shè)立標(biāo)記函數(shù)（決策函數(shù)） 為了為了確定加括號(hào)的次序確定加括號(hào)的次序，定義，定義 si,j,記錄記錄mi,j最優(yōu)時(shí)最優(yōu)時(shí)k的位置的位置 si,j=k問題：如何編程實(shí)現(xiàn)？ 自頂向下遞歸實(shí)現(xiàn) 自底向上迭代（遞推）實(shí)現(xiàn)int RecurMatrixChain(P,i,j) mi,j= si,j=i for( k=i to j 1 ) q = RecurMatrixChain(P,i,k) + RecurMatrixChain(P,k+1,j) + pi 1 pk pj If (qmi,j) mi,j=q si,j=k

7、/end if /end for return mi,j 這里沒有寫出算法的全部描述（進(jìn)入遞歸調(diào)用的初值等）復(fù)雜性滿足遞推關(guān)系復(fù)雜性滿足遞推關(guān)系 11111111)(2)()()()()(1)1()()(1)1()(nknknknkkTnOknTkTnOnTnOknTkTnOnT 數(shù)學(xué)歸納法證明數(shù)學(xué)歸納法證明 T(n) 2n 1 n=2,=2,顯然為真顯然為真 假設(shè)假設(shè)對(duì)于任何小于對(duì)于任何小于n 的的 k 命題為真命題為真, , 則則11111112)12(2)(22)()(2)()( nnnkknknOnOkTnOnT*遞歸實(shí)現(xiàn)的復(fù)雜性遞歸實(shí)現(xiàn)的復(fù)雜性n=5，計(jì)算子問題：，計(jì)算子問題：81個(gè)

8、個(gè)；不同的子問題：；不同的子問題：15個(gè)個(gè)子子問問題題1-12-23-34-45-51-22-33-44-51-32-43-51-42-51-5數(shù)數(shù)8121412845542221112復(fù)雜性高的原因：子問題重復(fù)計(jì)算復(fù)雜性高的原因：子問題重復(fù)計(jì)算MatrixChain(P,n) 令令所有的所有的 mi,j初值為初值為0 1 i j n for( r 2 to n) / r為計(jì)算的矩陣鏈長度為計(jì)算的矩陣鏈長度 for( i 1 to n r+1) /n-r+1為最后為最后r鏈的始位置鏈的始位置 j i+r 1 / 計(jì)算鏈計(jì)算鏈ij mi,j mi+1,j + pi 1*pi*pj / Ai(Ai

9、+1.Aj) si,j i /記錄分割位置記錄分割位置 for(k i+1 to j 1) t mi,k+mk+1,j+ pi 1*pk*pj /(Ai.Ak)(Ak+1.Aj) if( tmi,j) mi,jt si,jk /end if / end for(k=) /end for(i=.)113752010350437555427125205351000262554 3213000201535250005322min52541531521pppmmpppmmpppmmm算法復(fù)雜度分析：算法復(fù)雜度分析：算法matrixChain的主要計(jì)算量取決于算法中對(duì)r，i和k的3重循環(huán)。循環(huán)體內(nèi)的計(jì)算

10、量為O(1)，而3重循環(huán)的總次數(shù)為O(n3)。因此算法的計(jì)算時(shí)間上界為O(n3)。算法所占用的空間顯然為O(n2)。分析：設(shè)分析：設(shè) X=“abcbdab” Y=“bdcdb”最長公共子序列是：Z=“bcdb” 子問題劃分及依賴關(guān)系子問題劃分及依賴關(guān)系子問題邊界：子問題邊界： X和和Y 起始位置為起始位置為1，X的終止位置是的終止位置是 i，Y 的的終止位置是終止位置是 j，記作，記作 Xi=，Yj=依賴關(guān)系：依賴關(guān)系： X=, Y=, Z=， Z 為為 X 和和 Y 的的 LCS，那么，那么(1)若若xi=yj，則，則zk=xi=yj，且且Zk-1是是Xi-1和和Yj-1的最長公共子序列。的

11、最長公共子序列。(2)若若xiyj且且zkxi，則則ZK是是Xi-1和和Yj的最長公共子序列。的最長公共子序列。(3)若若xiyj且且zkyj，則則Zk是是Xi和和Yj-1的最長公共子序列。的最長公共子序列。由此可見，2個(gè)序列的最長公共子序列包含了這2個(gè)序列的前綴的最長公共子序列。因此，最長公共子序列問題具有最優(yōu)子結(jié)最優(yōu)子結(jié)構(gòu)性質(zhì)構(gòu)性質(zhì)。 u由最長公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關(guān)系。u用cij記錄序列和的最長公共子序列的長度。其中， Xi=x1,x2,xi；Yj=y1,y2,yj。當(dāng)i=0或j=0時(shí)，空序列是Xi和Yj的最長公共子序列。故此時(shí)Cij=0。u其他情況下，由最

12、優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下：jijiyxjiyxjijijicjicjicjic; 0,; 0,0, 01,1max1 110 遞推方程、決策函數(shù)遞推方程、決策函數(shù)標(biāo)記函數(shù)：標(biāo)記函數(shù)：Bi, j, 其值為字符其值為字符 、 ，分別表示，分別表示Ci,j取得最大值時(shí)的三種情況取得最大值時(shí)的三種情況LCS(X,Y,m,n) /求最長公共子序列長度求最長公共子序列長度 for( i=1 to m) Ci,0=0 /邊界邊界情況情況 for( i=1 to n ) C0,i=0 for( i=1 to m ) for( j=1 to n) if (Xi=Yj) Ci,j=Ci 1,j 1+1 Bi

13、,j= else if(Ci 1,j Ci,j 1) Ci,j=Ci 1,j Bi,j= else Ci,j=Ci,j 1 Bi,j= end for(j=) Construct_Sequence(B, i, j)/輸入輸入：Bi,j /輸出輸出：X與與Y的最長公共子序列的最長公共子序列 if( i=0 or j=0 ) then return /一個(gè)序列為空一個(gè)序列為空 if (Bi,j =“ ”) 輸出輸出Xi Construct_Sequence (B, i1, j1) else if(Bi,j=“ ”) Construct_Sequence (B, i1, j) else Constr

14、uct_Sequence (B, i, j1) 算法的計(jì)算復(fù)雜度算法的計(jì)算復(fù)雜度計(jì)算優(yōu)化函數(shù)和標(biāo)記函數(shù)：時(shí)間為計(jì)算優(yōu)化函數(shù)和標(biāo)記函數(shù)：時(shí)間為O(mn)構(gòu)造解：每一步至少縮小構(gòu)造解：每一步至少縮小X 或或 Y 的長度，時(shí)間的長度，時(shí)間 (m+n）空間：空間： (mn) 輸入：輸入：X=, Y=，標(biāo)記函數(shù)：標(biāo)記函數(shù)：解：解：X2,X3, X4, X6, 即即 B, C, B, A 1234561B1,1= B1,2= B1,3= B1,4= B1,5= B1,6= 2B2,1= B2,2= B2,3= B2,4= B2,5= B2,6= 3B3,1= B3,2= B3,3= B3,4= B3,5=

15、 B3,6= 4B4,1= B4,2= B4,3= B4,4= B4,5= B4,6= 5B5,1= B5,2= B5,3= B5,4= B5,5= B5,6= 6B6,1= B6,2= B6,3= B6,4= B6,5= B6,6= 7B7,1= B7,2= B7,3= B7,4= B7,5= B7,6= kiiiaaa21),(21kiiiaaa分析：1.貪心法 構(gòu)造兩個(gè)實(shí)例 （5,2,8,6,3,6,9,7） （3,18,7,14,10,12,23,41,16,24） 25368679有什么規(guī)律嗎？371810141216232441 （3,18,7,14,10,12,23,41,16,24） 3718101412231641242.動(dòng)態(tài)規(guī)劃方法 構(gòu)造兩個(gè)實(shí)例 （5,2,8,6,3,6,9,7） （3,18,7,14,10,12,23,41,16,24） for j = 1 to n L(j) = 1+maxL(i) | (i,j)Eend forreturn maxL(j)|j=1,2,nThere is one last issue to be cleared up: the L-values only tell us the length of the optimal subsequence, so how do we recover the sub