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

第三次上机报告班级：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。Testing Data：1. X = algorithm Y = altruistic2. X = GATCGGCAT Y = CAATGTGAATC1、 算法设计与描述对于序列Xi(0im)和序列Yj(0jn)来说，定义si,j为Xi转换成Yj的操作序列的最小代价。假定我们已经知道了最后一次执行的操作，此时分情况讨论问题的最优解结构。1. 最后一次操作为Copy，根据书中定义可知，xi=yj, 问题就转化成了求将Xi-1转换为Yj-1的最小开销。因此，当最后一次操作为copy时，可以定义si,j=si-1,j-1+cost(copy)。2. 最后一次操作为replace。此时，根据题目的定义可知xiyj。仿照上述分析，可以得到相同的最优子结构。此时si,j=si-1,j-1+cost(replace)。3. 最后一次操作为delete。根据题意，这时只是将xi从序列xi中除去，对序列Yj没有任何影响，此时问题的最优子结构的形式为将Xi-1转换成Yj，于是可以得到si,j=si-1,j+cost(delete)。4. 最后一次操作为insert。根据题意，在进行插入操作时，序列Xi无任何变化，序列Yj添加一个字符，因此，这时候问题的最优子结构的形式为将Xi转换成为Yj-1，此时si,j=si,j-1+cost(insert).5. 最终si,j = Min Case1, Case2, Case3, Case4二、主程序代码#include #include #include using namespace std; typedef enumCopy,Replace,Delete,Insert;int cost4 = -1,1,2,2; int s1515 = 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; /初始化s0,0=0 /si,0 = i * cost(delete) for(i = 1; i = x_Length; i+) si0 = i * costDelete; /s0,j = j * costinsert for(j = 1; j = z_Length; j+) s0j = i * costInsert; for(i = 0; i x_Length; i+) for(j = 0; j z_Length; j+) si+1j+1 = INT_MAX; /copy if(xi = zj) temp = sij + costCopy; if(temp si+1j+1) si+1j+1 = temp; /Replace if(xi != zj) temp = sij + costReplace; if(temp si+1j+1) si+1j+1 = temp; /delete temp = sij+1 + costDelete; if(temp si+1j+1) si+1j+1 = temp; /insert temp = si+1j + costInsert; if(temp si+1j+1) si+1j+1 = temp; return sx_Lengthz_Length; void Print_Cost(int x_Length, int z_Length) int i, j; for(i = 1; i = x_Length; i+) for(j = 1; j = z_Length; j+) coutsetw(4)sij; coutendl; 3、 设