Sous-structure et Chevauchement des Sous-problèmes

1. Le symptôme : le chevauchement des sous-problèmes

Le signe le plus visible qu'une approche récursive naïve est inefficace — et que la programmation dynamique pourrait être la solution — est la répétition massive des mêmes calculs.

Considérons l'exemple le plus canonique : le calcul du n-ième terme de la suite de Fibonacci, définie par :
$F(n)=\{\begin{array}{ll}n& \text{si }n\le 1\\ F(n-1)+F(n-2)& \text{si }n>1\end{array}$
Une traduction directe en fonction récursive est simple, mais observons l'arbre des appels pour calculer F(6) :

Ce phénomène où une même sous-tâche (par exemple, le calcul de F(3)) est résolue à de multiples reprises est appelé le chevauchement des sous-problèmes (overlapping subproblems). C'est le premier des deux piliers de la programmation dynamique.

Pour approfondir cette idée avec des exemples concrets, je vous propose de lire les premières sections du document suivant, qui illustre ce concept non seulement avec Fibonacci mais aussi avec le calcul des coefficients du binôme.

2. Le principe fondamental : la sous-structure optimale

Le chevauchement des sous-problèmes nous indique qu'il y a une inefficacité à corriger. Mais la raison pour laquelle la programmation dynamique fonctionne repose sur une propriété plus profonde : la sous-structure optimale.

Un problème présente une sous-structure optimale si une solution optimale du problème global peut être construite à partir des solutions optimales de ses sous-problèmes.

Vous avez déjà intuitivement rencontré ce principe. Dans l'algorithme de Dijkstra, si le plus court chemin de A à C passe par B, alors le segment de chemin de A à B est nécessairement le plus court chemin de A à B. La solution optimale globale contient des solutions optimales locales.

La vidéo suivante introduit la programmation dynamique sous cet angle, en posant la question fondamentale de la structure d'une solution optimale.

Pour formaliser cela, étudions un autre problème classique : le rendu de monnaie.

• Problème : Étant donné un système de pièces (ex: {1, 5, 10, 25}) et une somme S à rendre, quel est le nombre minimum de pièces à utiliser ?
• Sous-structure optimale : Supposons que nous ayons une solution optimale pour rendre la somme S. Cette solution utilise une première pièce, disons de valeur c. Le reste des pièces utilisées doit alors obligatoirement constituer une solution optimale pour rendre la somme S-c. Si ce n'était pas le cas, on pourrait remplacer cette partie de la solution par une meilleure, ce qui améliorerait notre solution globale pour S, contredisant son optimalité.

L'optimalité de la solution globale dépend directement de l'optimalité des solutions des sous-problèmes. Cette propriété nous permet de formuler une équation de récurrence. Si N(S) est le nombre minimal de pièces pour la somme S, alors :
$N(S)=1+{\min }_{c\in \text{pieˋces}}\{N(S-c)\}$
Le document PDF que vous avez commencé à lire formalise cette déduction de manière très claire.

3. Synthèse : Diviser pour Régner vs. Programmation Dynamique

Un problème doit posséder à la fois une sous-structure optimale et des sous-problèmes qui se chevauchent pour que la programmation dynamique soit la bonne approche.

Cela la distingue d'une autre technique que vous connaissez bien : diviser pour régner (utilisée par exemple dans le tri fusion).

• Diviser pour régner : Les sous-problèmes sont indépendants. Pour trier un tableau, on trie la moitié gauche et la moitié droite séparément. Le travail n'est jamais dupliqué.
• Programmation dynamique : Les sous-problèmes se chevauchent. Le calcul de F(n) et F(n-1) requièrent tous les deux le calcul de F(n-2).

L'image suivante illustre cette différence fondamentale.

La ressource suivante, issue d'un cours du MIT, résume parfaitement ces deux "marques de fabrique" de la programmation dynamique.

4. Exercice d'identification

Mettons en pratique votre nouvelle compétence de diagnostic. Considérez le problème de la plus longue sous-séquence commune (LCS - Longest Common Subsequence), que nous étudierons en détail plus tard.

• Définition : Une sous-séquence est obtenue en supprimant zéro, un ou plusieurs caractères d'une chaîne. Par exemple, "ACE" est une sous-séquence de "ABCDE".
• Problème : Étant donné deux chaînes X et Y, trouver la longueur de la plus longue sous-séquence qui soit commune aux deux.

Exemple : Pour X = "AGGTAB" et Y = "GXTXAYB", la LCS est "GTAB" de longueur 4.

Votre tâche est de répondre aux deux questions suivantes (sans écrire de code) :

1. Sous-structure optimale : Comment la solution pour X et Y dépend-elle des solutions pour des versions plus petites de X et Y (c'est-à-dire leurs préfixes) ?
   Indice : Soit X_i le préfixe de X de longueur i et Y_j celui de Y de longueur j. Considérez deux cas : X[i] == Y[j] et X[i] != Y[j]. Comment la longueur de LCS(X_i, Y_j) se déduit-elle de LCS(X_{i-1}, Y_j), LCS(X_i, Y_{j-1}) ou LCS(X_{i-1}, Y_{j-1}) ?

2. Chevauchement des sous-problèmes : Si vous écriviez une fonction récursive longueur_lcs(i, j) qui calcule la longueur de la LCS pour les préfixes X_i et Y_j, pourquoi des appels redondants se produiraient-ils ?

Prenez quelques minutes pour y réfléchir avant de lire la solution.

Conclusion

Aujourd'hui, nous avons posé les fondations théoriques de la programmation dynamique. Vous devriez maintenant être capable de définir et d'identifier ses deux caractéristiques essentielles :

1. La sous-structure optimale : La solution optimale d'un problème se compose de solutions optimales de ses sous-problèmes. C'est ce qui nous permet d'écrire une relation de récurrence.
2. Le chevauchement des sous-problèmes : Une résolution récursive naïve calcule de nombreuses fois les mêmes sous-problèmes, ce qui rend l'approche exponentielle. C'est cette redondance que la programmation dynamique vise à éliminer.

La reconnaissance de ces deux propriétés est la compétence la plus fondamentale. Avant même d'écrire une ligne de code, un bon algorithmicien doit être capable de diagnostiquer un problème et de dire : "Ceci est un problème de programmation dynamique".

Dans notre prochaine leçon, nous passerons à la pratique. Nous verrons comment transformer cette analyse en algorithmes concrets en comparant les deux approches principales : l'approche descendante (avec mémoïsation) et l'approche ascendante (par tabulation).