La programmation dynamique (PD) est une technique algorithmique qui résout les problèmes d'optimisation en les découpant en sous-problèmes plus petits et se chevauchant, chaque sous-problème n'étant résolu qu'une fois, ses résultats étant mémorisés pour éviter les recalculs. Elle s'épanouit sur les problèmes à sous-structure optimale et sous-problèmes qui se chevauchent.
Les principes clés
1. Sous-structure optimale
Un problème la possède si sa solution optimale se construit à partir des solutions optimales de ses sous-problèmes. Exemple : tout sous-chemin d'un plus court chemin entre deux villes est lui-même un plus court chemin.
2. Sous-problèmes qui se chevauchent
Le même sous-problème revient à plusieurs reprises. Le calcul récursif naïf de Fibonacci recalcule par exemple fib(3) plusieurs fois lors du calcul de fib(5).
3. Mémoïsation ou tabulation
La mémoïsation (haut-bas) décompose récursivement le problème et stocke chaque résultat (dans un dictionnaire ou une table de hachage) pour éviter les recalculs. La tabulation (bas-haut) calcule systématiquement tous les sous-problèmes, des plus petits au plus grand, en général dans un tableau.
4. État et transitions
Un état représente une configuration du problème ; bien le définir conditionne toute la solution, et son nombre détermine la complexité spatiale. Dans le sac à dos, un état peut être « (index, capacité) ». Les transitions décrivent comment calculer un état à partir des sous-problèmes, souvent sous forme d'équations récursives (par exemple fib(n) = fib(n-1) + fib(n-2)).
Les domaines d'application
Optimisation
- Chemins les plus courts : Floyd-Warshall (toutes paires) et Bellman-Ford (gère les poids négatifs).
- Sac à dos : versions 0/1, illimitée et fractionnaire.
- Plus longue sous-séquence commune (LCS) : bio-informatique, comparaison de fichiers, édition de texte.
- Multiplication de chaînes de matrices : ordre optimal pour minimiser les multiplications scalaires.
- Distance de Levenshtein : correcteurs orthographiques, séquençage d'ADN, TALN.
- Rendu de monnaie : nombre minimal de pièces ou nombre de façons d'atteindre un montant.
- Voyageur de commerce (Held-Karp) : solution exacte pour petites instances, impraticable au-delà (NP-difficile).
Analyse de séquences
Alignement d'ADN ou de protéines (Needleman-Wunsch global, Smith-Waterman local) et modèles de Markov cachés (algorithme de Viterbi pour la séquence d'états la plus probable).
Graphes, jeux et au-delà
Flots réseau maximaux ; stratégies optimales de jeux (Minimax avec élagage alpha-bêta) ; segmentation d'images ; justification de texte et césure ; contrôle optimal des systèmes.
Mémoïsation ou tabulation ?
- Mémoïsation : plus intuitive, ne calcule que le nécessaire, mais risque le dépassement de pile en récursion profonde.
- Tabulation : meilleure sur les facteurs constants (pas de surcharge de récursion), mais peut calculer des sous-problèmes inutiles et exige un ordre rigoureux.
La recette pour résoudre un problème de PD
- Définir l'état qui identifie un sous-problème.
- Établir les transitions vers les sous-problèmes plus petits.
- Poser les cas de base.
- Choisir mémoïsation ou tabulation pour calculer et stocker.
- Déterminer l'ordre de calcul (tabulation).
- Extraire la solution optimale depuis les résultats stockés.
Puissante mais exigeante, la programmation dynamique demande une analyse soignée et une conception propre à chaque problème. La maîtrise vient avec la pratique.