programmation dynamique

ASTRONOMIE
INFORMATIQUE
MATHEMATIQUES APPLIQUEES A L’ECONOMIE

La programmation dynamique (en anglais dynamic programming ou encore dynamic optimization) est une méthode algorithmique utilisée pour résoudre des problèmes d’optimisation.

C’est une technique d’optimisation d’un algorithme qui vise à résoudre un problème en se ramenant à la résolution de plusieurs problèmes similaires mais plus simples pouvant être résolus l’un à la suite de l’autre. Dans le cas d’algorithmes où on devrait calculer plusieurs fois des sous-problèmes, la méthode consiste à en stocker les résultats en mémoire (par exemple le calcul du n-ième terme de la suite de Fibonacci ).
Cette technique de programmation a été inventée par Richard Bellman . Elle s’appuie sur le principe d’optimalité de Bellman qui énonce que la solution optimale d’un problème peut être calculée à partir de solutions optimales de sous-problèmes.
On l’applique dans des problèmes de recherche opérationnelle : problème du sac à dos , problème du rendu de monnaie, algorithmes de plus court chemin, etc.