資源描述：
《算法設(shè)計與分析第6講 動態(tài)規(guī)劃.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、動態(tài)規(guī)劃DynamicProgramming1最長公共子序列問題給定兩個序列x(x1,..xm),y(y1,…yn)，尋找一個最長的公共子序列，lcs（x,y）.例X:ABCBDABY:BDCABALcs:BDAB,BCAB,BCBA算法１：窮舉－－給出X的一個子串（2m個？），測試是不是Y的子串。１次測試的時間是θ(n)，故總時間＝θ(n2m),是個指數(shù)級別的。2算法思路１ 先算出LCS(x,y)的長度２ 再擴充之，得到LCS.用
2、S
3、記錄串S的長度，策略：考慮x,y的前綴，變成一些會怎么樣？定義C[i,j]=
4、LCS(x(1,..i),y(1,,,j)
5、則C[m,n]=
6、LCS(x,y)3遞推式定理：證明：令Z(1,2,..k)＝LCS(x(1,2,..i),y(1,2,..j))則
7、Z
8、=C[i,j]=k.1x[i]=y[j].畫出Ｚ到x和y的一一對應(yīng)，z[k]一定對應(yīng)到x[i]或（和）y[j]？.那么Z(1,2,..k-1)肯定對應(yīng)在(x(1,2,..i-1),y(1,2,..j-1)上.另外，不會有更長的公共字串,故Z(1,2,..k-1)＝LCS(x(1,2,..i-1),y(1,2,..j-1)),即C[i-1,j-1]=k-1=C[i,j]-1.2else.如果Z[k]不對應(yīng)x[i]或者y[j]。如果不對應(yīng)X[i],則Z(1,2
9、,..k)=LCS(x(1,2,..i-1),y(1,2,..j)),如果不對應(yīng)y[i],則Z(1,2,..k)=LCS(x(1,2,..i),y(1,2,..j-1)),故C[I,j]=max(C[i-1,j],C[I,j-1])4動態(tài)規(guī)劃特征１－最優(yōu)子結(jié)構(gòu)剛才的證明發(fā)現(xiàn)，Z(1,2,..k)＝LCS(x,y)則Z(1,2…k-1)是x,y前綴的LCS.最優(yōu)子結(jié)構(gòu)：一個問題的最優(yōu)解的一部分，是子問題的最優(yōu)解。遞歸算法：LCS(x,y,i,j)Ifx[i]=y[j]thenC[i,j]=LCS(x,y,i-1,j-1)+1;ElseC[i,j]=max(LCS(x,y,i-
10、1,j),LCS(x,y,i,j-1))ReturnC[i,j]5遞歸算法復(fù)雜性遞歸樹（最差情況，x[i]!=y[j]任何的i,j）2叉樹，樹高（m+n）,故節(jié)點個數(shù)O(2m+n)但是，可以觀察到，很多子樹是相同的，不必要遞歸再計算一次7,37,56,67,46,56,55,67,66,46,45,55,56,45,54,66動態(tài)規(guī)劃特征2重疊子結(jié)構(gòu)：遞歸中，有獨立子問題被計算多次。實際上C[i,j]中，不同的只有mn個問題備忘錄算法：LCS(x,y,i,j)ifC[i,j]!=nilthenifx[i]=y[j]thenC[i,j]=LCS(x,y,i-1,j-1)+1;
11、ElseC[i,j]=max(LCS(x,y,i-1,j),LCS(x,y,i,j-1));returnC[i,j]T=θ(mn)7動態(tài)規(guī)劃算法自底向上計算，不遞歸ABCBDAB0000000B00111111D00111222C00122222A01122233B01223334A01223344回溯－重建LCS8
