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
投稿
猜你喜欢
- Python 截取字符串使用 变量[头下标:尾下标],就可以截取相应的字符串,其中下标是从0开始算起,可以是正数或负数,下标可以为空表示取到
- 如何用ASP建立Index Server查询对象并为其参数赋值?我们有两个方法可以做到这一点。一个方法是利用Index Server que
- 在这篇文章中,我们将讨论mask R-CNN背后的一些理论,以及如何在PyTorch中使用预训练的mask R-CNN模型。1.语义分割、目
- Oracle提供了不少方法用于数据空间的使用、监控和维护,同时也在各版本中陆续对这方面的功能进行了增强,目的在于简化这方面工作的复杂度,提高
- 使用scipy.optimize模块的root和fsolve函数进行数值求解线性及非线性方程,下面直接贴上代码,代码很简单from scip
- 行向量方式1import numpy as npb=np.array([1,2,3]).reshape((1,-1))print(b,b.s
- 函数局部变量 全局变量 及其作用域#简单类型(int str等)变量的局部变量与全局变量及其作用域的关系name = "xxx&q
- 如何在数据库中限制检索行数?为了照顾显示器屏幕的大小,使检索结果更整齐明了一些,请问,可以控制数据库的检索行数吗? &
- 一.ajax介绍1、ajax的含义Ajax全称“Async Javascript And XML”即:异步的javascript和XML。它
- 通过界面设计上是能手工操作的,无法达到我批量修改几千台服务器。 因为此了一个脚本来批量执行。 环境:redgate + mssql 2008
- 相关的题外话:一、操作系统window系统内部都是unicode的。文件夹名,文件名等都是unicode的,任何语言系统下都能正常显示。二、
- 本文实例讲述了PHP基于cookie与session统计网站访问量并输出显示的方法。分享给大家供大家参考,具体如下:<?php$f_o
- print函数的功能是打印图窗或保存为特定文件格式。语法print(filename,formattype)print(filename,f
- 对所有数据进行整合与管理当你使用SQL Server 2008企业级的数据仓库平台时,你可以高效的操纵所有数据,并对其进行统一管理存储。◆合
- AlexNet是2012年ImageNet比赛的冠军,虽然过去了很长时间,但是作为深度学习中的经典模型,AlexNet不但有助于我们理解其中
- 箱线图箱线图一般用来展现数据的分布,如上下四分位值、中位数等,也可以直观地展示异常点。Matplotlib提供了boxplot()函数绘制箱
- 这篇文章主要介绍了python Opencv计算图像相似度过程解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价
- 在oracle中,函数和存储过程是经常使用到的,他们的语法中有很多相似的地方,可是也有它们的不同之处,这段时间刚学完函数与存储过程,来给自己
- 在执行程序前,先在MySQL中创建一个数据库"pachong"。import pymysqlimport request
- 引言委托 和 事件在 .Net Framework中的应用非常广泛,然而,较好地理解委托和事件对很多接触C#时间不长的人来说并不容易。它们就