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

作者:罗兵 时间:2021-04-14 04:55:49 

本文实例讲述了Python使用回溯法子集树模板获取最长公共子序列(LCS)的方法。分享给大家供大家参考,具体如下:

问题

输入

第1行:字符串A
第2行:字符串B
(A,B的长度 <= 1000)

输出

输出最长的子序列,如果有多个,随意输出1个。

输入示例

belong
cnblogs

输出示例

blog

分析

既然打算套用回溯法子集树模板,那就要祭出元素-状态空间分析 * 。

以长度较小的字符串中的字符作为元素,以长度较大的字符串中的字符作为状态空间,对每一个元素,遍历它的状态空间,其它的事情交给剪枝函数!!!

解x的长度不固定,xi表示字符串b中的序号。

在处理每一个元素时,如果没有一个状态被选择(cnblogs中没一个字符被选取),那么程序无法去往下一个元素。

这确实是个不小的麻烦!!!思考了一天,终于想出办法了:扩充状态空间,增加一个状态q!如果元素选取了状态q,它是合法的。但是,状态q不加入解x内!!!

看一个直观的图:

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

至此,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使用回溯法子集树模板获取最长公共子序列(LCS)的方法

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

来源:http://%cnbcom%/hhh5460/p/6936384.html

标签:Python,回溯法
0
投稿

猜你喜欢

  • Python中PyAutoGUI帮助文档(推荐!)

    2022-12-18 20:50:16
  • python字典DICT类型合并详解

    2023-01-03 07:37:12
  • JavaScript大牛:Douglas Crockford

    2009-03-31 12:06:00
  • 用Python手把手教你实现2048小游戏

    2023-02-22 23:27:57
  • Vue3响应式对象Reactive和Ref的用法解读

    2024-05-02 16:34:48
  • asp无限级分类加js收缩伸展功能代码

    2009-12-08 12:25:00
  • python根据给定文件返回文件名和扩展名的方法

    2023-09-04 03:41:07
  • Pandas中两个dataframe的交集和差集的示例代码

    2022-05-24 14:52:37
  • Python常用标准库之os模块功能

    2022-03-03 03:49:59
  • keras 模型参数,模型保存,中间结果输出操作

    2023-06-05 09:52:33
  • ASP去掉字符串头尾连续回车和空格的Function

    2011-04-03 11:13:00
  • 解决mybatis使用char类型字段查询oracle数据库时结果返回null问题

    2024-01-26 03:05:05
  • 网页中插入视频播放代码全集

    2007-10-22 17:48:00
  • JavaScript风格要素

    2007-10-25 16:57:00
  • Numpy对于NaN值的判断方法

    2022-12-15 15:08:21
  • Python 实现定积分与二重定积分的操作

    2023-08-05 18:22:27
  • php实现的CSS更新类实例

    2023-11-21 22:28:30
  • Django框架安装及项目创建过程解析

    2022-09-20 12:55:45
  • Python实战项目用PyQt5制作漫画脸GUI界面

    2023-07-05 13:17:19
  • JS+CSS实现仿支付宝菜单选中效果代码

    2023-10-05 07:29:01
  • asp之家 网络编程 m.aspxhome.com