Programmation dynamique

La programmation dynamique (PD ; en anglais dynamic programming, DP) est une méthode de résolution de problèmes d'optimisation complexes, basée sur la décomposition du problème initial en une séquence de sous-problèmes plus simples. La méthode s'applique aux processus de décision séquentiels, où la solution optimale du problème global peut être construite à partir des solutions optimales de ses sous-problèmes.

Le terme a été introduit par le mathématicien américain Richard Bellman dans les années 1950. Dans ce contexte, le mot « programmation » est utilisé dans le sens de « planification » ou d'« élaboration d'un plan d'action optimal », et non dans celui de l'écriture de code informatique.

Principes et propriétés clés

L'applicabilité de la programmation dynamique à un problème est déterminée par la présence de deux propriétés fondamentales.

Principe d'optimalité de Bellman

Le concept central de la méthode est le principe d'optimalité de Bellman (en anglais Bellman's principle of optimality). Il stipule que, quels que soient l'état initial et la décision initiale, les décisions suivantes doivent constituer une stratégie optimale par rapport à l'état résultant de la première décision.

En d'autres termes, toute partie d'une trajectoire optimale est elle-même optimale. Cette propriété permet de décomposer le problème global en une séquence de sous-problèmes plus simples et de les résoudre de manière récursive.

Sous-problèmes chevauchants

Un problème possède la propriété de sous-problèmes chevauchants (en anglais overlapping subproblems) si, lors de sa résolution récursive, les mêmes sous-problèmes apparaissent de manière répétée. La programmation dynamique permet d'éviter les calculs redondants en sauvegardant les solutions des sous-problèmes déjà rencontrés (cette technique est appelée mémoïsation ou tabulation), ce qui augmente considérablement l'efficacité par rapport à une exploration récursive naïve.

Équation de Bellman

Du principe d'optimalité découle la relation de récurrence fondamentale de la méthode : l'équation de Bellman. Elle relie la « valeur » (gain ou coût optimal) de l'état actuel aux valeurs des états suivants. Sous sa forme générale pour un processus déterministe en plusieurs étapes avec une fonction objectif additive, elle s'écrit :

$V_{k-1}(x)=\underset{y\in U(x)}{max}\{{\phi }_k(x,y)+V_k(f_k(x,y))\}$

où :

• $k$ — le numéro de l'étape (de $m$ à 1) ;
• $x$ — l'état du système à l'étape $k-1$ ;
• $y$ — la décision (ou le contrôle) prise à l'étape $k$ ;
• ${\phi }_k(x,y)$ — le gain (ou le coût) à l'étape k ;
• $f_k(x,y)$ — la fonction définissant le nouvel état du système (fonction de transition) ;
• $V_k(s)$ — la valeur optimale de la fonction objectif pour le sous-problème commençant à l'étape $k$ dans l'état $s$.

L'équation est résolue séquentiellement, généralement « à rebours », en partant de la dernière étape pour remonter jusqu'à la première.

Exemples d'application

• Problème du plus court chemin dans un graphe : Ce problème possède la propriété de sous-structure optimale, car toute section d'un plus court chemin est elle-même un plus court chemin. Les algorithmes de Bellman-Ford et de Floyd-Warshall sont des exemples classiques de l'application de la programmation dynamique pour résoudre ce problème.
• Problème du sac à dos : Problème consistant à remplir de manière optimale un sac à dos de capacité limitée avec des objets de valeurs et de poids différents. La programmation dynamique permet de résoudre ce problème en considérant les objets séquentiellement et en calculant à chaque étape la valeur maximale pour toutes les capacités restantes possibles.
• Problème d'allocation de ressources : Allocation d'une ressource limitée (par exemple, des investissements) entre plusieurs projets afin de maximiser le gain total.

Limites

La principale limite de la méthode est le fléau de la dimensionnalité (en anglais curse of dimensionality) — un terme introduit par Bellman pour décrire la croissance exponentielle du nombre d'états et, par conséquent, de la complexité de calcul, à mesure que le nombre de variables décrivant l'état du système augmente. Cela limite l'application pratique de la programmation dynamique exacte aux problèmes de très grande dimension.

Concepts liés

• Recherche opérationnelle
• Théorie de la commande optimale
• Processus de décision markovien (généralisation stochastique)
• Équation de Hamilton-Jacobi-Bellman (analogue pour le temps continu)