第三次上机报告
班级: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 <iostream>
#include <limits>
#include <iomanip>
using namespace std;
typedef enum{Copy,Replace,Delete,Insert};