動(dòng)態(tài)規(guī)劃策略教材(完整版)
【正文】 10 ? 100, A2: 100 ? 5, A3: 5 ? 50, ?完全加括號(hào)的矩陣連乘積可遞歸地定義為： （ 1）單個(gè)矩陣是完全加括號(hào)的； （ 2）矩陣連乘積 A是完全加括號(hào)的，則 A可 表示為 2個(gè)完全加括號(hào)的矩陣連乘積 B和 C 的乘積并加括號(hào)，即 A=((B)(C)) ?設(shè)有四個(gè)矩陣 A、 B、 C、 D,它們的維數(shù)分別是 1050 ?? 4010 ?? 3040 ??C 530?D )))((( DBCA )))((( DCAB )))((( BCA )))((( CDB )))((( CDAB16000 10500 36000 87500 34500 四種加括號(hào)方式 ?窮舉法 ?列舉出所有可能的計(jì)算次序，并計(jì)算出每一種計(jì)算次序相應(yīng)需要的數(shù)乘次數(shù)，從中找出一種數(shù)乘次數(shù)最少的計(jì)算次序。 則稱 Z是 X的子 序列 。因此，最長(zhǎng)公共子序列問題具有 最優(yōu)子結(jié)構(gòu)性質(zhì) 。0,0,0]}][1[],1][[max{1]1][1[0]][[② 遞推方程、決策函數(shù) 標(biāo)記函數(shù)： B[i, j], 其值為字符 ↖ 、 ?、 ?，分別表示 C[i,j]取得最大值時(shí)的三種情況 LCS(X,Y,m,n) //求最長(zhǎng)公共子序列長(zhǎng)度 { 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的最長(zhǎng)公共子序列 if( i=0 or j=0 ) then return //一個(gè)序列為空 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) 算法的計(jì)算復(fù)雜度 計(jì)算優(yōu)化函數(shù)和標(biāo)記函數(shù)：時(shí)間為 O(mn) 構(gòu)造解：每一步至少縮小 X 或 Y 的長(zhǎng)度，時(shí)間 ?(m+n） 空間： ?(mn) 輸入： X=A,B,C,B,D,A,B, Y=B,D,C,A,B,A， 標(biāo)記函數(shù)： 解： X[2],X[3], X[4], X[6], 即 B, C, B, A 實(shí)例 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,4]= ? B[7,5]= ↖ B[7,6]= ? 例 4:(最長(zhǎng)遞增子序列 ) 若給定序列A=(a1,a2,… ,am),如果存在一個(gè)下標(biāo)序列 i1i2… ik ，使得 則稱 為長(zhǎng)度為 k的子序列。 2023年 3月 下午 7時(shí) 51分 :51March 23, 2023 1行動(dòng)出成果，工作出財(cái)富。 2023年 3月 23日星期四 下午 7時(shí) 51分 26秒 19:51: 1楚塞三湘接，荊門九派通。勝人者有力，自
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號(hào)-1