Programmation dynamique
Préambule
De quoi parle-t-on ?
La programmation dynamique est à la fois une méthode d’optimisation mathématique et une méthode de développement informatique. Dans ces deux contextes, il s’agit toujours de résoudre un problème en se basant sur plusieurs sous-problèmes plus simples à résoudre.
L’utilisation du mot programmation a en fait ici le même sens que dans la programmation linéaire ou la programmation mathématique : il s’agit donc là d’un synonyme d’optimisation mathématique. À l’origine, ce terme faisait référence à l’utilisation d’une méthode pour déterminer une planification optimale ; ainsi, dans le contexte dans lequel s’inscrit cette présentation, nous ne ferons que quelques allusions avec le développement informatique.
Un peu d'histoire
- 1940 – Richard Bellman utilise pour la première fois le terme dynamic programming pour décrire le processus de résolution de problèmes pour lesquels on a besoin de prendre un ensemble de solutions optimales successivement.
- 1953 – Il en affine la définition pour arriver à celle d’aujourd’hui : il s’agit d’emboîter des sous-problèmes aux solutions plus simples pour aboutir une conclusion plus large.
- Plus tard, l’IEEE reconnaîtra ce domaine comme faisant partie des sujets de l’analyse systémique et de l’ingénierie. On se souvient alors de la contribution de Bellman sous le nom de l’équation de Bellman.
L'équation de Bellman
Toute solution optimale s'appuie elle-même sur des sous-problèmes résolus localement de façon optimale.
Souvent, pour résoudre certains problèmes, on a besoin de résoudre certaines sous-parties de celui-ci et de combiner les solutions obtenues afin d’atteindre l’objectif initial.
Concrètement, cela signifie que l'on va pouvoir déduire la solution optimale d'un problème en combinant des solutions optimales d'une série de sous-problèmes. Les solutions des problèmes sont étudiées de bas en haut, c'est-à-dire que l'on calcule les solutions des sous-problèmes les plus petits pour ensuite déduire petit à petit les solutions de l'ensemble.