バックトラッキング手法サブセット ツリー テンプレートを使用して最長共通部分列問題を取得する Python の詳細な例

この記事では、Python がバックトラッキング法サブセット ツリー テンプレートを使用して最長共通部分列 (LCS) を取得する方法を主に紹介し、最長共通部分列問題について簡単に説明し、Python がバックトラッキング法サブセット ツリー テンプレートを使用してそれを分析する方法について説明します。最長共通部分列を取得するための操作手順と注意事項については、必要な友達は参考にしてください

この記事では、Python を使用してバックトラッキング サブセット ツリー テンプレートを使用して最長共通部分列 (LCS) を取得する方法について説明します。 。参考のために皆さんと共有してください。詳細は次のとおりです:

質問

入力

行 1: 文字列 A
行 2: 文字列 B
(A,B

Output

最長のサブシーケンスが複数ある場合は、任意に 1 つを出力します。

入力例

belong
cnblogs

出力例

blog

分析

バックトラッキングサブセットツリーテンプレートを適用する予定なので、要素状態を使用する必要があります空間分析方法。

文字列内のより短い長さの文字を要素として使用し、より長い長さの文字列内の文字を状態空間として使用します。要素ごとに、その状態空間をトラバースし、その他のことは枝刈り関数に任せます。 ！ ！

解決策 x の長さは固定されておらず、xi は文字列 b のシーケンス番号を表します。

各要素を処理するときに、状態が選択されていない (cnblogs 内の文字が選択されていない) 場合、プログラムは次の要素に進むことができません。

これは本当に大変なことです！ ！ ！ 1 日考えた結果、状態空間を拡張して状態 q を追加するという方法をついに見つけました。要素が状態 q を選択する場合、それは正当です。ただし、状態 q は解 x に加算されません。 ！ ！

直感的な画像を見てください:

さあ、お楽しみください!

コード

'''最长公共子序列'''
# 作者：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 中国語 Web サイトの他の関連記事を参照してください。