Java动态规划之编辑距离问题示例代码
作者:SilentKnight 发布时间:2023-10-30 00:21:21
动态规划过程是:每次决策依赖于当前状态,又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划。
动态规划实际上是一类题目的总称,并不是指某个固定的算法。动态规划的意义就是通过采用递推(或者分而治之)的策略,通过解决大问题的子问题从而解决整体的做法。动态规划的核心思想是巧妙的将问题拆分成多个子问题,通过计算子问题而得到整体问题的解。而子问题又可以拆分成更多的子问题,从而用类似递推迭代的方法解决要求的问题。问题描述:
对于序列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代码表示:
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()];
}
来源:http://www.cnblogs.com/littlepanpc/p/7895810.html
猜你喜欢
- 前言在工作中,比如要实现一个功能,前端传什么参数,后端的controller层中怎么接收参数 ,封装成了什么实体对象,有些参数是在URL上使
- 如何将ResultSet结果集遍历到List中今天在使用jstl标签展示查询结果时遇到一个小问题,即如何将ResultSet对象传递给前台页
- 背景:日常开发ERP系统,会有一些工单或者合同之类需要填写打印。我们就会将其word模板来通过系统自动化填写并转换为PDF格式(PDF文件打
- 如下所示:class Program {
- 之前代码有一个逻辑,是在初始化时读取某个包下的所有class文件,放入到一个HashMap里。代码运行过程中,通过Key获取到对应class
- Java 线程池原理Executor框架的两级调度模型在HotSpot VM的模型中,Java线程被一对一映射为本地操作系统线程。JAVA线
- 1 运算符1.1 概述运算符 用于连接 表达式 的 操作数,并对操作数执行运算。例如,表达式num1+num2,其操作数是num1和num2
- 在application.xml加上以下配置mybatis-plus.configuration.map-underscore-to-cam
- 提到java里的注解,和我们平时的注释还是有很大的区别,主要是作为java特性来使用的,跟我们常见的类是同一个使用的层面。关于java注解的
- TimeSpan 结构 表示一个时间间隔。命名空间:System 程序集:mscorlib(在 mscorlib.dll 中)说
- 冒泡排序冒泡排序是一种比较简单的排序算法,我们可以重复遍历要排序的序列,每次比较两个元素,如果他们顺序错误就交换位置,重复遍历到没有可以交换
- 效果展示人脸支付效果视频密码框输入支付效果视频因为密码支付时会调起系统安全键盘,开启自动保护功能,防止泄露,会导致输入密码时录屏黑屏,故使用
- 1.为项目添加POIPOI官网链接点进去之后下载(上边的是编译好的类,下边的是源代码) 解压文件夹,把下面三个文件复制到WebCo
- 这篇文章主要介绍了Java List分页功能实现代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的
- 基本操作import org.apache.hadoop.conf.Configuration;import org.apache.hado
- 本文实例讲述了java实现word文档转pdf并添加水印的方法。分享给大家供大家参考,具体如下:前段时间,项目需要自动生成word文档,用W
- Java 实现FTP服务实例详解1、FTP简介 FTP
- 在查询时经常出现一对多”的关系,所有会出现嵌套对象的情况,Mybatis在resultMap提供了collection标
- 0. Iochttps://docs.spring.io/spring-framework/docs/current/spring-fram
- 在传统的单服务架构中,一般来说,只有一个服务器,那么不存在 Session共享问题,但是在分布式/集群项目中,Session 共享则是一个必