Programmation dynamique
Cours · OCaml (option informatique), chapitre 13 · prépas MPSI et MP, option informatique · le début du chapitre, la suite sur Adloun
13.1 Introduction et motivation
Le chapitre 11 explorait tous les choix (exact mais exponentiel) ; le chapitre 12 n'en faisait qu'un, le meilleur local (rapide mais parfois faux). La programmation dynamique concilie les deux : elle obtient l'optimum sans tout réexplorer, en mémorisant les solutions des sous-problèmes pour ne les calculer qu'une fois. C'est elle qui résout proprement le rendu de monnaie sur un système quelconque, ou le sac à dos indivisible — là où le glouton se trompait.
Deux ingrédients la rendent applicable : une sous-structure optimale (la solution optimale se compose de solutions optimales de sous-problèmes) et un chevauchement des sous-problèmes (les mêmes reviennent sans cesse). On rangera alors les résultats dans une table (un tableau du chapitre 5) qu'on remplit dans le bon ordre — ou que l'on consulte par mémoïsation (la table de hachage du chapitre 8).
13.2 Le principe
Méthode : Concevoir une solution par programmation dynamique
- Définir le sous-problème : que représente
dp.(i)(oudp.(i).(j)) ? - Écrire la relation de récurrence : exprimer
dp.(i)en fonction de sous-problèmes plus petits. - Fixer les cas de base.
- Choisir l'ordre de remplissage : du plus petit sous-problème au plus grand (bas-haut), ou par récursion mémoïsée (haut-bas).
- (au besoin) Reconstruire la solution en retraçant les choix.
Exercices du chapitre
- Montées d'escalier corrigé
- Chemin de coût minimal dans une grille corrigé
- Plus longue sous-suite commune corrigé
- Sac à dos 0/1 corrigé
- Distance d'édition corrigé
- Reconstruire les pièces du rendu corrigé