Python使用回溯法子集树模板获取最长公共子序列(LCS)的方法
作者:罗兵 发布时间:2021-04-14 04:55:49
标签:Python,回溯法
本文实例讲述了Python使用回溯法子集树模板获取最长公共子序列(LCS)的方法。分享给大家供大家参考,具体如下:
问题
输入
第1行:字符串A
第2行:字符串B
(A,B的长度 <= 1000)
输出
输出最长的子序列,如果有多个,随意输出1个。
输入示例
belong
cnblogs
输出示例
blog
分析
既然打算套用回溯法子集树模板,那就要祭出元素-状态空间分析 * 。
以长度较小的字符串中的字符作为元素,以长度较大的字符串中的字符作为状态空间,对每一个元素,遍历它的状态空间,其它的事情交给剪枝函数!!!
解x的长度不固定,xi表示字符串b中的序号。
在处理每一个元素时,如果没有一个状态被选择(cnblogs中没一个字符被选取),那么程序无法去往下一个元素。
这确实是个不小的麻烦!!!思考了一天,终于想出办法了:扩充状态空间,增加一个状态q!如果元素选取了状态q,它是合法的。但是,状态q不加入解x内!!!
看一个直观的图:
至此,enjoy it!
代码
'''最长公共子序列'''
# 作者:hhh5460
# 时间:2017年6月3日
a = 'belong'
b = 'cnblogs'
x = [] # 一个解(长度不固定)xi是b中字符的序号
X = [] # 一组解
best_x = [] # 最佳解
best_len = 0 # 最大子序列长度
# 冲突检测
def conflict(k):
global n, x, X, a,b,best_len
# 如果两个字符不相等
if x[-1] < len(b) and a[k] != b[x[-1]]:
return True
# 如果两个字符相等,但是相对于前一个在b中的位置靠前
if a[k] == b[x[-1]] and (len(x) >= 2 and x[-1] <= x[-2]):
return True
# 如果部分解的长度加上后面a剩下的长度,小于等于best_len
if len(x) + (len(a)-k) < best_len:
return True
return False # 无冲突
# 回溯法(递归版本)
def LCS(k): # 到达a中的第k个元素
global x, X,a,b,best_len,best_x
#print(k, x)
if k == len(a): # 超出最尾的元素
if len(x) > best_len:
best_len = len(x)
best_x = x[:]
else:
for i in range(len(b)+1): # 遍历 状态空间:0~len(b)-1,技巧:人为增加一种状态len(b),表示改行没有元素选取
if i==len(b): # 此状态不放入解x内
LCS(k+1)
else:
x.append(i)
if not conflict(k): # 剪枝
LCS(k+1)
x.pop() # 回溯
# 根据一个解x,构造最长子序列lcs
def get_lcs(x):
global b
return ''.join([b[i] for i in x])
# 测试
LCS(0)
print(b)
print(best_x)
print(get_lcs(best_x))
效果图
希望本文所述对大家Python程序设计有所帮助。
来源:http://%cnbcom%/hhh5460/p/6936384.html
0
投稿
猜你喜欢
- Array可以使用下标,Map和Set不能使用下标,ES6引入了iterable类型,Array,Map,Set都属于iterable类型,
- Sql Server为每个触发器都创建了两个专用表:Inserted表和Deleted表。这两个表由系统来维护,它们存在于内存中
- 本文实例讲述了Python中的单继承与多继承。分享给大家供大家参考,具体如下:单继承一、介绍Python 同样支持类的继承,如果一种语言不支
- 密钥密码'''如密钥短语密码为: university -> universty明文: abcdefghijk
- 无法装载DLL Microsoft原因: 126(找不到指定的模块)。 U890帐套引入提示:“无法装载 DLL Microsoft提示您请
- 目录前言一.数据库基础知识1.什么是数据库2.数据库的分类3.数据库的常用语言4.数据库的常用操作方式5.MySQL的架构二.数据库的增删改
- folium是python的一个用来绘制地图,并在地图上打点,画圈,做颜色标记的工具类。简单易学,和pandas可以很好的融合,是居家必备良
- 在你的程序初始化时使用如下代码: <?php $Php2Html_FileUrl = $_SERVER["REQU
- 本文实例讲述了php+mysql删除指定编号员工信息的方法。分享给大家供大家参考。具体分析如下:利用php提交员工编号给mysql,然后由m
- 1. Single array iteration>>> a = np.arange(6).reshape(2,3)>
- <% Response.Buffer = True Server.ScriptTimeOut=9999999&
- 一、Remoting基础什么是Remoting,简而言之,我们可以将其看作是一种分布式处理方式。从微软的产品角度来看,可以说Remoting
- python多进程下实现日志记录按时间分割,供大家参考,具体内容如下原理:自定义日志handler继承TimedRotatingFileHa
- 大家好,我是海拥,在今天的博客中,我们将讨论 Python 中简化代码的技巧。我清楚地记得当我选择学习 python 时,最令我震惊的是它的
- 1 发送文本信息'''加密发送文本邮件'''def sendEmail(from_addr,
- 利用Python进行数据分析时,Numpy是最常用的库,经常用来对数组、矩阵等进行转置等,有时候用来做数据的存储。在numpy中,转置tra
- 本文实例为大家分享了python rsync服务器之间文件夹同步的具体代码,供大家参考,具体内容如下About rsync配置两
- 发送端可以不停的发送新文件,接收端可以不停的接收新文件。例如:发送端输入:e:\visio.rar,接收端会默认保存为 e:\new_vis
- 目录1. 正则表达式_匹配单个字符2. 正则表达式_匹配多个字符3. 正则表达式_匹配分组小提示:4. 小练习答案:总结1. 正则表达式_匹
- 本文实例为大家分享了python使用matplotlib绘制雷达图的具体代码,供大家参考,具体内容如下示例代码:# encoding: ut