動態(tài)規(guī)劃策略教材(編輯修改稿)
2025-03-22 21:43 本頁面
【文章內(nèi)容簡介】 r return m[i,j] } 這里沒有寫出算法的全部描述（進(jìn)入遞歸調(diào)用的初值等） ?方法 1：直接遞歸方法實現(xiàn) 26 復(fù)雜性滿足遞推關(guān)系 ?????????????????????????????11111111)(2)()()()()(1))1()()((1)1()(nknknknkkTnOknTkTnOnTnOknTkTnOnT 數(shù)學(xué)歸納法證明 T(n)?2n?1 n=2,顯然為真 假設(shè) 對于任何小于 n 的 k 命題為真 , 則 11111112)12(2)(22)()(2)()(??????????????? ??nnnkknknOnOkTnOnT*遞歸實現(xiàn)的復(fù)雜性 27 n=5，計算子問題： 81個 ；不同的子問題： 15個 子問題 11 22 33 44 55 12 23 34 45 13 24 35 14 25 15 數(shù) 8 12 14 12 8 4 5 5 4 2 2 2 1 1 1 2 復(fù)雜性高的原因：子問題重復(fù)計算 ?方法 2：直接遞推方法 MatrixChain(P,n) { 令 所有的 m[i,j]初值為 0 1? i j ? n for( r ?2 to n) // r為計算的矩陣鏈長度 for( i ?1 to n?r+1) { //nr+1為最后 r鏈的始位置 j ?i+r?1 // 計算鏈 i— j m[i,j] ? m[i+1,j] + pi?1*pi*pj // Ai(Ai+1..Aj) s[i,j] ? i //記錄分割位置 for(k ?i+1 to j?1){ t ?m[i,k]+m[k+1,j]+ pi?1*pk*pj //(Ai..Ak)(Ak+1..Aj) if( tm[i,j]){ m[i,j]?t s[i,j]?k }//end if }// end for(k=…) }//end for(i=….) A1 A2 A3 A4 A5 A6 30?35 35?15 15?5 5?10 10?20 20?25 ??????????????????????????????11 37520233504375]5][5[]4][2[71252053510002625]5][4[]3][2[13 00020233525000]5][3[]2][2[min]5][2[541531521pppmmpppmmpppmmm算法復(fù)雜度分析： 算法 matrixChain的主要計算量取決于算法中對 r，i和 k的 3重循環(huán)。循環(huán)體內(nèi)的計算量為 O(1)，而 3重循環(huán)的總次數(shù)為 O(n3)。因此算法的計算時間上界為 O(n3)。算法所占用的空間顯然為 O(n2)。 例 4:(最長公共子序列 ) 概念： ? 若 給定序列 X={x1,x2,…,x m},另 一 序列 Z={z1,z2,…,z k}， 如果存在 一個嚴(yán)格遞增下標(biāo)序列 {i1,i2,…,i k}使得對于所有j=1,2,…,k 有： zj=xij。 則稱 Z是 X的子 序列 。 ? 例， 序列 Z={B， C， D， B}是序列 X={A， B， C， B， D，A， B}的子序列，相應(yīng)的遞增下標(biāo)序列為 {2， 3， 5， 7}。 ? 給定 2個序列 X和 Y，當(dāng)另一序列 Z既是 X的子序列又是 Y的子序列時，稱 Z是序列 X和 Y的 公共子序列 。 ? 給定 2個序列 X={x1,x2,… ,xm}和 Y={y1,y2,… ,yn}， X和 Y的公共子序列有很多， 找出 X和 Y的最長公共子序列。 分析：設(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的最長公共子序列。 (2)若 xi≠yj且 zk≠xi， 則 ZK是 Xi1和 Yj的最長公共子序列。 (3)若 xi≠y
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1