编辑距离问题-算法导论
第三次上机报告
班级：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 = 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
#include
#include
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
cout
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
s[i][0] = i * cost[Delete];
//s[0,j] = j * cost[insert]
for(j = 1; j
s[0][j] = i * cost[Insert];
for(i = 0; i
{
for(j = 0; j
{
s[i+1][j+1] = INT_MAX;
//copy
if(x[i] == z[j])
{
temp = s[i][j] + cost[Copy];
if(temp
s[i+1][j+1] = temp;
}
//Replace
if(x[i] != z[j])
{
temp = s[i][j] + cost[Replace];
if(temp
s[i+1][j+1] = temp;
}
//delete
temp = s[i][j+1] + cost[Delete];
if(temp
s[i+1][j+1] = temp;
//insert
temp = s[i+1][j] + cost[Insert];
if(temp
s[i+1][j+1] = temp;
}
}
return s[x_Length][z_Length];
}
void Print_Cost(int x_Length, int z_Length)
{
int i, j;
for(i = 1; i
{
for(j = 1; j
cout
cout
}
}
三、设计与调试分析
1、算法复杂度分析
本算法时间复杂度为O （n^2）
2、运行结果
四、总结
程序利用动态规划的思想，将问题剖析细化得到最优解。这与之前所接触的程序设计思想有一定差异性，所以刚开始时并无头绪。这是理解编程的又一个进步。