P LAN
P ROGRAMMATION DYNAMIQUE
Walter A PPEL 1 U N EXEMPLE ( PRESQUE ) TRIVIAL
2 U N DEUXIÈME EXEMPLE
WALTER A PPEL P ROGRAMMATION DYNAMIQUE 1 / 13 WALTER A PPEL P ROGRAMMATION DYNAMIQUE 2 / 13
LA SUITE DE F IBONACCI C HEVAUCHEMENT DES SOUS - PROBLÈMES
Définissons la suite de Fibonacci par def fibo(n):
if n == 0 or n == 1:
F0 = 1
return 1
F1 = 1 else:
F
n+2 = Fn+1 + Fn ∀n ⩾ 0 return fibo(n-1) + fibo(n-2)
4 3
3 2 2 1
2 1 1 0 1 0
1 0
WALTER A PPEL P ROGRAMMATION DYNAMIQUE 4 / 13 WALTER A PPEL P ROGRAMMATION DYNAMIQUE 5 / 13
M ÉMOÏSATION M ÉMOÏSATION
On utilise une mise en mémoire des résultats : Dans le même esprit, on peut utiliser une fonction récursive
L = [ 0 , 1 ] + [ None ] * 200 # L est définie globalement auxiliaire :
def fibmem(n)
def fibo_m ( n ) : L = [1, 1] + [None] * (n-1)
i f L [ n ] == None : # Fn n’a pas été calculé # La taille est adaptée au problème
L [ n ] = fibo_m ( n−1) + fibo_m ( n−2) def fifi(k)
return L[ n ] # Dans tous les cas if L[k] == None:
L[k] = fifi(k-1) + fifi(k-2)
return L[k]
Python n’arrive pas à calculer fibo(50)... mais effectue return fifi(n)
fibmem(100) en une fraction de seconde.
Ennui : on effectue 499 calculs à l’appel fibmem(500)... puis
500 à l’appel de fibmem(501).
Ennui : et si on veut fibo(250) ?
WALTER A PPEL P ROGRAMMATION DYNAMIQUE 6 / 13 WALTER A PPEL P ROGRAMMATION DYNAMIQUE 7 / 13
M ÉMOÏSATION AVEC DICTIONNAIRE (1) M ÉMOÏSATION AVEC DICTIONNAIRE (2)
Un dictionnaire peut s’avérer utile car on peut ajouter un
def Fibo2(n):
élément d’indice quelconque → souplesse.
mem = {0: 1, 1: 1}
def Fibo(n, mem = {0: 1, 1: 1}): def fibo_mem(k):
# Le dictionnaire local mem reste en variable if not(k in mem):
# locale, et est conservé lors des appels récursifs a = fibo_mem(k - 1) + fibo_mem(k - 2)
if n in mem: mem[k] = a
return mem[n] return mem[k]
else: return fibo_mem(n)
a = Fibo(n - 1) + Fibo(n - 2) Ici, le dictionnaire ainsi qu’une fonction auxiliaire sont
mem[n] = a
utilisés comme variable locale. Le dictionnaire est recalculé
return a
(localement) dans fibo_mem, mais entièrement à chaque
Une fois qu’on a calculé Fibo(10), la variable locale mem appel de fibo2.
contient 11 éléments. Quand on a calculé Fibo(200), elle en
contient 201 — et calculer Fibo(100) est immédiat.
WALTER A PPEL P ROGRAMMATION DYNAMIQUE 8 / 13 WALTER A PPEL P ROGRAMMATION DYNAMIQUE 9 / 13
UN CHEMIN MAXIMAL À chaque case x de la pyramide, on calcule la valeur m(x)
du meilleur chemin partant de la base et arrivant en x.
Dans une pyramide de nombres, en partant de la base, et en
Pour un sommet x à la base, m(x) = v(x).
se dirigeant vers le sommet à chaque étape, on cherche à
maximiser le total des nombres traversés. Pour un sommet d’une ligne plus élevée,
3 m(x) = v(x) + max m(xg ), m(xd ) ,
7 4
2 4 6 où l’on a noté
9 5 9 3 x
xg xd
Z Si l’on connaît un chemin optimal, alors le sous-chemin
obtenu en en tronquant la fin est encore optimal. 3 23
7 4 20 19
2 4 6 11 13 5
9 5 9 3 9 5 9 3
Ainsi, le meilleur chemin a un score de 23.
WALTER A PPEL P ROGRAMMATION DYNAMIQUE 11 / 13 WALTER A PPEL P ROGRAMMATION DYNAMIQUE 12 / 13
P RINCIPE D ’ OPTIMALITÉ
Les raisonnements de « programmation dynamique » ont lieu
lorsque l’on a
Un principe d’optimalité
« si une solution est optimale à partir d’un état initial,
alors le raisonnement obtenu à partir du résultat de la
première décision est encore minimal. »
Un recouvrement des sous-problèmes empêchant la mise
en œuvre directe et brutale d’une récursion.
Très souvent, il est possible de raisonner :
de bas en haut, en remplissant itérativement un tableau
selon des contraintes de préséance ;
de haut en bas, en procédant récursivement, avec
mémoïsation.
WALTER A PPEL P ROGRAMMATION DYNAMIQUE 13 / 13
