算法设计与分析 课件 5.8-动态规划应用-编辑距离问题

信息工程大学算法设计与分析动态规划—编辑距离问题国家级实验教学示范中心计算机学科组规划教材算法设计与分析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(