Python使用回溯法子集树模板获取最长公共子序列（LCS）的方法

脚本专栏 2024/11/7 佚名

3 2 1

圆月山庄资源网 Design By www.vgjia.com

本文实例讲述了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相关内容可查看本站专题：《Python数据结构与算法教程》、《Python Socket编程技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》及《Python文件与目录操作技巧汇总》

希望本文所述对大家Python程序设计有所帮助。

Python,回溯法,子集树模板,最长公共子序列,LCS

标签：

Python,回溯法,子集树模板,最长公共子序列,LCS

圆月山庄资源网 Design By www.vgjia.com

广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）
免责声明：本站文章均来自网站采集或用户投稿，网站不提供任何软件下载或自行开发的软件！如有用户或公司发现本站内容信息存在侵权行为，请邮件告知！ 858582#qq.com

圆月山庄资源网 Design By www.vgjia.com

评论“Python使用回溯法子集树模板获取最长公共子序列（LCS）的方法”

暂无评论...

P70系列延期，华为新旗舰将在下月发布

3月20日消息，近期博主@数码闲聊站透露，原定三月份发布的华为新旗舰P70系列延期发布，预计4月份上市。

而博主@定焦数码爆料，华为的P70系列在定位上已经超过了Mate60，成为了重要的旗舰系列之一。它肩负着重返影像领域顶尖的使命。那么这次P70会带来哪些令人惊艳的创新呢？
根据目前爆料的消息来看，华为P70系列将推出三个版本，其中P70和P70 Pro采用了三角形的摄像头模组设计，而P70 Art则采用了与上一代P60 Art相似的不规则形状设计。这样的外观是否好看见仁见智，但辨识度绝对拉满。

更新日志

2024年11月07日

Python使用回溯法子集树模板获取最长公共子序列（LCS）的方法

Python,回溯法,子集树模板,最长公共子序列,LCS

Python 模拟购物车的实例讲解

python添加模块搜索路径方法

评论“Python使用回溯法子集树模板获取最长公共子序列（LCS）的方法”

P70系列延期，华为新旗舰将在下月发布

更新日志

友情链接