Aller au contenu

Programmation dynamique

Principe de la 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.
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.

La programmation dynamique est utilisée pour résoudre des problèmes d'optimisation. La conception d’un algorithme de programmation dynamique est typiquement découpée en 4 étapes :

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

En pratique, il s’agit de stocker les résultats des sous-problèmes au fur et à mesure pour éviter d’avoir à les résoudre plusieurs fois et les réutiliser facilement. Ce principe de stockage s’appelle la « mémoïsation ».

L’un des avantages de la programmation dynamique sur la méthode « diviser pour régner » vient de la mémoïsation. Chaque sous-problème n’est traité qu’une seule fois avec la programmation dynamique. Ce n’est pas forcément le cas avec la méthode « diviser pour régner ».

Application à la suite de Fibonacci⚓︎

Le graphe de dépendance ci-dessus permet d'illustrer que les sous-problèmes se chevauchent.
Par exemple, pour calculer F5, il faut F3 et F4.
Mais pour calculer F4, il faut F2 et F3.
F3 est donc utile à la fois pour le calcul de F4 et pour le calcul de F5.

La programmation dynamique consiste alors à stocker les valeurs des sous-problèmes pour éviter les recalculs. Il existe alors deux méthodes pour calculer effectivement une solution : la méthode ascendante et la méthode descendante.

Suite de Fibonacci et programmation dynamique ascendante

Dans la méthode ascendante (« bottom-up dynamic programming »), 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.

🐍 Editeur
def fibonacci(n: int) -> int:
    """programmation dynamique ascendante"""
    F = [0]*(n+1)
    F[0] = 0
    F[1] = 1
    for i in range(2, n+1):
        F[i] = F[i-1] + F[i-2]  
    return F[n]

#------------------------------------- TEST ------------------------------------ 

from time import perf_counter_ns

ti = perf_counter_ns()
f100 = fibonacci(100)
tf = perf_counter_ns()

print("fibonacci(100) = ", f"{f100:_}".replace('_', ' '),\
      "\ncalculé en", (tf-ti)/1e3, "ms")
▶️ Console
>>>
fibonacci(100) =  354 224 848 179 261 915 075 
calculé en 15.6 ms
>>>
Suite de Fibonacci et programmation dynamique descendante

Dans la méthode descendante (« top-down dynamic programming »), 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 dictionnaire F les résultats des appels récursifs :

🐍 Editeur
def fibonacci(n: int, F: dict={0: 0, 1: 1}) -> int:
    """programmation dynamique descendante"""
    if n not in F:
        F[n] = fibonacci(n-1, F) + fibonacci(n-2, F)
    return F[n]

#------------------------------------- TEST ------------------------------------

from time import perf_counter_ns

ti = perf_counter_ns()
f100 = fibonacci(100)
tf = perf_counter_ns()

print("fibonacci(100) = ", f"{f100:_}".replace('_', ' '),\
      "\ncalculé en", (tf-ti)/1e3, "ms")
▶️ Console
>>>
fibonacci(100) =  354 224 848 179 261 915 075 
calculé en 88.9 ms
>>>

Application au rendu de monnaie⚓︎

Rappel de l'énoncé du problème

Étant donné un système de monnaie (pièces et billets), comment rendre une somme donnée de façon optimale, c'est-à-dire avec le nombre minimal de pièces et billets ?

Le système de monnaie peut être identifié à un tableau croissant de n nombres :

monnaie = [1, 2, 5, 10, 20, 50, 100, 200, 500]
pour la zone euro si on ne tient pas compte des centimes.
On souhaite écrire une fonction rendu prenant en argument la liste monnaie et un entier s, correspondant à la somme d’argent à rendre, et renvoyant un tableau de longueur n indiquant le nombre de pièces ou billets à rendre de chaque sorte.
Ainsi, rendu([1, 2, 5], 9) renverra [0, 2, 1].

Algorithme glouton

Le problème du rendu de la monnaie a déjà été abordé en 1ère avec un algorithme glouton. On a vu que cet algorithme ne conduit pas nécessairement à une solution optimale mais que le coût temporel restait acceptable pour obtenir une valeur approchée de la solution. Ainsi, rendu([1, 3, 4], 6) renvoie [2, 0, 1] (3 pièces) au lieu de [20, 2, 0] (2 pièces).

🐍 Editeur
def rendu(monnaie: list, somme: int, index: int=None) -> list:
    """Rendu de monnaie récursif glouton"""
    if index is None:
        index = len(monnaie) - 1
    if somme == 0:
        return [0] * len(monnaie)
    if index < 0 or somme < 0:
        return None
    if somme >= monnaie[index]:
        restant = rendu(monnaie, somme-monnaie[index], index)
        # Solution trouvée pour le reste de la somme
        if restant is not None:
            # Incrémente le nombre de pièces/billets pour la valeur actuelle
            restant[index] += 1
            return restant
    # Si aucune solution, explore avec la valeur monétaire précédente
    return rendu(monnaie, somme, index-1)
▶️ Console
>>> rendu([1, 2, 5], 9)
[0, 2, 1]
>>> rendu([1, 3, 4], 6)
[2, 0, 1]
Solution optimale

Il est possible de déterminer la solution optimale avec un coût temporel raisonnable grâce à la programmation dynamique.

Rendu de monnaie et programmation dynamique ascendante

Exemple : monnaie = (1, 2, 5) et s = 13
On trouve une solution optimale pour chaque somme d’argent de 0 à s.
En effet, si on connaît les façons optimales de rendre toute somme d’argent strictement inférieure à s = 13, alors pour rendre une somme s , on prend une pièce, à choisir dans le n-uplet monnaie, et une somme strictement inférieure à s , ce qui correspond à un problème déjà résolu. Ainsi, on trouve la solution optimale avec une somme s en comparant les n solutions pour chaque pièce du n-uplet monnaie. On remplit le tableau par colonne. On peut noter directement les solutions dans le tableau.

Pour obtenir s = 13, il y a trois possibilités :
Possibilité n°1 : en ajoutant 1 pièce de 1 € :
13=12+1 → soient 3+1=4 pièces ([0, 1, 2] + [1, 0, 0] → [1, 1, 2])
Possibilité n°2 : en ajoutant 1 pièce de 2 € :
13=11+2 → soient 3+1=4 pièces ([1, 0, 2] + [0, 1, 0] → [1, 1, 2])
Possibilité n°3 : en ajoutant 1 pièce de 5 € :
13=8+5 → soient 3+1=4 pièces ([1, 1, 1] + [0, 0, 1] → [1, 1, 2])

Dans tous les cas, la solution est [1, 1, 2], i.e. avec :
• 1 pièce de 1 €,
• 1 pièce de 2 €,
• 2 pièces de 5 €.
soient 4 pièces.

🐍 Editeur
def rendu_dyn_bottom_up(monnaie: list, somme: int) -> list:
    """Rendu de monnaie dynamique bottom-up"""
    nb_pieces = [0] + [float('inf')] * somme
    # Stocker les pièces rendues pour chaque somme
    pieces_rendues = [[0] * len(monnaie) for _ in range(somme + 1)]
    for s in range(1, somme + 1):
        for j in range(len(monnaie)):
            p = monnaie[j]
            if p <= s and 1 + nb_pieces[s-p] < nb_pieces[s]:
                nb_pieces[s] = 1 + nb_pieces[s-p]
                # Copie de pieces_rendues[s-p] pour éviter un effet de bord
                pieces_rendues[s] = list(pieces_rendues[s-p])
                # Mise à jour des pièces rendues
                pieces_rendues[s][j] += 1
    return pieces_rendues[somme]
▶️ Console
rendu_dyn_bottom_up([1, 2, 5], 13)
>>> [1, 1, 2]
rendu_dyn_bottom_up([1, 3, 4], 6)
[0, 2, 0]
Visualisation dans Pythontutor

Rendu de monnaie et programmation dynamique descendante

🐍 Editeur
def rendu_dyn_top_down(monnaie, somme, memo=None):
    # Utilisation d'un dictionnaire pour mémoriser les résultats
    if memo is None:
        # Initialisation avec une liste de 0 pour chaque pièce de monnaie
        memo = {0: [0] * len(monnaie)}
    # Principe de la mémoïsation : 
    # si le résultat a déjà été calculé, on ne le recalcule pas
    if somme in memo:
        return memo[somme]  
    possibilites = []
    for i in range(len(monnaie)):
        p = monnaie[i]
        if somme - p >= 0:
            precedent = rendu_dyn_top_down(monnaie, somme - p, memo)
            nouveau = precedent.copy()  # Copie du résultat précédent
            nouveau[i] += 1  # Ajout de 1 à la pièce actuelle
            possibilites.append(nouveau)
    choix_optimal = min(possibilites, key=lambda x: sum(x))
    memo[somme] = choix_optimal
    return memo[somme]
▶️ Console
rendu_dyn_top_down([1, 2, 5], 13)
>>> [1, 1, 2]
rendu_dyn_top_down([1, 3, 4], 6)
[0, 2, 0]

Alignement de séquences en Python (vidéo)⚓︎

Programmation dynamique #1/2 | Cédric Gerland (20:01)

Rendu de monnaie en Python (vidéo)⚓︎

Programmation dynamique #2/2 | Cédric Gerland (20:48)

Programmation dynamique (doc. Eduscol)⚓︎

Fichier PDF (doc. Eduscol)