가장 긴 공통 하위 시퀀스 문제를 얻기 위해 역추적 방법 하위 집합 트리 템플릿을 사용하는 Python의 자세한 예

이 기사에서는 역추적 방법 부분 집합 트리 템플릿을 사용하여 가장 긴 공통 부분 수열(LCS)을 구하는 Python의 방법을 주로 소개합니다. 가장 긴 공통 부분 수열 문제를 간략하게 설명하고 이를 예제와 결합하여 기반으로 가장 긴 공통 부분 수열을 구하는 Python의 방법을 분석합니다. 역추적 방법 부분 집합 트리 템플릿에 대해 긴 공통 부분 수열의 작업 단계 및 관련 주의 사항에 대해 도움이 필요한 친구들이 참조할 수 있습니다

이 기사에서는 가장 긴 공통 부분 수열을 얻기 위해 역추적 방법 부분 집합 트리 템플릿을 사용하는 Python의 예를 설명합니다( LCS). 참고를 위해 모든 사람과 공유하세요. 세부 사항은 다음과 같습니다.

Question

Input

Line 1: String A
Line 2: String B
(A,B<= 1000의 길이 )

Output

가장 긴 하위 시퀀스를 출력합니다. 여러 개가 있으면 임의로 하나씩 출력합니다.

입력 예제

belong
cnblogs

출력 예제

blog

Analytic

요소를 사용해야 합니다. 상태공간 분석 방법.

문자열에서 길이가 짧은 문자를 요소로 사용하고, 길이가 긴 문자열의 문자를 상태 공간으로 사용합니다. 각 요소에 대해 상태 공간을 순회하고 다른 사항은 잘라내기 기능에 맡깁니다. ! !

해결 방법 x의 길이는 고정되어 있지 않으며 xi는 문자열 b의 시퀀스 번호를 나타냅니다.

각 요소를 처리할 때 상태가 선택되지 않으면(cnblogs의 문자가 선택되지 않음) 프로그램은 다음 요소로 이동할 수 없습니다.

이건 정말 큰 문제입니다! ! ! 하루 동안 고민한 끝에 마침내 방법을 알아냈습니다. 상태 공간을 확장하고 상태 q를 추가하는 것이었습니다! 요소가 상태 q를 선택하면 합법적입니다. 그러나 상태 q는 솔루션 x에 추가되지 않습니다! ! !

직관적인 그림 보기:

이제 즐겨보세요!

Code

'''最长公共子序列'''
# 作者：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))

Rendering

위 내용은 가장 긴 공통 하위 시퀀스 문제를 얻기 위해 역추적 방법 하위 집합 트리 템플릿을 사용하는 Python의 자세한 예의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!