Programmation dynamique
Cours · informatique (MP2I/MPI), chapitre 17 · MP2I et MPI · le début du chapitre, la suite sur Adloun
17.1 Ne pas recalculer deux fois la même chose
Le chapitre chap:recursivite montrait l'arbre des appels de fib 4 : fib 2 y était calculé deux fois, fib 1 trois fois. Sur fib 40, ce gaspillage atteint appels — comptés, pas estimés — pour quarante valeurs distinctes.
La programmation dynamique est la méthode qui supprime ce gaspillage. Elle s'applique dès que deux conditions sont réunies — et le programme les nomme toutes les deux.
- Sous-structure optimale : une solution optimale du problème contient des solutions optimales de ses sous-problèmes. C'est ce qui autorise à résoudre les sous-problèmes indépendamment.
- Chevauchement des sous-problèmes : les mêmes sous-problèmes reviennent plusieurs fois. C'est ce qui rend la mémorisation rentable.
Le chapitre chap:diviser découpait en sous-problèmes disjoints — les deux moitiés d'un tableau ne se recoupent pas. Il n'y a alors rien à mémoriser.
Ici, les sous-problèmes se chevauchent. Mémoriser leurs solutions transforme un arbre d'appels exponentiel en un tableau de taille polynomiale. C'est le chevauchement qui fait toute la différence, et c'est la première chose à vérifier.
17.2 Deux manières de faire, une seule idée
Méthode : Par mémoïsation, ou de haut en bas
On garde la formulation récursive, et l'on retient chaque valeur calculée.
(* n-ième terme de Fibonacci. Précondition : n >= 0. Complexité : Theta(n). *)
let fib n =
let memo = Hashtbl.create 97 in
let rec aux k =
if k < 2 then k
else match Hashtbl.find_opt memo k with
| Some v -> v (* déjà calculé : on rend *)
| None ->
let v = aux (k - 1) + aux (k - 2) in
Hashtbl.add memo k v; (* on retient AVANT de rendre *)
v
in
aux nAvantage : le code reste celui de la définition, et l'on ne calcule que les sous-problèmes effectivement atteints.
Méthode : De bas en haut, par remplissage de table
On renverse l'ordre : on calcule les petits sous-problèmes d'abord, dans un tableau, jusqu'à celui qu'on veut.
/* n-ième terme de Fibonacci. Précondition : 0 <= n < TAILLE. */
long long fib(int n) {
assert(0 <= n && n < TAILLE);
long long t[TAILLE];
t[0] = 0;
t[1] = 1;
for (int k = 2; k <= n; k = k + 1) { t[k] = t[k - 1] + t[k - 2]; }
return t[n];
}Avantage : aucune récursion, donc aucune pile à faire déborder, et des accès mémoire contigus — donc rapides.
Bonne pratique (Réduire la mémoire quand on ne remonte pas)
Le programme demande de « souligner les enjeux de complexité en mémoire ». La version ci-dessus occupe pour ne consulter que deux cases à la fois :
long long a = 0, b = 1;
for (int k = 2; k <= n; k = k + 1) { long long c = a + b; a = b; b = c; }
/* b vaut fib(n) ; mémoire : Theta(1) */Cette réduction est fréquente et gratuite — mais attention : elle interdit la reconstruction de la solution, dont il est question plus bas. On ne réduit la mémoire qu'après avoir décidé qu'on n'aura pas besoin du chemin.
17.3 Le sac à dos
C'est l'exemple canonique, déjà rencontré en exhaustif au chapitre chap:exploration et en glouton approché au chapitre chap:gloutons.
Exercices du chapitre
- Le glouton et la dynamique ne rendent pas la même monnaie corrigé
- Somme d'un sous-ensemble, et un mot sur « polynomial » corrigé
- Le sens d'une boucle décide du problème résolu corrigé
- La distance d'édition en deux lignes corrigé
- Ordonnancement de tâches pondérées corrigé
- La sous-structure optimale en défaut, sur un exemple de cinq arêtes corrigé