實例詳解Python使用回溯法子集樹模板取得最長公共子序列問題

這篇文章主要介紹了Python使用回溯法子集樹模板獲取最長公共子序列（LCS）的方法,簡單描述了最長公共子序列問題並結合實例形式分析了Python基於回溯法子集樹模板取得最長公共子序列的操作步驟與相關注意事項,需要的朋友可以參考下

本文實例講述了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 &#39;&#39;.join([b[i] for i in x])
# 测试
LCS(0)
print(b)
print(best_x)
print(get_lcs(best_x))

#效果圖

# 

###################### ######

以上是實例詳解Python使用回溯法子集樹模板取得最長公共子序列問題的詳細內容。更多資訊請關注PHP中文網其他相關文章！