我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:大丰收高手论坛 > 动态规划法 >

如何用动态规划的方法求编辑距离

归档日期:06-10       文本归类:动态规划法      文章编辑:爱尚语录

  毕业于福建农林大学,本科学士学位。从事IT行业3年,曾参与过多个大型项目的需求调研、软件研发。其实就是把一个复杂的最优解问题分解成一系列较为简单的最优解问题,再将较为简单的最优解问题一步步分解,直到能够一眼看出为止。

  我们拿sailn和failing这两个字符串作例子。首先我们定义这样一个函数——edit(i, j),它表示字符串1的长度为i的子串到字符串2的长度为j的子串的编辑距离。

  首先我们作出初始化edit(0, j) = j(字符串1子串长度为0,字符串2子串有多少个字符,就作多少次增加操作;于是同理,edit(i, 0) = i。)

  这里,我们要注意到对于操作(4),即交换相邻字符串的操作,我们要把某个字符通过这个操作到另一个位置上,我们最多只能执行一次操作,即只能移动到邻位上。原因是什么呢?这是因为,移动两次的话,就没有优势了,它的操作等于两次替换操作的操作数。大于2次的时候,移动操作会更差。所以,我们要进行操作(4),最多只发生一次操作。

  如果i 1且 j 1时,这个时候可能出现操作(4),由之前的推导,我们只能交换一次,否则就没有意义。这个时候在比较最小值中可能加入edit(i-2, j-2) +1,什么时候加入呢?假设i-2长度的字符串1子串和j-2长度的字符串2子串已经得出最优解,这个时候如果s1[i-1] == s2[j] 并且s1[i] == s2[j-1],这时就在比较值中加入edit(i-2, j-2) + 1(这个1是交换一次的操作)

本文链接:http://quangdungfc.net/dongtaiguihuafa/313.html