编辑距离问题-算法导论

《编辑距离问题-算法导论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三次上机报告班级：031013学号：03101283姓名：黄辉煌Title：动态规划求最短编辑距离问题描述：已知字符串X和Y，要求使用最少的字符串操作将字符串X转换成字符串Y，字符串操作包括以下四种：（1）删除一个字符（Delete），Cost（Delete）=2；（2）插入一个字符（Insert），Cost（Insert）=2；（3）替换一个字符（Replace），Cost（Replace）=1；（4）复制一个字符（Copy），Cost（Copy）=-1.Input:：字符串X和Y；Output：字符串X和Y的编辑距离EditDistance。TestingData：1.X=a

2、lgorithmY=altruistic2.X=GATCGGCATY=CAATGTGAATC一、算法设计与描述对于序列X[i](0≤i≤m)和序列Y[j](0≤j≤n)来说，定义s[i,j]为X[i]转换成Y[j]的操作序列的最小代价。假定我们已经知道了最后一次执行的操作，此时分情况讨论问题的最优解结构。1.最后一次操作为Copy，根据书中定义可知，x[i]=y[j],问题就转化成了求将X[i-1]转换为Y[j-1]的最小开销。因此，当最后一次操作为copy时，可以定义s[i,j]=s[i-1,j-1]+cost(copy)。2.最后一次操作为replace。此时，根据题目的定义可

3、知x[i]≠y[j]。仿照上述分析，可以得到相同的最优子结构。此时s[i,j]=s[i-1,j-1]+cost(replace)。3.最后一次操作为delete。根据题意，这时只是将x[i]从序列x[i]中除去，对序列Y[j]没有任何影响，此时问题的最优子结构的形式为将X[i-1]转换成Y[j]，于是可以得到s[i,j]=s[i-1,j]+cost(delete)。4.最后一次操作为insert。根据题意，在进行插入操作时，序列X[i]无任何变化，序列Y[j]添加一个字符，因此，这时候问题的最优子结构的形式为将X[i]转换成为Y[j-1]，此时s[i,j]=s[i,j-1]+cos

4、t(insert).5.最终s[i,j]=Min{Case1,Case2,Case3,Case4}二、主程序代码#include#include#includeusingnamespacestd;typedefenum{Copy,Replace,Delete,Insert};intcost[4]={-1,1,2,2};ints[15][15]={0};intEdit_Distance(char*x,char*z,intx_Length,intz_Length);voidPrint_Cost(intx_Length,intz_Le

5、ngth);voidmain(){charx[]="algorithm";charz[]="altruistic";intx_Length=strlen(x),z_Length=strlen(z);cout<<"代价："<

6、=0//s[i,0]=i*cost(delete)for(i=1;i<=x_Length;i++)s[i][0]=i*cost[Delete];//s[0,j]=j*cost[insert]for(j=1;j<=z_Length;j++)s[0][j]=i*cost[Insert];for(i=0;i

7、/Replaceif(x[i]!=z[j]){temp=s[i][j]+cost[Replace];if(temp