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

Principe[modifier | modifier le code]

La programmation dynamique s'appuie sur un principe simple, appelé le principe d'optimalité de Bellman : toute solution optimale s'appuie elle-même sur des sous-problèmes résolus localement de façon optimale[2]. Concrètement, cela signifie que l'on peut déduire une ou la solution optimale d'un problème en combinant des solutions optimales d'une série de sous-problèmes. Les solutions des problèmes sont calculées de manière ascendante, c'est-à-dire qu'on débute par les solutions des sous-problèmes les plus petits pour ensuite déduire progressivement les solutions de l'ensemble.

La méthode de programmation, comme la méthode diviser pour régner, résout des problèmes en combinant des solutions de sous-problèmes. Alors que 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 programmation dynamique, quant à elle, peut s’appliquer même lorsque les sous-problèmes ne sont pas indépendants, c’est-à-dire lorsque des sous-problèmes comportent des parties communes. Dans ce cas, un algorithme diviser-pour-régner fait du travail inutile en résolvant plusieurs fois le sous-problème commun. Un algorithme de programmation dynamique résout chaque sous-problème une seule fois et mémorise la réponse dans un tableau, évitant ainsi le recalcul[3].

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. Le développement d’un algorithme de programmation dynamique peut être découpé 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 de manière ascendante.
  4. Construire une solution optimale à partir des informations calculées.

La dernière étape n'est utile que si on veut connaître plus que la valeur optimale.

Exemples élémentaires[modifier | modifier le code]

Une pyramide de nombres[modifier | modifier le code]

Dans une pyramide de nombres, en partant du sommet, et en se dirigeant vers le bas à chaque étape, on cherche à maximiser le total des nombres traversés[4].

     3
    7 4
   2 4 6
  9 5 9 3

On peut voir la pyramide comme un graphe, parcourir les 8 chemins, et choisir celui qui a le plus grand total. Quand la pyramide a n niveaux, il y a chemins.

La définition récursive du maximum est facile. Pour un sommet , notons la valeur qu'il porte et le maximum cherché. Alors

pour un sommet de la ligne du bas, et sinon

.

et sont les sommets à gauche et à droite sous . Mais 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 au contraire à évaluer la fonction c(x) de manière ascendante, d'abord le niveau le plus bas, puis le niveau au-dessus, et ainsi de suite. 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 . L'important est de conserver dans un tableau les valeurs intermédiaires.

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 d'une matrice ligne par une matrice colonne de taille ne coûte que multiplications élémentaires, le produit d'une matrice colonne par une matrice ligne en coûte .

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.

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[6]. 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. L'inverse n'est pas vrai en général et un ensemble de sous-solutions chacune optimale ne garantit pas un résultat général lui-même optimal.
  3. a, b et c Cormen et al., Introduction à l'algorithmique, p. 315-316.
  4. Openclassrooms.
  5. Cori.
  6. 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]