La programmation dynamique pas à pas : dériver la distance d'édition

Objectif

Résoudre un problème dont la réponse optimale se construit à partir de réponses optimales à des instances plus petites, et dont la récursion naïve recalcule les mêmes instances un nombre exponentiel de fois, en temps polynomial et avec une mémoire prévisible.

Prérequis

Deux propriétés : la sous-structure optimale (la meilleure solution contient les meilleures solutions à des sous-problèmes) et les sous-problèmes chevauchants (le nombre de sous-problèmes distincts est polynomial alors que l'arbre d'appels naïf ne l'est pas). L'exemple : la distance d'édition entre les chaînes a (de longueur m) et b (de longueur n), le nombre minimal d'insertions, de suppressions et de substitutions d'un seul caractère transformant a en b.

Étapes

1. Définir l'état comme le plus petit ensemble de paramètres qui identifie un sous-problème : D(i, j) est la distance d'édition entre les i premiers caractères de a et les j premiers caractères de b. La réponse est D(m, n).
2. Écrire les cas de base : D(i, 0) = i (tout supprimer) et D(0, j) = j (tout insérer).
3. Écrire la récurrence. Si a[i-1] == b[j-1], alors D(i, j) = D(i-1, j-1). Sinon D(i, j) = 1 + min(D(i-1, j), D(i, j-1), D(i-1, j-1)), les trois termes correspondant à la suppression, à l'insertion et à la substitution.
4. Compter les états : (m+1) * (n+1), chacun calculé en temps constant à partir de trois voisins, donc l'algorithme est en O(mn). La récursion naïve revisite D(i-1, j-1) depuis trois appelants et explose.
5. Mémoïser de façon descendante (top-down) : écrire la récurrence littéralement comme une fonction récursive et la décorer avec @functools.cache (documenté dans functools à côté de lru_cache). C'est le moyen le plus rapide d'obtenir une version correcte, mais la profondeur croît avec m + n, ce qui convient aux entrées courtes.
6. Tabuler de façon ascendante (bottom-up) : remplir une table ligne par ligne, car chaque cellule n'a besoin que de la ligne du dessus et de la cellule à sa gauche. Pour kitten et sitting, la table se termine par D(6, 7) = 3 : substituer k par s, substituer e par i, insérer g.
7. Réduire la mémoire : ne conserver que la ligne précédente et la ligne courante, ce qui donne un espace en O(min(m, n)). Conserver la table complète lorsque le script d'édition effectif est nécessaire, et remonter (backtrack) depuis D(m, n).
8. Vérifier par rapport à une méthode par force brute sur de petites chaînes aléatoires, ainsi que sur des chaînes vides, des chaînes identiques et des différences d'un seul caractère.

Résultat attendu

Une fonction en temps quadratique et en espace linéaire, dont la récurrence est écrite en commentaire à côté du code, vérifiée par rapport à un oracle par force brute.

Limites et base de vérification

Les problèmes dépourvus de sous-structure optimale (le plus long chemin simple dans un graphe) ne se prêtent pas à cette méthode. Les espaces d'états portant sur des sous-ensembles sont exponentiels par rapport à la taille de l'ensemble et ne sont praticables que pour de petites entrées. Les chiffres de l'exemple découlent de la récurrence par simple calcul ; aucune mesure de temps n'est revendiquée.