Qu'est-ce que Programmation dynamique ?

Méthode de conception d'algorithmes qui découpe un problème en sous-problèmes plus petits et enregistre leurs réponses dans une table pour les réutiliser, ce qui évite de recalculer plusieurs fois la même chose. On l'utilise pour le problème du sac à dos, le rendu de monnaie avec un minimum de pièces, la plus longue sous-séquence commune, les plus courts chemins, etc.

Nom japonais: 動的計画法

« Programmation dynamique » apparaît dans 3 questions d'entraînement réparties sur 1 thèmes, dont Structures de données et algorithmes.

Domaine: Structures de données et algorithmes

L'idée : résoudre une seule fois chaque sous-problème qui se répète

Calculer les nombres de Fibonacci directement à partir de fib(n) = fib(n−1) + fib(n−2) par récursion recalcule les mêmes valeurs encore et encore, si bien que le nombre d'appels croît exponentiellement (environ 2,69 millions pour fib(30)). La programmation dynamique enregistre la réponse de chaque sous-problème dès qu'elle est trouvée et se contente ensuite de la consulter, si bien que fib(n) demande un travail proportionnel à n. Elle s'applique quand la solution optimale d'un grand problème peut se construire à partir des solutions optimales de sous-problèmes plus petits (sous-structure optimale) et que les mêmes sous-problèmes apparaissent de nombreuses fois (chevauchement des sous-problèmes).

Mémoïsation et remplissage de tables

Il existe deux façons de l'implémenter : la mémoïsation (descendante), qui garde la récursion mais retient les résultats calculés, et l'approche ascendante, qui remplit une table en partant des plus petits sous-problèmes. Pour le problème du sac à dos 0/1, par exemple, la table contient « la valeur maximale atteignable avec les objets jusqu'à i dans la capacité c », et on la remplit en prenant le plus grand des deux cas, avec ou sans chaque objet. Pour n objets et une capacité W, cela prend O(nW). Le problème du nombre minimal de pièces se résout de même en tabulant le nombre minimal de pièces pour chaque montant de 0 jusqu'à la cible.

Différence avec les algorithmes gloutons, et applications

Un algorithme glouton se contente de prendre le choix qui paraît le meilleur à chaque instant et de passer à la suite : il est rapide, mais pas optimal pour certains problèmes. Pour payer 8 yens avec des pièces de 1, 4 et 6 yens, l'algorithme glouton utilise trois pièces, 6 + 1 + 1, alors que la programmation dynamique en trouve deux, 4 + 4. La programmation dynamique est très utilisée, par exemple pour la distance d'édition et la plus longue sous-séquence commune de chaînes de caractères (comme dans la commande diff), l'alignement de séquences d'ADN, l'algorithme de Viterbi en reconnaissance vocale et l'algorithme de Floyd-Warshall pour les plus courts chemins entre toutes les paires de sommets.

S'entraîner : questions sur Programmation dynamique

Une fonction fib(n) qui calcule les nombres de Fibonacci est définie par récursion : « si n vaut 1 ou moins, renvoyer n ; sinon, renvoyer fib(n−1) + fib(n−2) ». Quand on appelle fib(5), combien de fois fib est-elle appelée, premier appel compris ?

Afficher la réponse et l'explication

Réponse : C. 15

Soit C(n) le nombre d'appels pour fib(n). On a C(0) = C(1) = 1 et C(n) = 1 + C(n−1) + C(n−2), donc C(2) = 3, C(3) = 5, C(4) = 9 et C(5) = 15. Comme les mêmes valeurs sont recalculées encore et encore, le nombre d'appels croît exponentiellement avec n : fib(30) fait environ 2,69 millions d'appels. Avec la mémoïsation (une forme de programmation dynamique), qui conserve dans une table les valeurs déjà calculées, seules les six valeurs fib(0) à fib(5) sont calculées et le nombre d'appels tombe à 9 (2n − 1). 6 est le nombre d'arguments distincts, et 9 le nombre d'appels avec mémoïsation.

On paie 8 yens avec des pièces de 1 yen, 4 yens et 6 yens. Quelle affirmation relie correctement le nombre de pièces choisi par un algorithme glouton, qui utilise d'abord autant que possible la plus grosse pièce, et le nombre minimal de pièces ?

AL'algorithme glouton atteint lui aussi le minimum de 2 pièces
BL'algorithme glouton utilise 3 pièces et manque le minimum de 2
CL'algorithme glouton utilise 3 pièces, et c'est le minimum

Afficher la réponse et l'explication

Réponse : B. L'algorithme glouton utilise 3 pièces et manque le minimum de 2

L'algorithme glouton prend d'abord une pièce de 6 yens et paie les 2 yens restants avec deux pièces de 1 yen, soit 3 pièces. Or deux pièces de 4 yens suffisent pour payer avec seulement 2 pièces. Comme un algorithme glouton ne fait qu'accumuler le choix qui paraît le meilleur à chaque instant, il n'est pas optimal pour certains systèmes de pièces. La programmation dynamique, qui remplit dans l'ordre croissant une table du nombre minimal de pièces pour chaque montant de 0 à 8 yens, trouve toujours le minimum. Pour des systèmes de pièces comme celui du Japon (1, 5, 10, 50, 100 et 500 yens), l'algorithme glouton donne toujours le minimum.

Questions fréquentes

En quoi la programmation dynamique diffère-t-elle de « diviser pour régner » ?

Les deux découpent un problème en sous-problèmes, mais dans les algorithmes de type « diviser pour régner » comme le tri fusion, les sous-problèmes ne se chevauchent pas, si bien qu'il n'est pas nécessaire d'enregistrer les réponses. La programmation dynamique s'en distingue en enregistrant et en réutilisant les réponses quand les mêmes sous-problèmes apparaissent de nombreuses fois.

Quelles sont les faiblesses de la programmation dynamique ?

Elle demande une mémoire et un travail proportionnels à la taille de la table. Le O(nW) du problème du sac à dos est proportionnel à la valeur de la capacité W, si bien qu'il devient impraticable quand W est très grand. On peut réduire la mémoire en n'enregistrant que le nécessaire ou en ne gardant que la ligne précédente de la table.

« Programmation dynamique » dans les explications

Avec la mémoïsation (une forme de programmation dynamique), qui conserve dans une table les valeurs déjà calculées, seules les six valeurs fib(0) à fib(5) sont calculées et le nombre d'appels tombe à 9 (2n − 1).
Une fonction fib(n) qui calcule les nombres de Fibonacci es…
La programmation dynamique, qui remplit dans l'ordre croissant une table du nombre minimal de pièces pour chaque montant de 0 à 8 yens, trouve toujours le minimum.
On paie 8 yens avec des pièces de 1 yen, 4 yens et 6 yens. …
La programmation dynamique met à jour, objet par objet, une table de la meilleure valeur atteignable pour chaque capacité c, et trouve l'optimum en O(nW) pour n objets et une capacité W.
On remplit un sac à dos de capacité 8 avec des objets chois…

Questions mentionnant « Programmation dynamique » (3)

Termes associés

Algorithme glouton (greedy) Récursion (récursivité) Argument Algorithme de Dijkstra Arbre binaire de recherche (binary search tree) Complexité temporelle (notation grand O) File d'attente Liste chaînée (linked list) Parcours en largeur (breadth-first search) Parcours en profondeur (depth-first search)

Retour au glossaire