Bonjour,
Dans notre leçon précédente, nous avons établi une distinction claire entre les approches de programmation dynamique descendante (mémoïsation) et ascendante (tabulation), en utilisant le cas unidimensionnel de la suite de Fibonacci. Vous avez appris à implémenter ces deux stratégies et à analyser leurs compromis respectifs.
Aujourd'hui, nous allons appliquer ces fondements à un problème plus complexe et fondamental en algorithmique : la plus longue sous-séquence commune (ou Longest Common Subsequence, LCS). Ce problème opère sur deux séquences, nous forçant à raisonner en deux dimensions.
L'objectif de cette leçon est de vous apprendre à accomplir l'étape la plus critique de la résolution d'un problème par programmation dynamique : la formulation de la relation de récurrence. Nous nous concentrerons sur la longueur de la LCS, laissant l'implémentation effective pour notre prochaine session. La maîtrise de cette étape de modélisation est une compétence essentielle, fréquemment évaluée à l'agrégation.
1. Définition du problème : Sous-séquence vs Sous-chaîne
Avant toute chose, il est impératif de distinguer une sous-séquence d'une sous-chaîne (ou substring).
- Une sous-chaîne est une suite de caractères contigus. "algo" est une sous-chaîne de "algorithmique".
- Une sous-séquence est une suite de caractères qui apparaissent dans le même ordre, mais pas nécessairement de manière contiguë. "agro" est une sous-séquence de "algorithmique", mais pas une sous-chaîne.
Le problème de la LCS consiste à trouver la plus longue sous-séquence qui est commune à deux séquences données. Par exemple, pour les chaînes X = "AGGTAB" et Y = "GXTXAYB", la plus longue sous-séquence commune est "GTAB", de longueur 4.
La vidéo suivante, issue du cours d'algorithmique du MIT, définit le problème de manière claire et donne un exemple motivant.
16. Dynamic Programming, Part 2: LCS, LIS, Coins
Cette vidéo pose le problème de la LCS. Concentrez-vous sur la distinction entre sous-séquence et sous-chaîne, qui est cruciale.
Regardez la section de 03:51 à 06:19. Notez bien la définition du problème et l'exemple donné (hieroglyphology et michelangelo).
2. Étape 1 : Définir les sous-problèmes
Pour résoudre ce problème avec la programmation dynamique, nous devons le décomposer en sous-problèmes qui se chevauchent. Comme nous avons deux chaînes en entrée, disons X de longueur m et Y de longueur n, un sous-problème devra être défini par l'état d'avancement dans chacune des deux chaînes.
La manière la plus naturelle de procéder est d'utiliser les préfixes des chaînes. Nous allons définir un sous-problème par un couple d'indices (i, j), où i représente la longueur du préfixe de X considéré, et j la longueur du préfixe de Y.
Posons X = x_1x_2...x_m et Y = y_1y_2...y_n.
Nous noterons X_i = x_1...x_i et Y_j = y_1...y_j les préfixes de longueur i et j.
Le sous-problème que nous cherchons à résoudre est donc :
"Quelle est la longueur de la plus longue sous-séquence commune à X_i et Y_j ?"
Nous noterons c[i, j] cette longueur. Notre objectif final sera de calculer c[m, n].
3. Étape 2 : Formuler la relation de récurrence
C'est le cœur de notre leçon. Nous allons établir une relation qui lie c[i, j] aux solutions de sous-problèmes plus petits. Pour ce faire, nous examinons les derniers caractères des préfixes considérés : x_i et y_j. Deux cas se présentent.
Cas 1 : Les derniers caractères sont identiques (x_i = y_j)
Si x_i = y_j, ce caractère commun peut clore une plus longue sous-séquence commune de X_i et Y_j. On peut démontrer (par un argument de type "couper-coller") qu'il existe une LCS de X_i et Y_j qui se termine par x_i (=y_j).
La longueur de cette LCS est donc 1 (pour ce caractère commun) plus la longueur de la LCS des préfixes restants, X_{i-1} et Y_{j-1}.
On a donc : c[i, j] = 1 + c[i-1, j-1].
Cas 2 : Les derniers caractères sont différents (x_i ≠ y_j)
Si x_i et y_j sont différents, ils ne peuvent pas être tous les deux le dernier caractère d'une même sous-séquence commune. Une LCS de X_i et Y_j doit donc être soit une LCS de X_{i-1} et Y_j (on "ignore" x_i), soit une LCS de X_i et Y_{j-1} (on "ignore" y_j). Comme nous cherchons la plus longue, nous prenons le maximum des longueurs de ces deux possibilités.
On a donc : c[i, j] = max(c[i-1, j], c[i, j-1]).
Cas de base
Enfin, si l'un des préfixes est vide (i=0 ou j=0), la plus longue sous-séquence commune est nécessairement la chaîne vide, de longueur 0.
On a donc : c[i, 0] = 0 pour tout i, et c[0, j] = 0 pour tout j.
Formalisation
Pour une préparation à l'agrégation, une compréhension formelle de cette dérivation est indispensable. Le document suivant, issu de l'ENS Rennes, formalise cette intuition sous la forme d'un théorème de structure, puis en déduit la relation de récurrence.
Plus longue sous-séquence commune - Minerve de l'ENS Rennes
Ce document formalise la structure des LCS et en déduit la récurrence. C'est une lecture courte mais dense, représentative du niveau de rigueur attendu.
Lisez attentivement le "Théorème 1 : de structure des plus longues sous-séquences communes" et sa démonstration (même si elle est rapide). Ensuite, lisez la section qui suit, jusqu'à la formule de récurrence (1). Notez que ce document utilise des mots indexés à partir de 1 et compare les derniers caractères xm et yn, ce qui est analogue à notre raisonnement sur xi et yj.
Pour compléter cette lecture formelle, le document ci-dessous, de l'ENS de Lyon, présente la même récurrence avec une justification textuelle très claire qui peut vous aider à consolider votre compréhension.
plus longue sous-séquence commune - Corrigé TD ENS Lyon
Ce corrigé de TD propose une justification alternative et très bien rédigée de la formule de récurrence.
Lisez la première question de la section "Résolution par programmation dynamique". Attardez-vous sur les paragraphes qui justifient les deux cas de la récurrence. La lecture du code récursif n'est pas nécessaire pour l'instant.
En rassemblant ces éléments, nous obtenons la relation de récurrence complète pour c[i, j], la longueur de la LCS de X_i et Y_j :
Cette formule est le plan de construction de notre algorithme. Elle nous dit exactement comment calculer la solution pour un problème (i, j) à partir de solutions de problèmes "plus petits" ((i-1, j), (i, j-1), (i-1, j-1)).
Conclusion
Aujourd'hui, vous avez franchi l'étape conceptuelle la plus importante pour résoudre le problème de la plus longue sous-séquence commune. Vous êtes passé d'un problème unidimensionnel à un problème bidimensionnel, ce qui est un saut de complexité significatif.
Points clés à retenir :
- Le problème de la LCS se prête à la programmation dynamique car il possède une sous-structure optimale (la LCS de deux chaînes est construite à partir de la LCS de leurs préfixes) et des sous-problèmes qui se chevauchent.
- La clé est de définir le sous-problème à l'aide de deux indices,
c[i, j], représentant la longueur de la LCS des préfixesX_ietY_j. - La relation de récurrence est dérivée en analysant les deux cas possibles pour les derniers caractères des préfixes : soit ils sont égaux, soit ils sont différents.
- La formule de récurrence complète (incluant les cas de base) constitue le cahier des charges pour l'implémentation de l'algorithme.
Dans notre prochaine leçon, nous mettrons en pratique cette relation de récurrence. Vous implémenterez une solution par tabulation (bottom-up) en Python, qui consistera à remplir une table c de dimensions (m+1) x (n+1) pour calculer c[m, n].