Exemple détaillé de Python utilisant un modèle d'arborescence de sous-ensembles de méthode de retour en arrière pour obtenir le problème de sous-séquence commune le plus long

Cet article présente principalement comment Python utilise le modèle d'arbre de sous-ensemble de méthode de retour en arrière pour obtenir la sous-séquence commune la plus longue (LCS). Il décrit brièvement le problème de sous-séquence commune la plus longue et analyse Python sur la base du modèle d'arbre de sous-ensemble de méthode de retour en arrière sous forme d'exemples. . Pour les étapes et les précautions associées pour obtenir la sous-séquence commune la plus longue, les amis dans le besoin peuvent se référer à

Cet article décrit la méthode d'utilisation de Python pour obtenir la sous-séquence commune la plus longue (LCS) à l'aide du modèle d'arborescence de sous-ensemble de retour en arrière. Partagez-le avec tout le monde pour votre référence, les détails sont les suivants :

Question

Entrer

Ligne n°1 : Chaîne A
Ligne 2 : Chaîne B
(longueur de A,B

Sortie

Sortie le plus Pour les sous-séquences longues, s'il y en a plusieurs, en sortez-en une à volonté.

Exemple de saisie

belong
cnblogs

Exemple de sortie

blog

Analyse

Puisque vous envisagez d'appliquer le modèle d'arborescence de sous-ensemble de retour en arrière, vous devez utiliser la méthode d'analyse spatiale élément-état.

Utilisez les caractères de la chaîne de plus petite longueur comme éléments et les caractères de la chaîne de plus grande longueur comme espace d'état. Pour chaque élément, parcourez son espace d'état et laissez le reste au cisaillement. fonction! ! !

La longueur de la solution x n'est pas fixe et xi représente le numéro de séquence dans la chaîne b.

Lors du traitement de chaque élément, si aucun état n'est sélectionné (aucun caractère dans cnblogs n'est sélectionné), alors le programme ne peut pas passer à l'élément suivant.

C'est en effet un gros problème ! ! ! Après avoir réfléchi une journée, j'ai finalement trouvé un moyen : étendre l'espace d'état et ajouter un état q ! Si l'élément sélectionne l'état q, c'est légal. Cependant, l’état q n’est pas ajouté à la solution x ! ! !

Regardez une image intuitive :

À ce stade, profitez-en !

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))

Rendu

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!