Programmation dynamique

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Cet article traite d'un paradigme algorithmique. Pour une classe particulière de langages de programmation, voir langage de programmation dynamique

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. terme « programmation » signifie à l’époque plus planification et ordonnancement.

La programmation dynamique s'applique avec succès lorsque le problème d'optimisation est composé de plusieurs sous-problèmes de même nature, et qu'une solution optimale du problème global s'obtient à partir de solutions optimales des sous-problèmes.

Elle a d'emblée connu un grand succès, car de nombreuses fonctions économiques de l'industrie étaient de ce type.

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[1]. 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 programmation dynamique, 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[2].

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

  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 utile 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[3].

     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 2^{n-1} chemins.

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

c(x) = v(x)

pour un sommet de la ligne du bas, et sinon

c(x) = v(x) +\max(c(g(x)),c(d(x)).

g(x) et d(x) sont les sommets à gauche et à droite sous x. 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 n(n+1)/2. 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 M_1, M_2,\ldots, M_h, et on veut calculer la matrice produit M_1 M_2 \cdots M_h[4],[5]. 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 un matrice colonne de taille m ne coûte que m multiplications élémentaires, le produit d'une matrice colonne par une matrice ligne en coûte m^2.

Chaque matrice M_i a m_i lignes et m_{i+1} colonnes. Le produit M_{i-1}M_i demande O(m_{i-1}m_im_{i+1}) opérations. On note c_{i,j} le nombre minimum d'opérations pour calculer le produit M_i\cdots M_j. On a alors

c_{i,i}=0, c_{i-1,i}=m_{i-1}m_im_{i+1}

Pour obtenir la meilleure valeur pour le produit M_i\cdots M_j, on le découpe en M_i\cdots M_k et M_{k+1}\cdots M_j et on choisit le meilleur k. Ceci conduit à la formule :

c_{i,j}=  \min_{i\le k<j}[c_{i,k} +  c_{k+1,j}+ m_{i}m_{k+1}m_{j+1}].

Le calcul des c_{i,j} 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]

  • 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.

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. 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.
  2. a et b Cormen et al., Introduction à l'algorithmique, p. 315-316.
  3. Openclassrooms.
  4. Cori.
  5. Cormen2fr.
  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 histoirques
  • Richard Bellman, Dynamic Programming, Princeton, Princeton University Press,‎ 1957. — 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,‎ janvier-février 2002, p. 48-51 (ISSN 1526-5463, lire en ligne)
Cours et notes de cours

Articles liés[modifier | modifier le code]