编辑距离问题-算法导论.docVIP

第三次上机报告 班级：031013 学号 姓名：黄辉煌 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。 Testing Data： 1. X = algorithm Y = altruistic 2. X = GATCGGCAT Y = 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。此时，根据题目的定义可知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]+cost(insert). 5. 最终s[i,j] = Min {Case1, Case2, Case3, Case4} 二、主程序代码 #include iostream #include limits #include iomanip using namespace std; typedef enum{Copy,Replace,Delete,Insert}; int cost[4] = {-1,1,2,2}; int s[15][15] = {0}; int Edit_Distance(char *x, char *z, int x_Length, int z_Length); void Print_Cost(int x_Length, int z_Length); void main() { char x[] = algorithm; char z[] = altruistic; int x_Length = strlen(x), z_Length = strlen(z); cout代价：Edit_Distance(x, z, x_Length, z_Length)endl; cout从i到j的编辑距离:endl; Print_Cost(x_Length, z_Length); } int Edit_Distance(char *x, char *z, int x_Length, int z_Length) { int i = 0, j = 0,temp; //初始化s[0,0]=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 x_Length; i++) { for(j = 0; j z_Length; j++) { s[i+1][j+1] = INT_