您的位置:永利集团登录网址 > 永利集团登录网址 > Python使用回溯法子集树模板获取最长公共子序列

Python使用回溯法子集树模板获取最长公共子序列

2019-10-04 12:12

不知道大家对于Python使用回溯法子集树模板获取最长公共子序列(LCS)知道多少呢?今天忽然想起,小编就给大家整理下它具体的获取方法,感兴趣的一起来了解下。

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

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

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

输入

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

输出

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

输入示例

belong
cnblogs

输出示例

blog

分析

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

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

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

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

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

看一个直观的图:

图片 1

至此,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))

效果图

 图片 2

更多关于Python相关内容可查看本站专题:《Python数据结构与算法教程》、《Python Socket编程技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》及《Python文件与目录操作技巧汇总》

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

本文实例讲述了Python使用回溯法子集树模板获取最长公共子序列(...

Python基于回溯法子集树模板解决选排问题示例,python回溯

本文实例讲述了Python基于回溯法子集树模板解决选排问题。分享给大家供大家参考,具体如下:

问题

从n个元素中挑选m个元素进行排列,每个元素最多可重复r次。其中m∈[2,n],r∈[1,m]。

如:从4个元素中挑选3个元素进行排列,每个元素最多可重复r次。

分析

解x的长度是固定的,为m。

对于解x,先排第0个位置的元素x[0],再排第1个位置的元素x[1]。我们把后者看作是前者的一种状态,即x[1]是x[0]的一种状态!!

一般地,把x[k]看作x[k-1]的状态空间a中的一种状态,我们要做的就是遍历a[k-1]的所有状态。

那么,套用子集树模板即可。

代码

'''
选排问题
从n个元素中挑选m个元素进行排列,每个元素最多可重复r次。其中m∈[2,n],r∈[1,m]。
作者:hhh5460
时间:2017年6月2日 09时05分
声明:此算法版权归hhh5460所有
'''
n = 4
a = ['a','b','c','d']
m = 3  # 从4个中挑3个
r = 2  # 每个元素最多可重复2
x = [0]*m  # 一个解(m元0-1数组)
X = []   # 一组解
# 冲突检测
def conflict(k):
  global n, r, x, X, a
  # 部分解内的元素x[k]不能超过r
  if x[:k+1].count(x[k]) > r:
    return True
  return False # 无冲突
# 用子集树模板实现选排问题
def perm(k): # 到达第k个元素
  global n,m, a, x, X
  if k == m: # 超出最尾的元素
    print(x)
    #X.append(x[:]) # 保存(一个解)
  else:
    for i in a: # 遍历x[k-1]的状态空间a,其它的事情交给剪枝函数!
      x[k] = i
      if not conflict(k): # 剪枝
        perm(k+1)
# 测试
perm(0) # 从x[0]开始排列

效果图

 图片 3

更多关于Python相关内容可查看本站专题:《Python数据结构与算法教程》、《Python Socket编程技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》及《Python文件与目录操作技巧汇总》

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

本文实例讲述了Python基于回溯法子集树模板解决选排问题。分享给大家供大家参考...

问题

输入

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

输出

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

输入示例

belong cnblogs

输出示例

blog

分析

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

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

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

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

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

看一个直观的图:

图片 4

至此,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))

效果图

图片 5

本文由永利集团登录网址发布于永利集团登录网址,转载请注明出处:Python使用回溯法子集树模板获取最长公共子序列

关键词:

  • 上一篇:没有了
  • 下一篇:没有了