Java动态规划之编辑距离问题示例代码_Java教程

动态规划过程是：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。

动态规划实际上是一类题目的总称，并不是指某个固定的算法。动态规划的意义就是通过采用递推（或者分而治之）的策略，通过解决大问题的子问题从而解决整体的做法。动态规划的核心思想是巧妙的将问题拆分成多个子问题，通过计算子问题而得到整体问题的解。而子问题又可以拆分成更多的子问题，从而用类似递推迭代的方法解决要求的问题。问题描述:

对于序列s和t,它们之间的距离定义为:对二者其一进行几次以下操作:1,删除一个字符;2,插入一个字符;3,改变一个字符.每进行一次操作,计数增加1.将s和t变为相等序列的最小计数就是两者的编辑距离(editdistance)或者叫相似度.请给出相应算法及其实现.

分析:

假设序列s和t的长度分别为m和n,两者的编辑距离表示为edit[m][n].则对序列进行操作时存在以下几种情况:

a,当s和t的末尾字符相等时,对末尾字符不需要进行上述定义操作中(亦即"编辑")的任何一个,也就是不需要增加计数.则满足条件:edit[m][n]=edit[m-1][n-1].

b,当s和t的末尾字符不相等时,则需要对两者之一的末尾进行编辑,相应的计数会增加1.

b1,对s或t的末尾进行修改,以使之与t或s相等,则此时edit[m][n]=edit[m-1][n-1]+1;

b2,删除s末尾的元素,使s与t相等,则此时edit[m][n]=edit[m-1][n]+1;

b3,删除t末尾的元素,使t与s相等,则此时edit[m][n]=edit[m][n-1]+1;

b4,在s的末尾添加t的尾元素,使s和t相等,则此时s的长度变为m+1,但是此时s和t的末尾元素已经相等,只需要比较s的前m个元素与t的前n-1个元素,所以满足edit[m][n]=edit[m][n-1]+1;

b5,在t的末尾添加s的尾元素,使t和s相等,此时的情况跟b4相同,满足edit[m][n]=edit[m-1][n]+1;

c,比较特殊的情况是,当s为空时,edit[0][n]=n;而当t为空时,edit[m][0]=m;这个很好理解,例如对于序列""和"abc",则两者的最少操作为3,即序列""进行3次插入操作,或者序列"abc"进行3次删除操作.

所以,以上我们不难推出编辑距离的动态规划方程为:

Java动态规划之编辑距离问题示例代码

所以, 字符串编辑距离的动态规划算法的递归实现可以用如下的java代码表示:

									public static int editdistance(string a, string b) {

									    if (a == null || b == null) {

									      return -1;

									    }

									    return editdistance(a, a.length() - 1, b, b.length() - 1);

									  }

									  public static int editdistance(string a, int m, string b, int n) {

									    if (m < 0 || n < 0) {

									      return 1;

									    } else if (a.charat(m) == b.charat(n)) {

									      return editdistance(a, m - 1, b, n - 1);

									    } else {

									      return math.min(math.min(editdistance(a, m - 1, b, n) + 1, editdistance(a, m, b, n - 1) + 1), editdistance(a, m - 1, b, n - 1) + 1);

									    }

									  }

update:

同时, 由编辑距离的动态规划方程我们可以看出, edit[m][n]可以由edit[m - 1][n - 1], edit[m - 1][n], edit[m][n - 1]得出, 而如果edit是一个二维数组的话, edit[m][n]可以由它的上, 左, 左上三个位置的元素通过条件判断得出. 亦即我们可以通过遍历二维数组, 然后通过回溯来计算当前值.

例如对于字符串s = "sailn"和t = "failing", 对二维数组进行初始化为:

m\n		f	a	i	l	i	n	g
	0	1	2	3	4	5	6	7
s	1	1
a	2
i	3
l	4
n	5

因为s[0] = s, t[0] = f, 则s[0] != t[0], 则对应于上述二维矩阵, edit[1][1] = min(edit[0][0], edit[0][1], edit[1][0]) + 1即edit[1][1] = min(0, 1, 1) + 1即edit[1][1] = 0 + 1 = 1.

m\n		f	a	i	l	i	n	g
	0	1	2	3	4	5	6	7
s	1	1	2	3	4	5	6	7
a	2	2	1
i	3
l	4
n	5

而对于s[1] = a, t[1] = a, s[1] = t[1], 则对应于二维矩阵, edit[2][2] = edit[1][1], 所以edit[2][2] = 1. 所以按照这种规则, 将上述二维矩阵填满则如下:

m\n		f	a	i	l	i	n	g
	0	1	2	3	4	5	6	7
s	1	1	2	3	4	5	6	7
a	2	2	1	2	3	4	5	6
i	3	3	2	1	2	3	4	5
l	4	4	3	2	1	2	3	4
n	5	5	4	3	2	2	2	3

所以, 两者的编辑距离为edit[m][n] = edit[5][7] = 3.

所以, 按照上述思路即动态规划的回溯解法的java版本可以如下进行:

									public static int editdistance(string a, string b) {

									    if (a == null || b == null) {

									      return -1;

									    }

									    int[][] matrix = new int[a.length() + 1][b.length() + 1];

									    for (int i = 0; i < a.length() + 1; i++) {

									      for (int j = 0; j < b.length() + 1; j++) {

									        if (i == 0) {

									          matrix[i][j] = j;

									        } else if (j == 0) {

									          matrix[i][j] = i;

									        } else {

									          if (a.charat(i - 1) == b.charat(j - 1)) {

									            matrix[i][j] = matrix[i - 1][j - 1];

									          } else {

									            matrix[i][j] = 1 + math.min(math.min(matrix[i - 1][j], matrix[i][j - 1]), matrix[i - 1][j - 1]);

									          }

									        }

									      }

									    }

									    return matrix[a.length()][b.length()];

									  }