Programmation dynamique

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
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 algorithmique pour résoudre des problèmes d'optimisation. Le concept a été introduit au début des années 1950 par Richard Bellman[1]. À l'époque, le terme « programmation » signifie planification et ordonnancement[1]. 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[1].

Principe[modifier | modifier le code]

Le graphe de dépendance des sous-problèmes pour le calcul de F5, le 5ème terme de la suite de Fibonacci.

Illustrons la programmation dynamique sur le calcul du nème terme de la suite de Fibonacci, souvent utilisé comme exemple introductif dans un cours sur la programmation dynamique[2][réf. insuffisante]. La suite de Fibonacci est définie par F0 = F1 = 1 et Fn = Fn-1 + Fn-2. 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 Fn s'obtient en additionnant Fn-1 et Fn-2.

La méthode de programmation dynamique, comme la méthode 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é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 1
   sinon
         retourner fibonacci(n-1) + fibonacci(n-2)

Le graphe de dépendance montré sur la droite n'est pas un arbre : cela illustre que les sous-problèmes se chevauchent. La programmation dynamique consiste alors à stocker les valeurs des sous-problèmes pour éviter les recalculs[3]. 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] = 1
   F[1] = 1
   pour tout i de 2 à n
        F[i] := F[i-1] + F[i-2]  
   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] est défini
         retourner F[n]
   si n = 0 ou n = 1
         F[n] := 1
   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[3].

  1. Caractériser la structure d’une solution optimale.
  2. Définir (souvent de manière récursive) la valeur d’une solution optimale.
  3. Calculer la valeur d’une solution optimale.
  4. 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 élémentaires[modifier | modifier le code]

Pyramide de nombres[modifier | modifier le code]

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[4][réf. insuffisante]. 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 chemins et 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 relation de récurrence, puis en donnant un algorithme (avec méthode ascendante ou descendante).

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

Donnons maintenant une définition récursive de  :

pour toute position situé au rez-de chaussée de la pyramide
pour toute autre position , où et sont les positions inférieurs gauche et droite sous la position .S

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 du sommet portant 4 du milieu par exemple est calculée deux fois, en venant de 7 et en venant du 4 au-dessus. Le paradigme de la programmation dynamique consiste à calculer les valeurs 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 .

Calcul d'un produit de matrices[modifier | modifier le code]

On se donne des matrices , et on veut calculer la matrice produit [5],[3]. 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 exige un nombre de multiplications différent à mesure que l'on débute par avec 320 multiplications, ou bien avec 300 multiplications, la seconde façon est optimale par rapport au nombre de multiplication.

Chaque matrice a lignes et colonnes. Le produit demande opérations. On note le nombre minimum d'opérations pour calculer le produit . On a alors

Pour obtenir la meilleure valeur pour le produit , on le découpe en et et on choisit le meilleur . Ceci conduit à la formule :

.

Le calcul des 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[modifier | modifier le code]

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 une après les autres. En 1953, il en donne la définition moderne, où les décisions à prendre sont ordonnés par sous-problèmes[6] 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 autobibliographie, Eye of the Hurricane: An Autobiography [7]. Il dit :

« 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 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.[8] 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 programmation linéaire et programmation mathématique, synonyme pour optimisation mathématique[9].

Mais cette explication est controversée. Dans le livre Artificial Intelligence: A Modern Approach de Russell et Norvig[10], pense que l'explication ci-dessus n'est pas tout à fait vrai car le premier article de 1952 où Bellman utilise le terme programmation dynamique a paru avant que Wilson devienne secrétaire de la défense en 1953. Aussi, dans un discours de Harold J. Kushner[11], il dit de Bellman : « 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[modifier | modifier le code]

Connexions[modifier | modifier le code]

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[12]. 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.

Notes et références[modifier | modifier le code]

  1. a, b et c Cormen et al., Introduction à l'algorithmique, p. 359.
  2. (en) « Cours du MIT sur la programmation dynamique ».
  3. a, b et c Cormen et al., Introduction à l'algorithmique, p. 315-316.
  4. Openclassrooms.
  5. Cori.
  6. [PDF] Stuart Dreyfus, « Richard Bellman on the birth of Dynamical Programming ».
  7. Richard Bellman, Eye of the Hurricane: An Autobiography , 1984, p. 159.
  8. Eddy, S. R., What is dynamic programming?, Nature Biotechnology, 22, 909–910, 2004.
  9. Nocedal, J.; Wright, S. J.: Numerical Optimization, page 9, Springer, 2006.
  10. Russell, S. and Norvig, P., Artificial Intelligence: A Modern Approach, 3rd edition, Prentice Hall, 2009.
  11. Harold J. Kushner.
  12. A. Martelli, « An application of heuristic search methods to edge and contour detection », Comm. ACM, 19(2):73--83, février 1976.

Bibliographie[modifier | modifier le code]

Ouvrages historiques
  • Richard Bellman, Dynamic Programming, Princeton, Princeton University Press, . — Réimpression 2003, Dover Publication, Mineola, New-York, (ISBN 0-486-42809-5).
  • Stuart Dreyfus, « Richard Bellman on the birth of Dynamic Programming », Operations Research, vol. 50, no 1,‎ , p. 48-51 (ISSN 1526-5463, lire en ligne)
Cours et notes de cours

Articles liés[modifier | modifier le code]