La programmation dynamique est une méthode algorithmique pour résoudre des problèmes d'optimisation. Le concept a été introduit au début des années 1950 par Richard Bellman.
Comme dans la méthode diviser pour régner, la programmation dynamique consiste à résoudre un problème en le décomposant en sous-problèmes. cependant, ici, ils ne sont pas forcément indépendants.
Ensuite, la programmation dynamique permet de résoudre les sous-problèmes, des plus petits aux plus grands en stockant les résultats intermédiaires (technique de mémoisation).
Voici un exemple avec la mesure de proximité de deux chaînes de caractères.⚓︎
Considérons les deux « textes » "LAPIN" et "CAPRIN".
À quel point sont-ils proches ?
Pour répondre à cette question, on peut se demander quelle est la plus longue sous-suite commune à ces deux textes.
Définition
On appelle sous-suite d'une chaîne de caractères, une chaîne produite en enlevant zéro, un ou plusieurs caractères.
Par exemple, "AN" est une sous-suite de "LAPIN".
"AN' est aussi une sous-suite commune à "LAPIN" et "CAPRIN".
Dans certains cas, il peut y avoir plusieurs sous-suites communes de longueurs identiques. Par exemple les chaînes "abc" et "bac" admettent deux sous-suites communes de longueur 2 : "ac" et "bc".
On va donc plutôt calculer la longueur de la plus longue sous-suite commune aux deux textes.
La comparaison de "LAPIN" et "CAPRIN" donne ceci (sur fond vert les caractères "identiques", sur fond rouge les "différents") :
LAPIN
CAPRIN
La plus longue sous-suite commune est donc "APIN". Elle est de longueur 4.
Écrire la fonction lplssc (pour longueur plus longue sous-suite commune) qui prend en argument les deux textes à comparer (texte_a et texte_b) et renvoie la longueur de la plus longue sous-suite commune.
On propose deux versions de cette fonction : une version récursive utilisant la mémoïsation et une itérative.
Ces deux méthodes permettent deux approches de la programmation dynamique : une qui construit la solution en partant des problèmes simples et en les combinant (bottom up), et une autre qui part du problème initial, découpé en sous problèmes, eux mêmes découpés par des les appels récursifs, jusqu'au cas de base (c'est la technique top down).
Une approche consiste à déterminer les longueurs des plus longues sous-suites communes de toutes les versions de chaque texte :
la version à 0 caractère, la version à 1 caractère, etc. Il y a (1+len(texte_a)) × (1+len(texte_b)) cas à envisager.
En prenant encore une fois texte_a="LAPIN" et texte_b="CAPRIN", les différents cas envisagés apparaissent dans le tableau ci-dessous. On trouve dans chaque case la longueur de la plus longue sous-suite commune à chaque texte s'il s'arrêtait au caractère indiqué en début de ligne ou de colonne.
Ainsi, le 1 au bout de la double flèche est la longueur de la plus longue sous-suite commune aux textes "LA" et "CAPRI".
On constate que :
la première colonne et la première ligne du tableau ne contiennent que des 0. C'est en effet la longueur de la plus longue sous-suite commune dans le cas où l'un des textes est vide ;
si les derniers caractères considérés sont identiques, ce caractère commun fait partie de la sous-suite commune. On peut le supprimer et ajouter 1 au résultat de la case au dessus à gauche (flèche en diagonale);
si les derniers caractères considérés diffèrent, l'un des deux caractères (ou les deux) ne fait pas partie de la sous-suite commune. On compare les valeurs des cases de gauche et du dessus (flèches horizontale et verticale).
Version récursive
Cette fonction fait appel à la fonction récursive lplssc_rec qui prend en paramètres le nombre de caractères de chaque texte à comparer taille_a et taille_b. Cette fonction renvoie la longueur de la plus longue sous-suite commune aux taille_a premiers caractères de texte_a et aux taille_b premiers caractères de texte_b.
Par exemple, avec texte_a="LAPIN" et texte_b="CAPRIN", l'appel lplssc_rec(2,5) renvoie la longueur de la plus longue sous-suite commune à "LA" et "CAPRI".
On gardera trace des résultats intermédiaires dans un dictionnaire longueurs qui, à chaque couple (taille_a, taille_b), associe la longueur de la plus longue sous-suite commune.
La fonction étant récursive, on débutera par l'appel prenant en compte tous les caractères de chaque texte.
###(Dés-)Active le code après la ligne # Tests (insensible à la casse) (Ctrl+I)
Entrer ou sortir du mode "deux colonnes" (Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran" (Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Dans cette version itérative on détermine là encore les longueurs des plus longues sous-suites communes de toutes les versions de chaque texte.
On peut toutefois remarquer que les deux formules de récurrences (derniers caractères identiques ou différents) ne font intervenir que deux lignes à la fois. On peut donc compléter le tableau ligne par ligne en partant de la première et en ne gardant trace que de la dernière ligne complétée.
###(Dés-)Active le code après la ligne # Tests (insensible à la casse) (Ctrl+I)
Entrer ou sortir du mode "deux colonnes" (Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran" (Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)