Programmation dynamique

Un exemple simple

Chemin d'un pion sur un damier Le jeu de Dames se pratique sur un damier de 10 cases sur 10. Les pions sont placés sur les cases foncées et ne peuvent se déplacer que d'une case à la fois, toujours vers l'avant en diagonale. Une des stratégies du jeu consiste à amener un pion sur la dernière rangée pour être promu en dame.

La question est la suivante : Sur le damier ci-contre, combien de chemins peut emprunter le pion blanc depuis cette case de départ pour arriver à la case vide sur la rangée du haut et être promu en dame ?

Si on essaie de compter tous les chemins on risque de vite perdre le compte. Une idée simple pour répondre à ce problème efficacement consiste à noter à chaque intersection le nombre de chemins en partant de la fin. Découpons le processus en plusieurs étapes.

Etape 1Etape 2Etape 3Etape 4Etape 5Etape 6

On peut déjà observer qu'un certain nombre de cases ne peuvent pas être atteintes par le pion blanc depuis sa position de départ, ou ne peuvent pas mener à la case d'arrivée, on peut donc les exclure de nos calculs.

Chemin d'un pion sur un damier-étape 1

Il n'y a que deux cases sur la deuxième rangée qui permettent d'aller sur la case d'arrivée, et pour chacune il n'y a qu'un seul chemin possible.

Marquons ces cases avec leur nombre de chemins possibles.

Chemin d'un pion sur un damier-étape 2

Il y a trois cases sur la troisième rangée pouvant aller sur les deux cases précédentes.

Un pion sur la case à gauche ou celle à droite n'a qu'un seul chemin possible.

Par contre un pion sur la case au milieu peut se déplacer soit vers le haut à droite, soit vers le haut à gauche. Dans les deux cas, il n'a plus qu'un chemin possible ensuite. Il y a donc deux chemins possibles au départ de cette case.

Chemin d'un pion sur un damier-étape 3

Continuons à la rangée suivante. Comme dans la rangée précédente, un pion sur la case à gauche ou celle à droite n'a qu'un seul chemin possible.

Les deux pions placés au milieu peuvent se déplacer soit vers le haut à droite, soit vers le haut à gauche. Selon le choix que l'on fait, ils pourront emprunter 1 ou 2 chemins différents. Au total, il y a donc 3 chemins possibles au départ de ces deux cases. On comprend que le nombre de chemins possibles à partir d'une case est égal à la somme des nombres de chemins au départ des cases à gauche et à droite de la rangée du dessus.

On a décomposé un problème en deux sous-problèmes plus simples.

Chemin d'un pion sur un damier-étape 4

Appliquons cette même idée à la rangée suivante, et notons le nombre de chemins possibles égal à la somme des nombres de chemins indiqués dans les cases à gauche et à droite sur la rangée du dessus.

On constate le nombre de chemins calculé pour une case, par exemple 3, est utilisé deux fois : pour la case qui a 4 chemins possibles et pour la case qui a 6 chemins possibles.

Il faut donc garder en mémoire les résultats intermédiaires pour ne pas recalculer la même chose plusieurs fois.

Chemin d'un pion sur un damier-étape 5

Continuons à descendre dans le damier rangé par rangée en appliquant le même principe : pour chaque case on ajoute les nombres de chemins trouvés pour les cases à gauche et à droite de la rangée de dessus.

On arrive au résultat final : il y a 126 chemins possibles pour aller de la case de départ jusqu'à l'arrivée.

Chemin d'un pion sur un damier-étape 6

On peut observer deux choses dans la réalisation de cet algorithme :

Pour chaque case, il suffit de faire la somme du nombre de chemins depuis la case de gauche et depuis la case de droite sur la rangée au-dessus : on découpe le problème en sous-problèmes plus faciles à résoudre.
Le nombre de chemins calculé pour une case est utilisé pour calculer les nombres de chemins de plusieurs autres cases. Les sous-problèmes se chevauchent. Il faut garder en mémoire les résultats intermédiaires pour ne pas recalculer la même chose plusieurs fois.

Ce sont les deux principes de la programmation dynamique.

Exercice corrigé

Mario veut rejoindre la princesse Peach. Il ne peut se déplacer que vers la gauche et vers le haut, et ne peut jamais revenir en arrière. Combien de chemins différents peut-il emprunter ?

Chemin de mario sur un quadrillage 3 x 4

Réponse

Notons à chaque intersection le nombre de chemins en partant de la fin. Pour chaque intersection, il suffit de faire la somme du nombre de chemins depuis l‘intersection à sa gauche et des chemins depuis l'intersection au dessus.

Chemin de mario sur un quadrillage 3 x 4

Mario peut prendre 10 chemins différents.

Cours

La programmation dynamique¹ résout un problème en combinant des solutions de sous-problèmes qui se chevauchent, c'est à dire qu'il possède des sous-sous-problèmes identiques.

Afin d'éviter les calculs redondants, chaque sous-sous-problème n'est résolu qu'une seule fois et sa réponse est gardée en mémoire.

On peut voir la programmation dynamique comme une amélioration ou une adaptation de la méthode « diviser pour régner » puisqu'on divise un problème en sous problèmes, à la différence que la programmation dynamique s'applique quand les sous-problèmes se chevauchent, autrement dit un sous-problème peut être utilisé dans la solution de plusieurs sous-problèmes différents. Tandis que l'approche « diviser pour régner » crée des sous-problèmes qui sont complètement séparés et peuvent être résolus indépendamment les uns des autres.

Graphe comparant la méthode diviser pour régner et la programmation dynamique

Rendu de monnaie

Problème : On dispose d'un nombre illimité de pièces de ①, ②, ⑤ et ⑩ euros pour rendre une certaine somme. Quel est le plus petit nombre de pièces nécessaire ?

Algorithme glouton

On a vu en classe de première une solution donnée par un algorithme glouton, qui consiste à faire, étape par étape, un choix optimum local, dans l'espoir d'obtenir un résultat optimum global : dans ce cas on choisit de façon répétitive la pièce de plus grande valeur qui ne dépasse pas la somme restante :

Programme itératifProgramme récursif

pieces = [10, 5, 2, 1]

def rendu_monnaie_glouton(n):
    nombre_pieces = 0
    i = 0 # on commence par la plus grande pièce
    while n > 0:
        if n >= pieces[i]: # on peut rendre pieces[i]
            nombre_pieces += 1
            n = n - pieces[i]
        else:    # on passe à la pièce suivante
            i = i + 1
    return nombre_pieces

pieces = [10, 5, 2, 1]

def rendu_monnaie_glouton(n, i=0):
    if n == 0: 
       return 0  
    if pieces[i] <= n:  # on peut rendre pieces[i]
        return 1 + rendu(n - pieces[i], i)
    return rendu(n, i + 1)   # on passe à la pièce suivante

Testons l'algorithme glouton pour rendre 13 euros. On obtient bien les 3 pièces ⑩ + ② + ① qui font un total de 13.

>>> rendu_monnaie_glouton(13)
3

Mais que se passe-t-il si on n'a pas de pièce de 1 euro ? Remplaçons pieces = [10, 5, 2] et testons l'algorithme :

IndexError: list index out of range

Pourtant on peut rendre ⑤ + ② + ② + ② + ② qui font aussi un total de 13 euros !

C'est le propre des algorithmes gloutons : une fois qu'une décision a été prise, on ne revient pas en arrière. Dans certains cas l'algorithme ne trouve pas de solution, ou pas la meilleure solution. Ici l'algorithme choisit la pièce de 10 euros qui ne mène à rien, il ne peut pas revenir en arrière et ressayer avec une autre pièce !

Programmation dynamique

La programmation dynamique consiste à résoudre notre problème en combinant les solutions de sous-problèmes. Ici, rendre une somme \(n\) peut se faire de plusieurs manières :

rendre \(n – 10\) et rajouter une pièce de ⑩, ou
rendre \(n – 5\) et rajouter une pièce de ⑤, ou
rendre \(n – 2\) et rajouter une pièce de ②.

Dans notre exemple, pour rendre 13 euros on peut :

rendre 3 et rajouter une pièce de ⑩, ou
rendre 8 et rajouter une pièce de ⑤, ou
rendre 11 et rajouter une pièce de ②.

Graphe de rendu de monnaie pour 13 euros - première étape

Chacun de ces sous-problèmes peut être résolus de la même façon. Constituons l'arbre des possibilités :

Graphe de rendu de monnaie pour 13 euros - complet

Certaines branches mènent à une solution, quand il reste 0 euros à rendre, d'autres pas.

Implémentons cet algorithme en considérant trois cas :

Si \(n\) est égal à 0, alors on a rendu \(n\), il n'y a pas de pièces supplémentaires à rendre, on renvoie 0.
Si \(n\) est plus petit que la valeur de la plus petite pièce, on ne pourra pas rendre \(n\), on renvoie une très grande valeur, par exemple en utilisant inf la valeur infinie du module avec math, afin de ne pas impacter une autre branche qui mènerait à une solution.
Sinon, on renvoie 1 plus le plus petit nombre de pièces de tous les rendus de \(n – p\), pour toutes les pièces de valeur \(p\) telles que \(p <= n\).

Traduisons cet algorithme en Python :

from math import inf     # valeur infinie du module math

pieces = [10, 5, 2]

def rendu_monnaie_dynamique(n):
    if n == 0:  # Il faut 0 piece pour rendre 0 euro
        return 0                
    if n < min(pieces):   # n est plus petit que la plus petite piece
        return inf          # on ne peut pas rendre n avec ces pieces
    # Tableau de tous les rendus possibles de n - p
    rendus = [rendu_monnaie_dynamique(n - p) for p in pieces if p <= n]
    # On rend 1 piece + le plus petit nombre de pieces de tous les rendus
    return 1 + min(rendus)  

>>> rendu_monnaie_dynamique(13)
5

Avec la programmation dynamique, tous les cas possibles ont été traités, et plusieurs cas ont renvoyé la même solution. On a donc une solution optimale au problème.

Mais testons maintenant cette fonction avec quelques valeurs plus grandes que 13. Très vite la fonction prend beaucoup de temps pour s'exécuter. Quelques secondes pour exécuter rendu_monnaie_dynamique(60), dizaines de secondes pour rendu_monnaie_dynamique(70), plusieurs minutes pour rendu_monnaie_dynamique(80), etc. Le programme devient vite trop lent, même pour des rendus très simples de quelques pièces de ⑩ euros !

Essayons d'estimer la complexité temporelle de cette fonction. Le nombre d'opérations pour rendre un montant \(n\) avec des pieces de 10, 5 et 2 est le nombre d'opérations pour rendre \(n-10\), plus le nombre d'opérations pour rendre \(n-5\), plus celui pour rendre \(n-2\), plus quelques opérations élémentaires. Si on appelle \(T(n)\) le nombre d'opérations pour rendre \(n\), alors on peut donc écrire que :

\(T(n) = T(n-10) + T(n-5) + T(n-2) + O(1)\),

avec \(O(1)\) pour les quelques opérations supplémentaires. Pour de grandes valeurs de \(n\), on peut faire l'approximation que retirer 10, 5, 2 ou 1 euro à \(n\) ne change pas grand chose, donc que \(T(n-10)\), \(T(n-5)\), et \(T(n-2)\) sont du même ordre de grandeur que \(T(n-1)\), autrement dit \(T(n) \approx 3 \times T(n-1) + O(1)\). A chaque fois que \(n\) augmente de 1, le nombre d'opérations est multiplié par 3, plus quelques opérations. La complexité est donc exponentielle en \(O(3^n)\) ici, ou de façon générale en \(O({nbPieces}^n)\) pour un rendu avec \(nbPieces\) pieces.

Version descendante (top-down), récursivité et mémoïsation

Les appels récursifs sont trop nombreux, la complexité est trop importante pour calculer un solution en temps raisonnable.

En programmation dynamique les sous-problèmes se chevauchent et les mêmes calculs reviennent plusieurs fois. Dans un exemple aussi simple que celui de rendre 13 euros, on retrouve 2 fois la branche qui part de "6" :

Arbre de rendu de monnaie pour 13 euros - branche rendre 6

La solution pour limiter le nombre d'opérations consiste à ne calculer les solutions des sous-problèmes qu'une seule fois et de les garder en mémoire. C'est la technique de mémoïsation.

Cours

La mémoïsation consiste à garder en mémoire les valeurs déjà calculées.

Par exemple, avec un dictionnaire déclaré en variable globale :

from math import inf     # valeur infinie du module math

memoise = {0: 0}       # Il faut 0 piece pour rendre 0 euro
pieces = [10, 5, 2]

def rendu_monnaie_dynamique(n):
    if n in memoise:             # Si on a déjà calculé le nombre de pièces pour n
        return memoise[n]
    if n < min(pieces):   # n est plus petit que la plus petite piece
        return inf          # On ne peut pas rendre n avec ces pieces

    # Tableau de tous les rendus possibles de n - p
    rendus = [rendu_monnaie_dynamique(n - p) for p in pieces if p <= n]
    # On rend 1 piece + le plus petit nombre de pieces de tous les rendus
    memoise[n] = 1 + min(rendus)
    return memoise[n]

Cette fois ci, le résultat est immédiat, même avec des valeurs de n de quelques milliers (dans la limite de la pile d'appels récursifs).

Version ascendante (bottom-up)

On a déjà vu dans l'exemple précédent comment écrire un algorithme récursif en utilisant la mémoïsation. Une autre approche de la programmation dynamique consiste à calculer d'abord les sous-problèmes en partant d'un cas de base et à « remonter » jusqu'à résoudre le problème initial : c'est la version ascendante, ou bottom-up.

Rendu de monnaie pour 13 euros bottom-up

Appelons \(nb_i\) le nombre de pièces pour rendre une somme \(i\). Comme dans l'approche top-down, \(nb_i\) est égal à 1 + le plus petit nombre de pièces de tous les rendus de \(i – p\), pour toutes les pièces \(p\) telles que \(p <= i\). Si aucune pièce p ne convient, alors il n'est pas possible de rendre \(i\), on peut représenter \(nb_i\) par l'infini².

On va créer le même dictionnaire que celui utilisé pour la mémoïsation, mais en le remplissant itérativement en partant cette fois de 0 et en incrémentant jusqu'à n.

from math import inf

nb = {0: 0}       # dictionnaire {montant i: nombres de pieces pour rendre i}
pieces = [10, 5, 2]

def rendu_bottom_up(n):
    # On remplit le dictionnaire pour tous les montants i allant de 1 à n
    for i in range(1, n + 1):   
        # Tableau de tous les rendus possibles de i - p
        rendus = [nb[i - p] for p in pieces if p <= i]

        if rendus == []:   # Si c'est impossible de rendre i 
            nb[i] = inf
        else:           # Sinon on prend le plus petit nombre de pieces des i - p et on ajoute 1 
            nb[i] = 1 + min(rendus)
    return nb[n]              # On renvoie la valeur pour la clé correspondant au montant n

Ici, aucun soucis avec la complexité de la fonction (ni de limite de pile d'appels récursifs), la fonction s'exécute instantanément même avec de très grandes valeurs de n. En effet, la fonction fait une double boucle imbriquée, sur la valeur à rendre \(n\), et sur le nombre de pièces disponibles. La complexité est donc simplement linéaire en \(O(n \times nbPieces)\), ou plus simplement en \(O(n)\) si on considère un nombre limité de pièces disponibles.

Cours

La programmation dynamique peut prendre deux formes :

Une forme récursive descendante de haut en bas, ou top-down, avec mémoïsation :
- On utilise directement la formule de récurrence.
- Lors d'un appel récursif, avant d'effectuer un calcul on regarde si son résultat n'est pas gardé en mémoire.
- Sinon, on fait le calcul et on le garde en mémoire.
Une forme itérative ascendante de bas en haut, ou bottom-up :
- On résout de façon itérative d'abord les sous-problèmes de la plus "petite taille", puis ceux de la taille "d'au dessus", etc. Au fur et à mesure on garde les résultats en mémoire.
- On continue jusqu'à la taille voulue.

Découpe d'une tige d'acier

Problème : Soit une tige d'acier que l'on peut découper en plusieurs morceaux pour les revendre selon la grille de prix suivante :

Longueur (m)	0	1	2	3	4	5	6	7	8	9	10
Prix (€)	0	1	5	8	9	10	17	17	20	24	30

Comment découper la tige de façon optimale pour en tirer un revenu maximum ?

Prenons, l'exemple d'une tige de longueur 4 m. On peut la découper de 8 façons différentes :

Découpe d'une tige de 4 m

On voit que le revenu maximum est donc 10 €, obtenu en découpant la tige en 2 morceaux de 2 m. Mais comment le calculer de façon systématique ?

Un algorithme glouton simple qui consiste à choisir en priorité les longueurs de morceaux les plus chers ne donne pas le meilleur revenu puisqu'il proposera toujours de garder les morceaux les plus longs possibles, ce sont les plus chers selon la grille de prix. Une approche plus fine consiste à prendre en compte le prix linéaire (ratio prix/longueur) pour optimiser les découpes. Reprenons la grille de prix de l'exemple précédant pour les morceaux jusqu'à 4 m :

Longueur (m)	0	1	2	3	4
Prix (€)	0	1	5	8	9
Prix linéaire (€/m)	0	1	2,5	2,67	2,25

Cet algorithme glouton commence par choisir le meilleur ratio prix/longueur, c'est une découpe d'un morceau de 3 m, mais ensuite il ne reste plus qu'un autre morceau de 1 m, qui lui a une très faible valeur linéaire ! C'est trop tard, l'algorithme ne peut pas revenir en arrière sur la découpe du premier morceau de 3 m, on obtient un revenu de 9 €, ce n'est pas le revenu maximum.

ici encore, la programmation dynamique nous permet de trouver la solution optimale.

Appelons R[n] le revenu maximum d'une tige de longueur n et Prix le tableau de la grille de prix pour différentes longueurs.

Comment calculer R[4], le revenu maximum pour découper une tige de longueur 4 m ? On peut voir ce qu'il se passe si on fait une découpe d'un premier morceau de 1 m, ou bien de 2 m, ou encore de 3 m, ou même ne pas couper la tige, puis comparer le revenu obtenu dans chaque cas pour prendre le plus grand. R[4] est donc égal à la plus grande valeur entre :

Le prix d'un morceau de longueur 1 + le revenu maximum d'un tige de longueur 3 : Prix[1] + R[3]
Le prix d'un morceau de longueur 2 + le revenu maximum d'un tige de longueur 2 : Prix[2] + R[2]
Le prix d'un morceau de longueur 3 + le revenu maximum d'un tige de longueur 1 : Prix[3] + R[1]
Le prix d'un morceau de longueur 4 + le revenu maximum d'un tige de longueur 0: Prix[4] + R[0]

Découpe d'une tige de 4 m - éape 1 Découpe d'une tige de 4 m - étape 1

La valeur de R[0] est immédiate, c'est le revenu maximum d'une tige de longueur de zéro, c'est-à-dire 0. Mais comment calculer R[1], R[2] et R[3] ? On applique le même principe.

Découpe d'une tige de 4 m - arbre complet

On voit qu'on a ici découpé le problème en plusieurs sous-problèmes. Par ailleurs, les résultats de certains sous-problèmes, par exemple le calcul de R[2], sont réutilisés plusieurs fois. Les sous-problèmes se chevauchent. Ce sont les deux grands principes de la programmation dynamique.

Généralisons cet algorithme à une tige de longueur n pour écrire R[n] en considérant les deux cas :

Si n est égal à 0, alors la tige a une longueur de 0, son revenu maximum est 0.
Sinon, R[n] est égal à la plus grande valeur entre les prix d'un morceau de longueur i (prix[i]) auquel on ajoute le revenu maximum d'une tige de longueur n - i (R[n-i]), calculés pour toutes les longueurs i possibles, c'est-à-dire toutes les valeurs de i allant de 1 à n + 1 (exclus) sans dépasser la taille de la grille des prix : 1 <= i < min(len(Prix), n + 1).

On peut donc écrire la formule : R[n] = max(Prix[i] + R[n - i] pour 1 ≤ i < min(len(Prix), n + 1) et R[0] = 0.

Traduisons maintenant cet algorithme de programmation dynamique en version descendante :

Prix = [0, 1 ,5, 8, 9, 10, 17, 17, 20, 24, 30]

def R(n):
    if n == 0: # Le revenu d'une tige de longueur 0 est 0
        return 0

    # Tableau des revenus max de toutes les découpes possibles de la grille de prix
    decoupes = [Prix[i] + R(n - i) for i in range(1, min(len(Prix), n + 1))]

    # On renvoie le plus grand revenu de toutes les découpes possibles
    return max(decoupes)

Avec la programmation dynamique, tous les cas possibles ont été traités, et plusieurs cas ont renvoyé la même solution. On obtient donc une solution optimale au problème.

>>> R(4)
10

Mais testons maintenant cette fonction avec quelques valeurs plus grandes que 4. Très vite la fonction prend beaucoup de temps pour s'exécuter. Essayons d'estimer la complexité temporelle de cette fonction.

Si on appelle \(T(n)\) le nombre d'opérations pour calculer le revenu maximum pour une tige de longueur \(n\), il est égal aux nombres d'opérations de toutes les découpes de tiges de longueurs \(n - i\), \(T(n - i)\), pour toutes les valeurs de \(i\) de la grille de prix, plus quelques opérations élémentaires.

\(T(n) = T(n-1) + T(n-2) + T(n-3) + ..T(n-i)+... + T(n - 10) + O(1)\),

Si on suppose que pour les grandes valeurs de \(n\), \(i\) reste très petit en comparaison, par exemple ici il vaut entre 1 et 10, alors on peut écrire que :

\(T(n) \approx 10 \times T(n-1) + O(1)\)

A chaque fois que \(n\) augmente de 1, le nombre d'opérations est multiplié par la taille de la grille de prix, plus quelques opérations. La complexité est donc exponentielle en \(O(10^n)\) ici, ou de façon générale en \(O({tailleGrillePrix}^n)\) pour une grille de prix de longueur \(tailleGrillePrix\) .

Cette solution n'est donc pas utilisable pratiquement, mais on constate une fois de plus que les sous-problèmes se chevauchent, on peut donc garder les résultats des sous-problèmes en mémoire pour améliorer cette situation. Appliquons la technique de mémoïsation :

Prix = [0, 1 ,5, 8, 9, 10, 17, 17, 20, 24, 30]

memo = {0: 0}    # Le revenu d'une tige de longueur 0 est 0
def R(n):
    if n in memo:  return memo[n]

    # Tableau des revenus max de toutes les découpes possibles de la grille de prix
    decoupes = [Prix[i] + R(n - i) for i in range(1, min(len(Prix), n + 1))]

    # On renvoie le plus grand revenu de toutes les découpes possibles
    memo[n] = max(decoupes)
    return memo[n]

L'ajout d'une variable globale dans la fonction permet de se convaincre facilement de l'effet sur la complexité temporelle :

cpt = 0
def R(n):
    global cpt
    cpt + = 1
    if n == 0: 
        #...

Alors que la première fonction, sans mémoïsation, s'appelle 1024 fois pour le calcul de R(10) et 1 043 456 fois pour R(20), la version avec mémoïsation s'appelle seulement 56 et 156 pour les mêmes calculs ! Mais cela se fait aux dépends de la complexité spatiale.

La version ascendante est une autre façon efficace de palier au problème de complexité temporelle :

Prix = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]

revenus = {0: 0}    # dictionnaire {longueur m :  revenu max pour une tige de longueur m}

def R(n):
    # On remplit le dictionnaire pour toutes les longueurs m allant de 1 à n
    for m in range(1, n + 1):

        # Tableau des revenus max de toutes les découpes possibles de m
        decoupes = [Prix[i] + revenus[m - i] for i in range(1, min(len(Prix), m + 1))]
        revenus[m] = max(decoupes)

    return revenus[n]          # On renvoie la valeur pour la clé correspondant à la longueur n

Ici, aucun soucis avec la complexité de la fonction (ni de limite de pile d'appels récursifs), la fonction s'exécute instantanément même avec de très grandes valeurs de n. En effet, la fonction fait une double boucle imbriquée, sur la longueur de la tige \(n\), et sur la longueur de la grille des prix. La complexité est donc simplement linéaire en \(O(n \times tailleGrillePrix)\), ou plus simplement en \(O(n)\) si on considère une grille de prix de petite taille.

Cette méthode a été introduite au début des années 1950 par Richard Bellman. Le terme "programmation" dans "programmation dynamique", ne doit pas s'entendre comme "utilisation d'un langage de programmation", mais comme synonyme de planification et ordonnancement. ↩
\(nb_i\) est donné par la formule de récurrence \(nb_i = \underset{p \leq i}{\min}⁡ (1+ nb_{i-p})\). ↩