La programmation dynamique

Paradigmes algorithmiques

L'algorithme glouton construit une solution de manière incrémentale, en optimisant un critère de manière locale.

Diviser pour régner divise un problème en sous-problèmes indépendants (qui ne se chevauchent pas), résout chaque sous-problème, et combine les solutions des sous-problèmes pour former une solution du problème initial.

La programmation dynamique, quant à elle, divise un problème en sous-problèmes qui sont non indépendants (qui se chevauchent), et cherche (et stocke) des solutions de sous-problèmes de plus en plus grands.

Bref historique

Ce paradigme, la programmation dynamique, a été développé par Richard Bellman en 1953 chez Rand Corporation. À l'époque, le terme « programmation » signifie planification et ordonnancement. Il s'agit d'une technique de conception d'algorithme très générale et performante.

Elle a d'emblée connu un grand succès, car de nombreuses fonctions économiques de l'industrie étaient de ce type, comme la conduite et l'optimisation de procédés chimiques, ou la gestion de stocks.

La programmation dynamique permet de résoudre de nombreux problèmes d'optimisation comme nous allons le voir sur les exercices de ce chapitre.