Skip to content
Retour aux résultats

Programmation dynamique

Introduite par
Richard Bellman
Année
1957
Type
Exact combinatorial optimization via recursive decomposition
Famille
Mathematical programming

Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais

Taille de police

À quoi sert-elle ?

La programmation dynamique (PD) est une technique d'optimisation exacte introduite par Richard Bellman en 1957 pour résoudre les problèmes de décision multi-étapes.

Elle décompose un problème complexe en sous-problèmes simples et interdépendants, résout chaque sous-problème une fois et stocke les résultats pour éviter les calculs redondants. Fondée sur le principe d'optimalité, la PD garantit des solutions globalement optimales lorsque le problème présente des sous-problèmes interdépendants et une sous-structure optimale.

L’intuition derrière la méthode

Imaginez planifier le trajet le plus court à travers une ville en trouvant d'abord les chemins les plus courts entre chaque paire d'intersections voisines, puis en combinant ces petites solutions vers le haut. Au lieu de réexplorer toutes les routes complètes possibles à partir de zéro, vous réutilisez des réponses locales pré-calculées. La programmation dynamique fonctionne de la même manière : elle met en cache les solutions de petits sous-problèmes afin que la construction de la réponse complète ne nécessite que des consultations de table plutôt que des calculs intensifs répétés.

Histoire

Richard Bellman a inventé le terme « programmation dynamique » en 1957 alors qu'il travaillait à la RAND Corporation, choisissant délibérément le mot « programmation » pour désigner la planification plutôt que le codage informatique. Le principe d'optimalité qu'il a énoncé est devenu le fondement théorique de la théorie du contrôle, de la recherche opérationnelle et, plus tard, de l'apprentissage par renforcement. Les algorithmes classiques de PD — l'algorithme de Dijkstra pour le plus court chemin, l'algorithme de Viterbi et l'aligneur de séquences de Needleman-Wunsch — dérivent tous directement du cadre de Bellman.

Quand l’utiliser

La programmation dynamique est appropriée lorsqu'un problème présente des sous-problèmes interdépendants et une sous-structure optimale — des propriétés courantes dans la prise de décision séquentielle, l'allocation de ressources, la planification et l'alignement de chaînes de caractères. Elle exige que l'espace d'états soit entièrement énumérable et de taille gérable ; la méthode souffre de la malédiction de la dimensionnalité lorsque les variables d'état sont nombreuses ou continues. Pour les problèmes avec des espaces d'états intraitable, la PD approximative ou l'apprentissage par renforcement sont des alternatives préférables.

Limites et points d’attention

  • Souffre de la malédiction de la dimensionnalité : les exigences en mémoire et en temps croissent exponentiellement avec le nombre de variables d'état.
  • Nécessite une connaissance préalable complète de la structure de transition et de la fonction de récompense ; inapplicable aux environnements inconnus sans approximation.
  • L'espace d'états doit être discret ou discrétisable ; les problèmes continus de haute dimension exigent des schémas d'approximation qui sacrifient l'exactitude.
  • La formulation de la représentation d'état correcte et de la relation de récurrence nécessite une compréhension approfondie spécifique au problème.

Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.

Points forts

  • Garantit des solutions globalement optimales exactes pour les problèmes satisfaisant le principe d'optimalité.
  • Élimine les calculs redondants via la mémoïsation, atteignant un temps polynomial par rapport au nombre d'états.
  • Produit une politique optimale explicite, et pas seulement une valeur optimale, permettant un support décisionnel direct.
  • Largement applicable dans divers domaines, y compris la théorie du contrôle, la bioinformatique, l'économie et la recherche opérationnelle.

Applications

  • Problèmes de plus court chemin et de routage dans les réseaux (variantes de Bellman-Ford, Dijkstra).
  • Alignement de séquences en biologie computationnelle (algorithmes de Needleman-Wunsch, Smith-Waterman).
  • Allocation optimale de ressources et problèmes combinatoires de type sac à dos en recherche opérationnelle.
  • Reconnaissance vocale et manuscrite via l'algorithme de Viterbi sur les modèles de Markov cachés.
  • Contrôle optimal et optimisation de portefeuille multi-périodes en économie et en ingénierie.

Comment ça marche

Comment ça marche

1

Le problème d'optimisation global est exprimé sous forme de relation de récurrence. Pour chaque état s et chaque étape de décision n, la fonction de valeur V_n(s) est égale à la meilleure récompense immédiate plus la valeur actualisée de l'état suivant résultant. Cette équation de Bellman formalise le principe d'optimalité : tout sous-chemin d'un chemin optimal doit lui-même être optimal.

Formule
V_n(s) = \max_{a \in A(s)} \left[ r(s,a) + \gamma V_{n-1}(T(s,a)) \right]
2

La récurrence est résolue itérativement ou récursivement. En itération de valeur, V^*(s) est mise à jour de manière répétée pour tous les états jusqu'à convergence, en utilisant l'estimation actuelle des valeurs des états voisins. Chaque mise à jour remplace l'ancienne valeur par la meilleure combinaison de récompense immédiate et de valeur future réalisable, propageant ainsi les informations d'optimalité à travers l'espace d'états.

Formule
V^*(s) = \max_{a \in A(s)} \left[ r(s,a) + \gamma V^*(s') \right], \quad s' = T(s,a)
3

Les valeurs calculées sont stockées dans une table indexée par l'état. Les états terminaux reçoivent une valeur de base de zéro (ou une récompense connue), et toutes les autres entrées sont remplies au fur et à mesure que les sous-problèmes sont résolus. La mémoïsation garantit que chaque état est évalué au plus une fois, réduisant la recherche récursive exponentielle à un temps polynomial par rapport au nombre d'états et d'étapes.

Formule
\text{Table}[s] = \begin{cases} 0 & \text{if } s \in S_{\text{terminal}} \\ V^*(s) & \text{otherwise} \end{cases}
4

Une fois la table de valeurs complétée, la politique optimale pi^*(s) est récupérée par un simple passage glouton : pour chaque état, on sélectionne l'action qui maximise la récompense immédiate plus la valeur stockée de l'état successeur. Cette extraction en une seule passe est peu coûteuse en calcul et produit une règle de décision déterministe et globalement optimale.

Formule
\pi^*(s) = \arg\max_{a \in A(s)} \left[ r(s,a) + \gamma \, \text{Table}[T(s,a)] \right]

Pièges courants

  • Définir une représentation d'état insuffisamment expressive conduit à des récurrences incorrectes et à des solutions sous-optimales.
  • Confondre la mémoïsation descendante (top-down) avec la tabulation ascendante (bottom-up) peut produire des erreurs de dépassement de pile (stack overflow) ou un ordre incorrect d'évaluation des sous-problèmes.
  • Appliquer la PD à des problèmes qui manquent de sous-structure optimale (par exemple, le chemin le plus long dans un graphe général) donne des résultats incorrects sans avertissement.
  • Ignorer la précision numérique dans les calculs de récompenses cumulées peut causer des erreurs subtiles d'optimalité dans les implémentations en virgule flottante.

Questions fréquentes

Quelle est la différence entre la programmation dynamique et la méthode diviser pour régner ?

Les deux décomposent les problèmes en sous-problèmes, mais la méthode diviser pour régner suppose des sous-problèmes indépendants résolus une seule fois naturellement. La programmation dynamique cible les sous-problèmes interdépendants — le même sous-problème apparaît dans plusieurs branches — et mémoïse les résultats pour éviter un travail redondant. Sans sous-problèmes interdépendants, la PD n'offre aucun avantage computationnel par rapport à la récursion directe.

Quand dois-je utiliser la mémoïsation descendante (top-down) par rapport à la tabulation ascendante (bottom-up) ?

La mémoïsation descendante est plus facile à implémenter directement à partir de la récurrence et ne calcule que les sous-problèmes nécessaires, ce qui est bénéfique pour les espaces d'états épars. La tabulation ascendante évite la surcharge de la récursion et les limites de la pile, convient aux espaces d'états denses et est souvent plus rapide en pratique. Choisissez la méthode descendante lorsque l'ensemble des sous-problèmes nécessaires est difficile à prévoir, et la méthode ascendante lorsque tous les sous-problèmes seront nécessaires.

Comment la programmation dynamique est-elle liée à l'apprentissage par renforcement ?

La PD classique nécessite un modèle de processus décisionnel markovien entièrement connu (probabilités de transition et récompenses). L'apprentissage par renforcement étend les idées de la PD à des contextes où le modèle est inconnu, en utilisant plutôt l'expérience échantillonnée. Des algorithmes comme Q-learning et les méthodes de gradient de politique sont des procédures de PD approximatives qui apprennent les fonctions de valeur à partir de l'interaction plutôt que d'un modèle explicite.

Méthodes associées

Sources

  1. Bellman, R. (1957). Dynamic Programming. Princeton University Press.

    ISBN : 978-0-691-07951-6
    Copié.