这篇文章主要介绍了python使用回溯法子集树模板获取最长公共子序列（lcs）的方法,简单描述了最长公共子序列问题并结合实例形式分析了python基于回溯法子集树模板获取最长公共子序列的操作步骤与相关注意事项,需要的朋友可以参考下
本文实例讲述了Python使用回溯法子集树模板获取最长公共子序列（LCS）的方法。分享给大家供大家参考，具体如下：
问题
输入
第1行：字符串A
第2行：字符串B
(A,B的长度
立即学习“Python免费学习笔记（深入）”；
输出
输出最长的子序列，如果有多个，随意输出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] = 2 and x[-1] 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，构造最长子序列lcsdef 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使用回溯法子集树模板获取最长公共子序列问题的详细内容，更多请关注【创想鸟】其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至253000106@qq.com举报，一经查实，本站将立刻删除。
发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/2266561.html
