Voir la source de Programmation dynamique

{{confusion|texte=''Cet article traite d'un paradigme algorithmique. Pour une classe particulière de langages de programmation, voir [[langage de programmation dynamique]]''}}

En [[informatique]], la '''programmation dynamique''' est une méthode [[Algorithme|algorithmique]] pour résoudre des [[Optimisation (mathématiques)|problèmes d'optimisation]]. Le concept a été introduit au début des années 1950 par [[Richard Bellman]]<ref name="Cormen359">{{harvsp|id=Cormen2fr|texte=Cormen et al., Introduction à l'algorithmique|p=359}}.</ref>. À l'époque, le terme « programmation » signifie planification et ordonnancement<ref name="Cormen359"/>. La programmation dynamique consiste à résoudre un problème en le décomposant en sous-problèmes, puis à résoudre les sous-problèmes, des plus petits aux plus grands en stockant les résultats intermédiaires. Elle a d'emblée connu un grand succès, car de nombreuses fonctions économiques de l'industrie étaient de ce type, comme la conduite et l'optimisation de procédés chimiques, ou la gestion de stocks<ref name="Cormen359"/>.

== Principe ==
[[Fichier:Fibonacci dynamic programming.svg|vignette|149x149px|Le graphe de dépendance des sous-problèmes pour le calcul de F<sub>5</sub>, le 5ème terme de la suite de Fibonacci.]]
Illustrons la programmation dynamique sur le calcul du n<sup>ème</sup> terme de la [[suite de Fibonacci]], parfois utilisé comme exemple introductif dans un cours sur la programmation dynamique<ref>{{Lien web|langue=Anglais|titre=Cours du MIT sur la programmation dynamique|url=https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-19-dynamic-programming-i-fibonacci-shortest-paths/|date=}}.</ref>. La suite de Fibonacci est définie par F<sub>0</sub> = 0, F<sub>1</sub> = 1 et F<sub>n</sub> = F<sub>n-1</sub> + F<sub>n-2</sub>. La programmation dynamique s'appuie sur le ''principe d'optimalité de Bellman'' : une solution optimale d'un problème s'obtient en combinant des solutions optimales à des sous-problèmes. Sur l'exemple de la suite de Fibonacci, la solution F<sub>n</sub> s'obtient en additionnant F<sub>n-1</sub> et F<sub>n-2</sub>.

La méthode de programmation dynamique, comme la méthode [[Diviser pour régner (informatique)|diviser pour régner]], résout des problèmes en combinant des solutions de sous-problèmes. Les algorithmes diviser-pour-régner partitionnent le problème en sous-problèmes indépendants qu’ils résolvent [[récursivité|récursivement]], puis combinent leurs solutions pour résoudre le problème initial. La méthode diviser-pour-régner est inefficace si on doit résoudre plusieurs fois le même sous-problème. Par exemple, l'algorithme suivant est inefficace :
 fonction fibonacci(n)
    si n = 0 ou n = 1
          retourner n
    sinon
          retourner fibonacci(n-1) + fibonacci(n-2)

Le [[Dépendance fonctionnelle|graphe de dépendance]] montré sur la droite n'est pas un [[Arbre_(théorie_des_graphes)|arbre]] : cela illustre que les sous-problèmes se chevauchent. Par exemple, pour calculer F<sub>5</sub>, nous avons besoin de F<sub>3</sub> et F<sub>4</sub>. Mais pour calculer F<sub>4</sub>, nous avons besoin de F<sub>2</sub> et F<sub>3</sub>. Ainsi, F<sub>3</sub> est utile à la fois pour le calcul de F<sub>4</sub> et pour le calcul de F<sub>5</sub>. La programmation dynamique consiste alors à stocker les valeurs des sous-problèmes pour éviter les recalculs<ref name="Cormen">{{harvsp|id=Cormen2fr|texte=Cormen et al., Introduction à l'algorithmique|p=315-316}}.</ref>. Il existe alors deux méthodes pour calculer effectivement une solution : la méthode ascendante et la méthode descendante. Dans la méthode ascendante, on commence par calculer des solutions pour les sous-problèmes les plus petits, puis, de proche en proche, on calcule les solutions des problèmes en utilisant le principe d'optimalité et on mémorise les résultats dans un tableau F[.]. Par exemple :
 fonction fibonacci(n)
    F[0] = 0
    F[1] = 1
    pour tout i de 2 à n
 <nowiki>        F[i] := F[i-1] + F[i-2]  </nowiki>
    retourner F[n]

Dans la méthode descendante, on écrit un [[algorithme récursif]] mais on utilise la [[mémoïsation]] pour ne pas résoudre plusieurs fois le même problème, c'est-à-dire que l'on stocke dans un tableau F[.] les résultats des appels récursifs :
 fonction fibonacci(n)
    si F[n] n'est pas défini
       si n = 0 ou n = 1
          F[n] := n
       sinon
          F[n] := fibonacci(n-1) + fibonacci(n-2)
    retourner F[n]

La programmation dynamique est utilisée pour résoudre des problèmes d'optimisation. Les sections suivantes en donnent quelques exemples. La conception d’un algorithme de programmation dynamique est typiquement découpée en quatre étapes<ref name="Cormen" />.
# Caractériser la structure d’une solution optimale.
# Définir (souvent de manière récursive) la valeur d’une solution optimale.
# Calculer la valeur d’une solution optimale.
# Construire une solution optimale à partir des informations calculées.
La dernière étape est utile pour calculer une solution optimale, et pas seulement la valeur optimale. Un problème d'optimisation peut avoir de nombreuses solutions. Chaque solution a une valeur, et on souhaite trouver une solution ayant la valeur optimale. Une telle solution optimale au problème n'est pas forcément unique, c'est sa valeur qui l'est.

== Exemples ==
=== Pyramide de nombres ===
Dans une pyramide de nombres, on cherche, en partant du sommet de la pyramide, et en se dirigeant vers le bas à chaque étape, à maximiser le total des nombres traversés<ref>{{harvsp|id=opc|texte=Openclassrooms |p=}}.</ref>. Dans l'exemple ci-dessous, le maximum est obtenu pour le chemin en gras (3+7+4+9 = 23).
      '''3'''
     '''7''' 4
    2 '''4''' 6
   9 5 '''9''' 3

Un algorithme naïf, sur l'exemple, consiste à examiner les 8 chemins possibles, et choisir celui qui a le plus grand total. En général, quand la pyramide a ''n'' niveaux, il y a <math>2^{n-1}</math> chemins et <math>2^{n}-2</math> calculs à effectuer. Donc l'algorithme naïf est en temps exponentiel en n.

Le paradigme de la programmation dynamique permet d'obtenir un algorithme efficace en définissant des sous-problèmes, en écrivant une [[Suite définie par récurrence|relation de récurrence]], puis en donnant un algorithme (avec méthode ascendante ou descendante).

Pour toute position <math>x</math> dans la pyramide, notons <math>v(x)</math> le nombre écrit à cette position et <math>c(x)</math> la somme des nombres traversés dans un chemin maximal issu de <math>x</math>. Les sous-problèmes consistent à calculer les valeurs de <math>c(x)</math> pour tout <math>x</math>. Le problème initial consiste à calculer <math>c(x)</math> lorsque <math>x</math> est le sommet de la pyramide.

Donnons maintenant une ''définition récursive'' de <math>c(x)</math> : 
: <math>c(x) = v(x)</math> pour toute position <math>x</math> située au rez-de chaussée de la pyramide
: <math>c(x) = v(x) +\max(c(g(x)),c(d(x)))</math> pour toute autre position <math>x</math>, où <math>g(x)</math> et <math>d(x)</math> sont les positions inférieures gauche et droite sous la position <math>x</math>.

Si on cherche à calculer directement par la définition récursive, on évalue plusieurs fois la même valeur : dans l'exemple ci-dessus, la valeur 4 de la troisième ligne est calculée deux fois en venant de la ligne supérieure (une fois depuis le 7, une fois depuis le 4). Le paradigme de la programmation dynamique consiste à calculer les valeurs <math>c(x)</math>, soit à l'aide d'un algorithme itératif ascendant en stockant les valeurs déjà calculées dans un tableau, soit à l'aide d'un algorithme récursif descendant avec [[mémoïsation]]. L'important est de conserver dans un tableau les valeurs intermédiaires. La séquence des calculs est indiquée en gras :

     3                                        '''23'''
    7 4                         '''20  19'''      20  19
   2 4 6        '''11 13 15'''      11  13  15
  '''9 5 9 3'''      9  5  9  3

Le nombre de calculs est seulement <math>n(n-1)/2</math>.

=== Calcul d'un produit de matrices ===
{{Article détaillé|Algorithme de multiplication de matrices enchaînées}}

On se donne des [[Matrice (mathématiques)|matrices]] <math>M_1, M_2,\ldots, M_h</math>, et on veut calculer la matrice produit <math>M_1 M_2 \cdots M_h</math><ref>{{harvsp|id=Cori|Cori|p=}}.</ref>{{,}}<ref name="Cormen"/>. Les matrices ne sont pas forcément carrées, et l'ordre dans lequel on effectue les multiplications peut influencer le coût. Ainsi, le produit des matrices <math>A_{4\times5}.B_{5\times 8}.C_{8\times 5}</math> exige un nombre de multiplications différent suivant que l'on débute par <math>(A_{4\times5}.B_{5\times8}).C_{8\times 5} = M_{4\times8}.C_{8\times 5}</math>, avec {{nobr|320 multiplications}}, ou par <math>A_{4\times5}.(B_{5\times8}.C_{8\times 5}) = A_{4\times5}.N_{5\times 5}</math>, avec {{nobr|300 multiplications}}. La seconde façon est optimale par rapport au nombre de multiplications.

Si chaque matrice <math>M_i</math> a <math>m_i</math> lignes et <math>m_{i+1}</math> colonnes, le produit <math> M_{i-1}M_i</math> demande <math>O(m_{i-1}m_im_{i+1})</math> opérations. On note <math>c_{i,j}</math> le nombre minimum d'opérations pour calculer le produit <math>M_i\cdots M_j</math>. On a alors
: <math>c_{i,i}=0, c_{i-1,i}=m_{i-1}m_im_{i+1}</math>.
Pour obtenir la meilleure valeur pour le produit <math>M_i\cdots M_j</math>, on le découpe en <math>M_i\cdots M_k</math> et <math>M_{k+1}\cdots M_j</math> et on choisit le meilleur <math>k</math>. Ceci conduit à la formule :
: <math>c_{i,j}=  \min_{i\le k<j}[c_{i,k} +  c_{k+1,j}+ m_{i}m_{k+1}m_{j+1}]</math>.
Le calcul des <math>c_{i,j}</math> se fait dans un tableau, diagonale par diagonale, en temps quadratique en le nombre de matrices.

Dans cet exemple aussi, il est important de garder le résultat des calculs dans un tableau pour ne pas les recalculer.

== Histoire ==
Le terme ''programmation dynamique'' était utilisé dans les [[années 1940]] par [[Richard Bellman]] pour décrire le processus de résolution de problèmes où on trouve les meilleures décisions les unes après les autres. En 1953, il en donne la définition moderne, où les décisions à prendre sont ordonnées par sous-problèmes<ref>{{pdf}} Stuart Dreyfus, [https://web.archive.org/web/20050110161049/http://www.wu-wien.ac.at/usr/h99c/h9951826/bellman_dynprog.pdf « Richard Bellman on the birth of Dynamical Programming »].</ref>  et le domaine a alors été reconnu par [[IEEE]] comme un sujet d'analyse de systèmes et d’ingénierie. La contribution de Bellman est connu sous le nom d'équation de Bellman, qui présente un problème d'optimisation sous forme récursive.

Bellman explique l'idée du terme ''programmation dynamique'' dans son autobiographie, ''{{langue|en|Eye of the Hurricane: An Autobiography}}'' <ref>Richard Bellman, ''{{langue|en|Eye of the Hurricane: An Autobiography}}'' , 1984, {{p.|159}}.</ref>. Il dit :
{{Citation bloc|I spent the Fall quarter (of 1950) at RAND. My first task was to find a name for multistage decision processes. An interesting question is, Where did the name, dynamic programming, come from? The 1950s were not good years for mathematical research. We had a very interesting gentleman in Washington named [[Charles Erwin Wilson|Wilson]]. He was Secretary of Defense, and he actually had a pathological fear and hatred of the word research. I’m not using the term lightly; I’m using it precisely. His face would suffuse, he would turn red, and he would get violent if people used the term research in his presence. You can imagine how he felt, then, about the term mathematical. The RAND Corporation was employed by the Air Force, and the Air Force had Wilson as its boss, essentially. Hence, I felt I had to do something to shield Wilson and the Air Force from the fact that I was really doing mathematics inside the RAND Corporation. What title, what name, could I choose? In the first place I was interested in planning, in decision making, in thinking. But planning, is not a good word for various reasons. I decided therefore to use the word “programming”. I wanted to get across the idea that this was dynamic, this was multistage, this was time-varying. I thought, let's kill two birds with one stone. Let's take a word that has an absolutely precise meaning, namely dynamic, in the classical physical sense. It also has a very interesting property as an adjective, and that it's impossible to use the word dynamic in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. It's impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activities.}}
L'adjectif ''dynamique'' était donc choisi par Bellman pour insister sur l'aspect temporel des problèmes, et parce que le terme impressionnait<ref name="Eddy">Eddy, S. R., What is dynamic programming?, Nature Biotechnology, 22, 909–910, 2004.</ref>. Le mot ''programmation'' référait à l'utilisation d'une méthode pour trouver un ''programme'' optimal dans un sens militaire : emploi du temps ou de la logistique. D'ailleurs, l'usage est le même que dans les termes [[Optimisation linéaire|programmation linéaire]] et programmation mathématique, synonyme pour optimisation mathématique<ref>Nocedal, J.; Wright, S. J.: Numerical Optimization, page 9, Springer, 2006.</ref>.

Mais cette explication est controversée. Selon le [[Intelligence artificielle : une approche moderne|livre ''{{langue|en|Artificial Intelligence: A Modern Approach}}'']] de [[Stuart Russell|Russell]] et [[Peter Norvig|Norvig]]<ref>Russell, S. and Norvig, P., Artificial Intelligence: A Modern Approach, 3rd edition, Prentice Hall, 2009.</ref>, l'explication ci-dessus n'est pas tout à fait vraie car le premier article de 1952 où Bellman utilise le terme ''programmation dynamique'' a paru avant que [[Charles Erwin Wilson|Wilson]] devienne secrétaire de la défense en 1953. Aussi, dans un discours de [[Harold J. Kushner]]<ref>[http://a2c2.org/awards/richard-e-bellman-control-heritage-award/2004-00-00t000000/harold-j-kushner Harold J. Kushner].</ref>, il dit de Bellman : {{citation|On the other hand, when I asked him the same question, he replied that he was trying to upstage Dantzig's linear programming by adding dynamic. Perhaps both motivations were true.}}

== Applications algorithmiques ==
* Le [[problème du plus court chemin]] ([[algorithme de Bellman-Ford]] et [[algorithme de Floyd-Warshall]]) ;
* [[Problème d'affectation]] des ressources. Il s'agit (par exemple) de distribuer ''m'' skis à ''n'' skieurs (''m>n'') en minimisant les écarts de taille entre les skis et les skieurs. La propriété d'optimalité des sous-structures (si une distribution est optimale, alors toute sous-partie des skis et des skieurs est optimale) le rend traitable par programmation dynamique{{Référence nécessaire|date=29 mai 2023}} ;
* Le [[problème du sac à dos]] (''knapsack'' en anglais) est un problème classique de [[recherche opérationnelle]] qui est [[complexité en temps|NP-difficile]], mais qui est résolu de manière [[algorithme pseudo-polynomial|pseudo-polynomiale]] à l'aide d'un algorithme de programmation dynamique ;
* Le [[problème du rendu de monnaie]] dans le cas général ;
* La recherche de la [[plus longue sous-suite strictement croissante]] dans une suite de nombres ;
* Des problèmes d'[[algorithmique du texte]] comme le calcul de la plus longue sous-suite commune entre deux chaînes{{Référence nécessaire|date=29 mai 2023}}, le calcul de la [[distance de Levenshtein]] ou encore l'[[alignement de séquences]] (avec l'[[algorithme de Smith-Waterman]] par exemple) ;
* L'[[Algorithme de Cocke-Younger-Kasami|algorithme CYK]] est un algorithme d'[[analyse syntaxique]] ;
* La méthode la plus utilisée pour résoudre le problème de [[détection de ruptures]] est la [[Détection de ruptures#Programmation dynamique|programmation dynamique]].
* L'[[algorithme de Viterbi]], utilisé en [[Reconnaissance automatique de la parole|reconnaissance de la parole]] et dans différents problèmes de reconnaissance utilisant des [[Modèle de Markov caché|modèles de Markov cachés]].

== Connexions ==
La programmation dynamique a des liens avec le [[calcul des variations]] et la [[commande optimale]].
Un théorème général énonce que tout algorithme de programmation dynamique peut se ramener à la recherche du plus court chemin dans un graphe<ref>A. Martelli, « ''{{Lang|en|An application of heuristic search methods to edge and contour detection}}'' », ''Comm. ACM'', 19(2):73--83, février 1976.</ref>. Or, les techniques de recherche heuristique basées sur l'[[algorithme A*]] permettent d'exploiter les propriétés spécifiques d'un problème pour gagner en temps de calcul. Autrement dit, il est souvent plus avantageux d'exploiter un algorithme A* que d'utiliser la programmation dynamique.

== Programmation dynamique et apprentissage par renforcement ==
{{Section vide ou incomplète}}

== Notes et références ==
{{Références}}

== Bibliographie ==
;Ouvrages historiques
* {{Ouvrage
|auteur1=[[Richard Bellman]]
|titre=Dynamic Programming
|lieu=Princeton
|éditeur=[[Princeton University Press]]
|année=1957
}}. {{Commentaire biblio SRL|Réimpression 2003, Dover Publication, Mineola, New-York, {{isbn|0-486-42809-5}}}}.
* {{article
|auteur=Stuart Dreyfus
|titre=Richard Bellman on the birth of Dynamic Programming
|journal=Operations Research|volume=50|numéro=1|mois=janvier-février|année=2002|pages=48-51
|issn=1526-5463|url=http://www.eng.tau.ac.il/~ami/cd/or50/1526-5463-2002-50-01-0048.pdf
}}
;Cours et notes de cours
* {{Cormen2fr|page=323–369}} {{Commentaire biblio SRL|Chapitre 15, « Programmation dynamique », pages 315-360}}.
* {{Lien web|url= http://openclassrooms.com/courses/introduction-a-la-programmation-dynamique|titre=Introduction à la programmation dynamique|site=openclassrooms.com |éditeur=OpenClassrooms|consulté le=21 février 2015|id=opc}}
* {{Lien web|url= http://dept-info.labri.u-bordeaux.fr/~cori/Enseirb/progDynamique.pdf
|titre=Principe de la programmation dynamique|auteur=Robert Cori|id=Cori
|éditeur=Enseirb|consulté le=21 février 2015
}}.
* {{Lien web|url= https://www.ceremade.dauphine.fr/~carlier/progdyn.pdf
|titre=Programmation dynamique - Notes de cours|auteur=Guillaume Carlier|année=2007
|éditeur=ENSAE|consulté le=21 février 2015
}}.

== Annexes ==

=== Articles connexes ===
{{colonnes|nombre=3|
* [[Commande optimale]]
* [[Automatique]]
* [[Diviser pour régner (informatique)|Diviser pour régner]]
* [[Mémoïsation]]
* [[Décomposition arborescente]]
* [[Algorithme glouton]]
* [[Algorithme de Viterbi]]
* [[Distance de Levenshtein]]
* [[Algorithme de Smith-Waterman]]
* [[Algorithme de Bellman-Ford]]
* [[Algorithme de Cocke-Younger-Kasami]]
* [[Problème du sac à dos]]
* [[Problème du rendu de monnaie]] 
* [[Problème du voyageur de commerce]]
* [[Problème de Josèphe]]
* [[Taux d'erreur de mots]]
* [[Plus longue sous-séquence commune]]
* [[FASTA (programme informatique)]]
* [[Distance d'édition sur les arbres]]
* [[Plus petit ancêtre commun]]
* [[Graphe hamiltonien]]
}}
{{Palette|Informatique théorique|Optimisation}}
{{Portail|informatique théorique|mathématiques}}

[[Catégorie:Algorithme d'optimisation]]
[[Catégorie:Recherche opérationnelle]]
[[Catégorie:Méthode algorithmique]]