動態(tài)規(guī)劃策略教材(文件)
【正文】 C)) ?設(shè)有四個矩陣 A、 B、 C、 D,它們的維數(shù)分別是 1050 ?? 4010 ?? 3040 ??C 530?D )))((( DBCA )))((( DCAB )))((( BCA )))((( CDB )))((( CDAB16000 10500 36000 87500 34500 四種加括號方式 ?窮舉法 ?列舉出所有可能的計算次序，并計算出每一種計算次序相應需要的數(shù)乘次數(shù)，從中找出一種數(shù)乘次數(shù)最少的計算次序。循環(huán)體內(nèi)的計算量為 O(1)，而 3重循環(huán)的總次數(shù)為 O(n3)。 則稱 Z是 X的子 序列 。 分析：設(shè) X=“ abcbdab” Y=“ bdcdb” 最長公共子序列是： Z=“ bcdb” ① 子問題劃分及依賴關(guān)系 子問題邊界： X和 Y 起始位置為 1， X的終止位置是 i， Y 的 終止位置是 j，記作 Xi=x1,x2,…, xi， Yj=y1,y2,…, yj 依賴關(guān)系： X=x1,x2,…, xm, Y=y1,y2,…, yn, Z=z1,z2,…, zk， Z 為 X 和 Y 的 LCS，那么 (1)若 xi=yj，則 zk=xi=yj， 且 Zk1是 Xi1和 Yj1的最長公共子序列。因此，最長公共子序列問題具有 最優(yōu)子結(jié)構(gòu)性質(zhì) 。當 i=0或 j=0時，空序列是Xi和 Yj的最長公共子序列 。0,0,0]}][1[],1][[max{1]1][1[0]][[② 遞推方程、決策函數(shù) 標記函數(shù)： B[i, j], 其值為字符 ↖ 、 ?、 ?，分別表示 C[i,j]取得最大值時的三種情況 LCS(X,Y,m,n) //求最長公共子序列長度 { for( i=1 to m) C[i,0]=0 //邊界 情況 for( i=1 to n ) C[0,i]=0 for( i=1 to m ) for( j=1 to n) { if (X[i]==Y[j]){ C[i,j]=C[i?1,j?1]+1 B[i,j]=’?’ } else if(C[i?1,j] ? C[i,j?1]) { C[i,j]=C[i?1,j] B[i,j]=’?’ } else{ C[i,j]=C[i,j?1] B[i,j]=’?’ } }end for(j=…) Construct_Sequence(B, i, j) {//輸入 ： B[i,j] //輸出 ： X與 Y的最長公共子序列 if( i=0 or j=0 ) then return //一個序列為空 if (B[i,j] =“ ↖ ” ) { 輸出 X[i] Construct_Sequence (B, i－ 1, j－ 1) } else if(B[i,j]==“ ?” ) Construct_Sequence (B, i－ 1, j) else Construct_Sequence (B, i, j－ 1) 算法的計算復雜度 計算優(yōu)化函數(shù)和標記函數(shù)：時間為 O(mn) 構(gòu)造解：每一步至少縮小 X 或 Y 的長度，時間 ?(m+n） 空間： ?(mn) 輸入： X=A,B,C,B,D,A,B, Y=B,D,C,A,B,A， 標記函數(shù)： 解： X[2],X[3], X[4], X[6], 即 B, C, B, A 實例 1 2 3 4 5 6 1 B[1,1]= ? B[1,2]= ? B[1,3]= ? B[1,4]=↖ B[1,5]= ? B[1,6]=↖ 2 B[2,1]=↖ B[2,2]= ? B[2,3]= ? B[2,4]= ? B[2,5]=↖ B[2,6]= ? 3 B[3,1]= ? B[3,2]= ? B[3,3]=↖ B[3,4]= ? B[3,5]= ? B[3,6]= ? 4 B[4,1]= ↖ B[4,2]= ? B[4,3]= ? B[4,4]= ? B[4,5]=↖ B[4,6]= ? 5 B[5,1]= ? B[5,2]=↖ B[5,3]= ? B[5,4]= ? B[5,5]= ? B[5,6]= ? 6 B[6,1]= ? B[6,2]= ? B[6,3]= ? B[6,4]=↖ B[6,5]= ? B[6,6]=↖ 7 B[7,1]=↖ B[7,2]= ? B[7,3]= ? B[7,
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1