信息工程大學算法設計與分析動態規劃—編輯距離問題國家級實驗教學示范中心計算機學科組規劃教材算法設計與分析Python案例詳解微課視頻版

設A和B是兩個字符串，要用最少的字符操作將A轉換為B。字符操作有三種：（1）刪除一個字符；（2）插入一個字符；（3）將一個字符改為另一個字符。

將字符串A轉換為字符串B所用的最少字符操作數稱為字符串A到B的編輯距離。字符串Abanana操作修改修改刪除字符串BpandaA轉換為B的編輯距離為3編輯距離反映兩個字符串的相似程度。最長公共子序列反映兩個字符串的相似程度。關注差異性bana

napanda編輯距離是3關注公共部分ba

nanapa

nda最長公共子序列是3字符串Abanana字符串Bpanda1.首先對比最后一個字符，都是a，相等；問題轉換為banan和pand的編輯距離問題；2.比較最后一個字符，n和d不等，取min{刪除n+bana和pand的編輯距離，插入d+banan和pan的編輯距離，修改n為d+bana和pan的編輯距離}3.…1.找出最優解性質，刻畫結構特征

δ(A,B)表示字符串A和B的編輯距離。定義D[i,j]=δ(A[1..i],B[1..j])。D[i,j]=min{D[i-1,j-1]+δ(A[i],B[j]),D[i-1,j]+1,D[i,j-1]+1}；D[i,0]=i，i=0~m；D[0,j]=j，j=0~n；2.遞歸地定義最優值3.以自底向上的方式計算最優值00000000000BjAmB1B2BnA1A2Ai012nm1204.根據計算最優值時得到的信息，構造最優解定義C[i,j]：D[i,j]獲得最優值時對應的字符操作。C[i,j]=0：表示A[i]和B[j]相等C[i,j]=1：表示把A[i]修改為B[j]C[i,j]=2：表示刪除A[i]C[i,j]=3：表示插入B[j]實例分析：A=“banana”，B=“panda”

j=0j=1pj=2aj=3nj=4dj=5ai=0012345i=1b112345i=2a221234i=3n332123i=4a443222i=5n554333i=6a665443數組D[i,j]

j=0j=1pj=2aj=3nj=4dj=5ai=0033333i=1b21(修改)1111i=2a210(不變)330i=3n2120(不變)33i=4a2102(刪除)10i=5n21201(修改)1i=6a210210(不變)實例分析：A=”banana”，B=”panda”數組C[i,j]判斷題。編輯距離問題中，最優解可能有多個。A.正確B.錯誤/*動態規劃求解編輯距離，字符串A長度為m，字符串B長度為n*/voideditDistance(char*A,char*B,intm,intn){……/*初始化D和C數組*/for(i=0;i<=m;i++){D[i][0]=i;C[i][0]=2;}for(j=0;j<=n;j++){D[0][j]=j;C[0][j]=3;}

for(i=1;i<=m;i++)for(j=1;j<=n;j++)/*當字符相等時，不做任何操作*/

if(A[i]==B[j]){D[i][j]=D[i-1][j-1];C[i][j]=0;}else{t1=D[i-1][j-1]+1;t2=D[i-1][j]+1;t3=D[i][j-1]+1;if(t1<=t2&&t1<=t3){D[i][j]=t1;C[i][j]=1;}elseif(t2<=t1&&t2<=t3){D[i][j]=t2;C[i][j]=2;}

elseif(t3<=t1&&t3<=t2){D[i][j]=t3;C[i][j]=3;}}}時間復雜度：O(