Programmation dynamique

La programmation dynamique est un paradigme de conception d'algorithmes qui résout des problèmes présentant une sous-structure optimale et des sous-problèmes superposés en résolvant chaque sous-problème une seule fois et en stockant son résultat pour réutilisation, transformant ainsi la recalcul exponentielle en un calcul en temps polynomial.

Definition

La programmation dynamique est une méthode qui résout un problème d'optimisation ou de dénombrement en définissant sa valeur de manière récursive en termes de sous-problèmes superposés et en calculant chaque sous-problème distinct exactement une fois, en mettant en cache le résultat afin qu'il puisse être réutilisé plutôt que recalculé.

Scope

Ce sujet aborde les deux caractéristiques fondamentales qui rendent la programmation dynamique applicable — la sous-structure optimale et les sous-problèmes superposés — ainsi que les deux styles d'implémentation : la mémoïsation descendante (top-down) et la tabulation ascendante (bottom-up). Il inclut des problèmes canoniques tels que la plus longue sous-séquence commune, la distance d'édition, le problème du sac à dos, la multiplication de chaînes de matrices et les programmes dynamiques de chemin le plus court, ainsi que la conception de l'espace d'états et l'analyse des compromis temps-espace. Il exclut les méthodes de chemin le plus court spécifiques aux graphes, traitées dans les algorithmes de graphes, bien qu'elles partagent le même principe sous-jacent.

Core questions

• Le problème présente-t-il une sous-structure optimale permettant de construire une solution optimale à partir de sous-solutions optimales ?
• Comment l'ensemble des sous-problèmes (l'espace d'états) est-il défini de manière à ce que chacun ne se reproduise qu'un nombre polynomial de fois ?
• La solution doit-elle être implémentée de manière descendante avec mémoïsation ou ascendante avec tabulation ?
• Comment la table peut-elle être reconstruite pour récupérer la solution optimale réelle, et non seulement sa valeur ?
• Comment l'espace peut-il être réduit lorsque seule une partie de la table est nécessaire à chaque étape ?

Key concepts

• sous-structure optimale
• sous-problèmes superposés
• principe d'optimalité
• mémoïsation
• tabulation
• espace d'états et récurrence
• plus longue sous-séquence commune
• distance d'édition
• problème du sac à dos

Key theories

Principle of optimality

Le principe d'optimalité de Bellman stipule qu'une politique optimale a la propriété que, quels que soient l'état initial et la décision, les décisions restantes doivent constituer une politique optimale pour l'état résultant — la base formelle des récurrences de la programmation dynamique.

Memoization versus tabulation

Un programme dynamique peut être réalisé de manière descendante en ajoutant un cache à une formulation récursive (mémoïsation) ou de manière ascendante en remplissant une table selon l'ordre de dépendance (tabulation) ; les deux calculent chaque sous-problème une seule fois mais diffèrent par l'ordre d'évaluation et le comportement spatial.

Clinical relevance

La programmation dynamique est omniprésente en pratique : l'alignement de séquences (Needleman-Wunsch, Smith-Waterman) en biologie computationnelle, la distance d'édition dans la correction orthographique et les différences de contrôle de version, l'algorithme de Viterbi dans la reconnaissance vocale et les communications, et les programmes dynamiques dans la recherche opérationnelle, la finance et l'apprentissage par renforcement.

History

Richard Bellman a développé la programmation dynamique dans les années 1950 alors qu'il était à la RAND Corporation, choisissant ce nom en partie pour être acceptable aux yeux des sponsors de recherche. Le principe d'optimalité et l'équation de Bellman sont devenus fondamentaux dans la recherche opérationnelle, la théorie du contrôle et l'informatique, et la technique a ensuite été codifiée comme un paradigme algorithmique central dans les manuels d'algorithmes.

Key figures

• Richard Bellman
• Thomas H. Cormen
• Jon Kleinberg
• Éva Tardos

Seminal works

• bellman1957
• cormen2009

Frequently asked questions

Quelle est la différence entre la division pour régner et la programmation dynamique ?

Les deux décomposent un problème en sous-problèmes, mais les sous-problèmes de la division pour régner sont indépendants et résolus une seule fois, tandis que les sous-problèmes de la programmation dynamique se chevauchent et seraient recalculés de nombreuses fois par une récursion naïve. La programmation dynamique met en cache les solutions des sous-problèmes pour éviter cette recalcul.

Quand la programmation dynamique ne s'applique-t-elle pas ?

Elle nécessite une sous-structure optimale et un ensemble de sous-problèmes distincts de taille polynomiale. Si le problème manque de sous-structure optimale, ou si l'espace d'états naturel est exponentiel et ne peut être compressé, la programmation dynamique est soit incorrecte, soit n'est plus efficace.