La programmation dynamique
Cours · NSI (terminale), chapitre 7 · terminale, spécialité numérique et sciences informatiques · le début du chapitre, la suite sur Adloun
La programmation dynamique est une technique algorithmique puissante permettant de résoudre efficacement des problèmes d'optimisation et de dénombrement. Son principe fondamental consiste à décomposer un problème complexe en sous-problèmes plus simples, à résoudre chacun d'eux une seule fois, puis à mémoriser leurs solutions afin de les réutiliser. Cette approche évite de recalculer plusieurs fois les mêmes valeurs, ce qui transforme souvent un algorithme exponentiel en un algorithme polynomial.
Dans ce chapitre, nous étudierons les deux conditions qui rendent un problème soluble par programmation dynamique : la présence de sous-problèmes recouvrants et celle d'une sous-structure optimale. Nous présenterons les deux grandes stratégies de mise en œuvre, la mémoïsation descendante (top-down) et l'approche ascendante (bottom-up). De nombreux exemples emblématiques illustreront ces idées : la suite de Fibonacci optimisée, le rendu de monnaie, la plus longue sous-séquence commune et le problème du sac à dos. Enfin, nous comparerons la programmation dynamique avec les méthodes diviser-pour-régner et gloutonnes étudiées par ailleurs.
7.1 Principes fondamentaux
7.1.1 Sous-problèmes recouvrants et sous-structure optimale
Avant d'appliquer la programmation dynamique, il faut s'assurer que le problème possède deux propriétés essentielles. Sans elles, la technique n'apporte aucun gain, voire ne s'applique pas.
Un problème présente des sous-problèmes recouvrants (overlapping subproblems) lorsque sa résolution récursive amène à résoudre plusieurs fois exactement les mêmes sous-problèmes. La programmation dynamique tire parti de cette redondance en mémorisant chaque solution pour ne la calculer qu'une seule fois.
Le calcul récursif naïf de nécessite de calculer et ; mais recalcule à son tour et , etc. Ainsi est calculé deux fois, trois fois, et le nombre total d'appels croît de manière exponentielle. Les sous-problèmes se chevauchent massivement : c'est le signe qu'une mémorisation sera très bénéfique.
Un problème possède une sous-structure optimale (optimal substructure) lorsqu'une solution optimale du problème peut être construite à partir des solutions optimales de ses sous-problèmes. Cette propriété permet d'écrire une relation de récurrence reliant la solution globale aux solutions partielles.
La programmation dynamique est adaptée à un problème si et seulement si celui-ci présente à la fois :
- des sous-problèmes recouvrants (justifiant la mémorisation) ;
- une sous-structure optimale (justifiant la décomposition récursive).
Si les sous-problèmes sont indépendants (non recouvrants), la méthode diviser-pour-régner suffit. Si la sous-structure optimale est absente, aucune récurrence simple ne peut être établie.
7.1.2 Mémoïsation et approche ascendante
Une fois la relation de récurrence établie, deux stratégies permettent de la calculer efficacement.