La programmation dynamique
Cours · informatique (tronc commun des prépas scientifiques), chapitre 18 · prépas scientifiques, tronc commun · le début du chapitre, la suite sur Adloun
18.1 Introduction et motivation
Le chapitre 6 s'était achevé sur un avertissement : la fonction de Fibonacci récursive à deux appels explose en — non parce que le problème est dur, mais parce qu'elle recalcule sans fin les mêmes sous-problèmes. Le chapitre 7 avait laissé une blessure ouverte : le rendu de monnaie glouton, optimal sur les pièces usuelles, rend cinq pièces pour avec le système quand deux suffisent — le choix local sûr n'existait pas. Ce chapitre soigne les deux maux d'un seul remède, l'une des méthodes les plus puissantes de l'algorithmique : la programmation dynamique.
L'idée tient en une phrase : quand on ne sait pas quel choix est le bon, on les essaie tous — mais on ne calcule chaque sous-problème qu'une fois, en mémorisant sa réponse. Deux ingrédients la rendent possible : une sous-structure optimale (l'optimum se construit à partir d'optimums de sous-problèmes) et un chevauchement des sous-problèmes (les mêmes reviennent sans cesse — sinon mémoriser ne sert à rien). Quand les deux sont réunis, l'exponentielle des essais s'effondre en un produit raisonnable : nombre d'états coût par état. Au menu : la monnaie enfin rendue exactement, des partitions équilibrées, des sous-suites communes, la distance entre deux mots, et les distances dans un graphe par une triple boucle de trois lignes — avec, à chaque fois, la reconstruction de la solution, pas seulement sa valeur.
18.2 Le mal et le remède : recalculer ou mémoriser
18.2.1 Le chevauchement des sous-problèmes
L'arbre des appels de fib(5) appelle fib(3) deux fois, fib(2) trois fois, fib(1) cinq fois — les mêmes calculs, refaits. Pour fib(30) : environ millions d'appels pour… valeurs distinctes. Le problème n'a que sous-problèmes ( à ) ; c'est leur chevauchement — chacun requis par une myriade de chemins de l'arbre — qui fabrique l'exponentielle.
