Laboratoire visuel : programmation dynamique

Chaque case intérieure de la table dépend de trois voisines : nord-ouest, nord et ouest. Déroulez le remplissage du code du cours, ou choisissez vous-même l’ordre des cases : une case n’est acceptée que si ses trois voisines sont déjà calculées.

Laboratoire visuel : programmation dynamique

Problème
Mode

Essayer :

Table vide

Lire la table en texte
    calculée en coursvoisines NO, N, Oremontée

    Compteurs

    Cases calculées0
    Appels de la version récursive0
    Valeur cherchée—

    Journal

      À explorer

      Les algorithmes suivis

      Les cases intérieures sont calculées par lignes, par colonnes croissantes, comme dans le code du cours ; les deux autres ordres sont des variantes qui respectent les mêmes dépendances. Pour la suite double, les bords valent 1 et f est choisie parmi trois fonctions.

      Suite double

      def suite_double(n, m, f, bord_gauche, bord_haut):
          T = [[0] * (m + 1) for _ in range(n + 1)]
          for i in range(n + 1):
              T[i][0] = bord_gauche(i)
          for j in range(1, m + 1):
              T[0][j] = bord_haut(j)
          for i in range(1, n + 1):
              for j in range(1, m + 1):
                  T[i][j] = f(T[i - 1][j - 1], T[i - 1][j], T[i][j - 1])
          return T

      Le compteur d’appels suit la version récursive directe :

      def suite_double_recursif(i, j, f, bord_gauche, bord_haut):
          if i == 0:
              return bord_haut(j)
          if j == 0:
              return bord_gauche(i)
          return f(suite_double_recursif(i - 1, j - 1, f, bord_gauche, bord_haut),
                   suite_double_recursif(i - 1, j, f, bord_gauche, bord_haut),
                   suite_double_recursif(i, j - 1, f, bord_gauche, bord_haut))

      Plus longue sous-suite commune

      def plsc_table(u, v):
          n, m = len(u), len(v)
          A = [[0] * (m + 1) for _ in range(n + 1)]
          provenance = [[None] * (m + 1) for _ in range(n + 1)]
          for i in range(n):
              for j in range(m):
                  if u[i] == v[j]:
                      A[i + 1][j + 1] = A[i][j] + 1
                      provenance[i + 1][j + 1] = "diag"
                  elif A[i][j + 1] >= A[i + 1][j]:
                      A[i + 1][j + 1] = A[i][j + 1]
                      provenance[i + 1][j + 1] = "haut"
                  else:
                      A[i + 1][j + 1] = A[i + 1][j]
                      provenance[i + 1][j + 1] = "gauche"
          return A, provenance
      from plsc_table import plsc_table
      
      
      def plsc(u, v):
          _, provenance = plsc_table(u, v)
          i, j = len(u), len(v)
          lettres = []
          while i > 0 and j > 0:
              if provenance[i][j] == "diag":
                  lettres.append(u[i - 1])
                  i, j = i - 1, j - 1
              elif provenance[i][j] == "haut":
                  i = i - 1
              else:
                  j = j - 1
          lettres.reverse()
          return "".join(lettres)

      Distance d’édition

      Un alignement écrit u au-dessus de v, avec des trous. Son coût est le nombre de colonnes où les deux symboles diffèrent. La distance d’édition est le plus petit de ces coûts.

      Dans la case (I, J), on examine la dernière colonne d’un alignement des préfixes u[:I] et v[:J].

      Dernière colonne Préfixes plus courts Coût ajouté
      u[I-1] / v[J-1] D[I-1][J-1] 0 si les lettres coïncident, 1 pour une substitution
      u[I-1] / – D[I-1][J] 1 pour une suppression
      – / v[J-1] D[I][J-1] 1 pour une insertion

      distance_edition.py renvoie seulement D[n][m]. Pour reconstruire un alignement, le laboratoire déduit chaque flèche des valeurs de la table, comme dans l’exercice du polycopié sur la PLSC sans table de provenance. En remontant jusqu’à (0, 0), il ajoute à gauche la dernière colonne de chaque paire de préfixes. Quand les lettres coïncident, il suit la diagonale.

      Sans substitutions, chaque colonne à deux lettres conserve une lettre commune. Avec k lettres conservées, il reste n + m − 2·k insertions et suppressions. Minimiser ce coût revient à choisir une plus longue sous-suite commune, de longueur A[n][m].

      def distance_edition(u, v):
          n, m = len(u), len(v)
          D = [[0] * (m + 1) for _ in range(n + 1)]
          for i in range(n + 1):
              D[i][0] = i
          for j in range(m + 1):
              D[0][j] = j
          for i in range(n):
              for j in range(m):
                  if u[i] == v[j]:
                      D[i + 1][j + 1] = D[i][j]
                  else:
                      D[i + 1][j + 1] = 1 + min(D[i][j], D[i][j + 1], D[i + 1][j])
          return D[n][m]