Programmation dynamique

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

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.

Other Languages
Bahasa Indonesia: Pemrograman dinamis
日本語: 動的計画法
한국어: 동적 계획법
srpskohrvatski / српскохрватски: Dinamičko programiranje
Simple English: Dynamic programming
oʻzbekcha/ўзбекча: Dinamik dasturlash
Tiếng Việt: Quy hoạch động
中文: 动态规划