本文实例讲述了Python使用回溯法子集树模板获取最长公共子序列(LCS)的方法。分享给大家供大家参考,具体如下:
问题
输入
第1行:字符串A
第2行:字符串B
(A,B的长度 <= 1000)
输出
输出最长的子序列,如果有多个,随意输出1个。
输入示例
belong
cnblogs
输出示例
blog
分析
既然打算套用回溯法子集树模板,那就要祭出元素-状态空间分析大法。
以长度较小的字符串中的字符作为元素,以长度较大的字符串中的字符作为状态空间,对每一个元素,遍历它的状态空间,其它的事情交给剪枝函数!!!
解x的长度不固定,xi表示字符串b中的序号。
在处理每一个元素时,如果没有一个状态被选择(cnblogs中没一个字符被选取),那么程序无法去往下一个元素。
这确实是个不小的麻烦!!!思考了一天,终于想出办法了:扩充状态空间,增加一个状态q!如果元素选取了状态q,它是合法的。但是,状态q不加入解x内!!!
看一个直观的图:
至此,enjoy it!
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
'''最长公共子序列'''
# 作者: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://www.cnblogs.com/hhh5460/p/6936384.html