La programmation dynamique
1
Programmation dynamique
C’est une des plus vieilles techniques pour produire des
algorithmes exacts plus efficaces que l’énumération exhaustive.
Programmation dynamique
C’est une des plus vieilles techniques pour produire des
algorithmes exacts plus efficaces que l’énumération exhaustive.
Principe (Bellman, 1949)
Composer une solution optimale du problème en combinant les
solutions (optimales) de ses sous-problèmes.
2
Programmation dynamique
C’est une des plus vieilles techniques pour produire des
algorithmes exacts plus efficaces que l’énumération exhaustive.
Principe (Bellman, 1949)
Composer une solution optimale du problème en combinant les
solutions (optimales) de ses sous-problèmes.
En pratique :
I Décomposer le problème en des sous-problèmes plus petits ;
I Calculer les solutions optimales de tous ces sous-problèmes et
les garder en mémoire.
I Calculer la solution optimale à partir des solutions optimales
des sous-problèmes
2
Plan
Suite de Fibonacci
version récursive
Version de la programmation dynamique
Un premier exemple : problème du stockage
Le plus court chemin dans un graphe
Récapitulatif
Codage des entiers
3
Plus précisément
Suite de Fibonacci
version récursive
Version de la programmation dynamique
4
Suite de Fibonacci
Données : Un entier t ∈ N
Objectif : Calculer le n-ième terme de la suite de Fibonacci
(F (0) = F (1) = 1, F (n) = F (n − 1) + F (n − 2)).
On peut le calculer en utilisant la récursivité
Suite de Fibonacci
Données : Un entier t ∈ N
Objectif : Calculer le n-ième terme de la suite de Fibonacci
(F (0) = F (1) = 1, F (n) = F (n − 1) + F (n − 2)).
On peut le calculer en utilisant la récursivité
fonction Fib(n)
1. si (n=0) ou (n=1) alors retourner 1 ;
2. sinon retourner Fib(n-1) + Fib(n-2) ;
Suite de Fibonacci
Données : Un entier t ∈ N
Objectif : Calculer le n-ième terme de la suite de Fibonacci
(F (0) = F (1) = 1, F (n) = F (n − 1) + F (n − 2)).
On peut le calculer en utilisant la récursivité
fonction Fib(n)
1. si (n=0) ou (n=1) alors retourner 1 ;
2. sinon retourner Fib(n-1) + Fib(n-2) ;
Fib(5)
Suite de Fibonacci
Données : Un entier t ∈ N
Objectif : Calculer le n-ième terme de la suite de Fibonacci
(F (0) = F (1) = 1, F (n) = F (n − 1) + F (n − 2)).
On peut le calculer en utilisant la récursivité
fonction Fib(n)
1. si (n=0) ou (n=1) alors retourner 1 ;
2. sinon retourner Fib(n-1) + Fib(n-2) ;
Fib(5)
Fib(4) Fib(3)
Suite de Fibonacci
Données : Un entier t ∈ N
Objectif : Calculer le n-ième terme de la suite de Fibonacci
(F (0) = F (1) = 1, F (n) = F (n − 1) + F (n − 2)).
On peut le calculer en utilisant la récursivité
fonction Fib(n)
1. si (n=0) ou (n=1) alors retourner 1 ;
2. sinon retourner Fib(n-1) + Fib(n-2) ;
Fib(5)
Fib(4) Fib(3)
Fib(3) Fib(2)
Suite de Fibonacci
Données : Un entier t ∈ N
Objectif : Calculer le n-ième terme de la suite de Fibonacci
(F (0) = F (1) = 1, F (n) = F (n − 1) + F (n − 2)).
On peut le calculer en utilisant la récursivité
fonction Fib(n)
1. si (n=0) ou (n=1) alors retourner 1 ;
2. sinon retourner Fib(n-1) + Fib(n-2) ;
Fib(5)
Fib(4) Fib(3)
Fib(3) Fib(2)
Fib(2) Fib(1)
Fib(1) Fib(0)
Suite de Fibonacci
Données : Un entier t ∈ N
Objectif : Calculer le n-ième terme de la suite de Fibonacci
(F (0) = F (1) = 1, F (n) = F (n − 1) + F (n − 2)).
On peut le calculer en utilisant la récursivité
fonction Fib(n)
1. si (n=0) ou (n=1) alors retourner 1 ;
2. sinon retourner Fib(n-1) + Fib(n-2) ;
Fib(5)
Fib(4) Fib(3)
Fib(3) Fib(2) Fib(2) Fib(1)
Fib(2) Fib(1) Fib(1) Fib(0) Fib(1) Fib(0)
Fib(1) Fib(0)
Suite de Fibonacci
Données : Un entier t ∈ N
Objectif : Calculer le n-ième terme de la suite de Fibonacci
(F (0) = F (1) = 1, F (n) = F (n − 1) + F (n − 2)).
On peut le calculer en utilisant la récursivité
fonction Fib(n)
1. si (n=0) ou (n=1) alors retourner 1 ;
2. sinon retourner Fib(n-1) + Fib(n-2) ;
Fib(5)
Fib(4) Fib(3)
Fib(3) Fib(2) Fib(2) Fib(1)
Fib(2) Fib(1) Fib(1) Fib(0) Fib(1) Fib(0)
Fib(1) Fib(0)
√
nb exponentiel d’appels récursifs : O(φn ) avec φ = (1 + 5)/2.
Plus précisément
Suite de Fibonacci
version récursive
Version de la programmation dynamique
6
Suite de Fibonacci
Données : Un entier t ∈ N
Objectif : Calculer le n-ième terme de la suite de Fibonacci
(F (0) = F (1) = 1, F (n) = F (n − 1) + F (n − 2)).
On peut le calculer en utilisant la programmation dynamique :
7
Suite de Fibonacci
Données : Un entier t ∈ N
Objectif : Calculer le n-ième terme de la suite de Fibonacci
(F (0) = F (1) = 1, F (n) = F (n − 1) + F (n − 2)).
On peut le calculer en utilisant la programmation dynamique :
fonction Fib-Dynamique (n)
1. F[0]=1 ; F[1]=1
2. pour i allant de 3 à n, faire F[i]=F[i-1] + F[i-2] ;
3. retourner F [n]
n
F [n]
Suite de Fibonacci
Données : Un entier t ∈ N
Objectif : Calculer le n-ième terme de la suite de Fibonacci
(F (0) = F (1) = 1, F (n) = F (n − 1) + F (n − 2)).
On peut le calculer en utilisant la programmation dynamique :
fonction Fib-Dynamique (n)
1. F[0]=1 ; F[1]=1
2. pour i allant de 3 à n, faire F[i]=F[i-1] + F[i-2] ;
3. retourner F [n]
n 0 1
F [n] 1 1
Suite de Fibonacci
Données : Un entier t ∈ N
Objectif : Calculer le n-ième terme de la suite de Fibonacci
(F (0) = F (1) = 1, F (n) = F (n − 1) + F (n − 2)).
On peut le calculer en utilisant la programmation dynamique :
fonction Fib-Dynamique (n)
1. F[0]=1 ; F[1]=1
2. pour i allant de 3 à n, faire F[i]=F[i-1] + F[i-2] ;
3. retourner F [n]
n 0 1 2
F [n] 1 1 2
Suite de Fibonacci
Données : Un entier t ∈ N
Objectif : Calculer le n-ième terme de la suite de Fibonacci
(F (0) = F (1) = 1, F (n) = F (n − 1) + F (n − 2)).
On peut le calculer en utilisant la programmation dynamique :
fonction Fib-Dynamique (n)
1. F[0]=1 ; F[1]=1
2. pour i allant de 3 à n, faire F[i]=F[i-1] + F[i-2] ;
3. retourner F [n]
n 0 1 2 3
F [n] 1 1 2 3
Suite de Fibonacci
Données : Un entier t ∈ N
Objectif : Calculer le n-ième terme de la suite de Fibonacci
(F (0) = F (1) = 1, F (n) = F (n − 1) + F (n − 2)).
On peut le calculer en utilisant la programmation dynamique :
fonction Fib-Dynamique (n)
1. F[0]=1 ; F[1]=1
2. pour i allant de 3 à n, faire F[i]=F[i-1] + F[i-2] ;
3. retourner F [n]
n 0 1 2 3 4
F [n] 1 1 2 3 5
Suite de Fibonacci
Données : Un entier t ∈ N
Objectif : Calculer le n-ième terme de la suite de Fibonacci
(F (0) = F (1) = 1, F (n) = F (n − 1) + F (n − 2)).
On peut le calculer en utilisant la programmation dynamique :
fonction Fib-Dynamique (n)
1. F[0]=1 ; F[1]=1
2. pour i allant de 3 à n, faire F[i]=F[i-1] + F[i-2] ;
3. retourner F [n]
n 0 1 2 3 4 5 ...
F [n] 1 1 2 3 5 7 ...
Suite de Fibonacci
Données : Un entier t ∈ N
Objectif : Calculer le n-ième terme de la suite de Fibonacci
(F (0) = F (1) = 1, F (n) = F (n − 1) + F (n − 2)).
On peut le calculer en utilisant la programmation dynamique :
fonction Fib-Dynamique (n)
1. F[0]=1 ; F[1]=1
2. pour i allant de 3 à n, faire F[i]=F[i-1] + F[i-2] ;
3. retourner F [n]
n 0 1 2 3 4 5 ...
F [n] 1 1 2 3 5 7 ...
Complexité : n additions
Plan
Suite de Fibonacci
version récursive
Version de la programmation dynamique
Un premier exemple : problème du stockage
Le plus court chemin dans un graphe
Récapitulatif
Codage des entiers
8
Un premier exemple : problème du stockage.
Considérons n programmes P1 , P2 , . . . , Pn qui peuvent être stockés
sur un disque dur de capacité D gigabytes.
Chaque programme Pi a besoin si gigabytes pour être stocké.
Tous les programmes ne peuvent pas être stockés sur le
Xn
disque : ( si > D)
i=1
Objectif :
Concevoir un algorithme qui permet de maximiser la quantité
de données stockées sur le disque.
9
Formulation sous-forme de problème d’optimisation
Données :
P un ensemble fini de programmes : P = {P1 , P2 , . . . , Pn }
v une valuation des éléments de P : v (Pi ) = si
Un entier D.
Solutions faisables :
Une solution faisable S est une partie de P telle que
X
v (S) = v (e) ≤ D
e∈S
Notons F l’ensemble des solutions faisables.
Objectif : Trouver S ∈ F qui maximise la quantité v (S)
10
Les algorithmes gloutons ne fonctionnent pas
1. Classer les programmes P1 , P2 , . . . , Pn en fonction de la taille
du programme si : s1 ≥ s2 ≥ · · · ≥ sn
2. Initialiser la recherche avec S = ∅
3. Pour i = X 1 à n faire :
Si sj + si ≤ D alors S ← S ∪ {Pi }
Pj ∈S
4. Retourner S
11
Les algorithmes gloutons ne fonctionnent pas
1. Classer les programmes P1 , P2 , . . . , Pn en fonction de la taille
du programme si : s1 ≥ s2 ≥ · · · ≥ sn
2. Initialiser la recherche avec S = ∅
3. Pour i = X 1 à n faire :
Si sj + si ≤ D alors S ← S ∪ {Pi }
Pj ∈S
4. Retourner S
Exemple : Considérons qu’on dispose 4 programmes de tailles 7, 5,
4, 1, et un disque dur de capacité D = 10.
L’algorithme retourne S = {P1 , P4 }
alors que la solution optimale est {P2 , P3 , P4 }.
11
Algorithme « force brute »
Toutes les solutions sont des parties de l’ens. des programmes.
Le nombre de solutions est au plus 2|P| .
L’algorithme « force brute » est l’algorithme suivant :
1. pour toute partie S de l’ensemble P
1.1 tester si S est une solution faisable
1.2 Si oui, conserver S si
v (S) = max{v (S 0 ) : S 0 solution déjà testée }
2. retourner la solution conservée ;
La complexité de l’algorithme « force brute » est en O(2|P| )
opérations.
12
Exemple
Considérons l’exemple où 4 programmes sont de tailles 4, 7, 1, 5 et
où D = 10.
Pour les deux solutions S1 = {5} et S1 = {1, 4}, la quantité
des données stockées est identique.
13
Exemple
Considérons l’exemple où 4 programmes sont de tailles 4, 7, 1, 5 et
où D = 10.
Pour les deux solutions S1 = {5} et S1 = {1, 4}, la quantité
des données stockées est identique.
S[q] : ensemble des solutions faisables S telles que v (S) = q
q 0 1 2 3 4 5 6 7 8 9 10
S[q] ∅
Les ensembles {7, 5}, {7, 4} . . . ne sont pas des solutions
faisables.
13
Exemple
Considérons l’exemple où 4 programmes sont de tailles 4, 7, 1, 5 et
où D = 10.
Pour les deux solutions S1 = {5} et S1 = {1, 4}, la quantité
des données stockées est identique.
S[q] : ensemble des solutions faisables S telles que v (S) = q
q 0 1 2 3 4 5 6 7 8 9 10
S[q] ∅ {1}
Les ensembles {7, 5}, {7, 4} . . . ne sont pas des solutions
faisables.
13
Exemple
Considérons l’exemple où 4 programmes sont de tailles 4, 7, 1, 5 et
où D = 10.
Pour les deux solutions S1 = {5} et S1 = {1, 4}, la quantité
des données stockées est identique.
S[q] : ensemble des solutions faisables S telles que v (S) = q
q 0 1 2 3 4 5 6 7 8 9 10
S[q] ∅ {1} {4}
Les ensembles {7, 5}, {7, 4} . . . ne sont pas des solutions
faisables.
13
Exemple
Considérons l’exemple où 4 programmes sont de tailles 4, 7, 1, 5 et
où D = 10.
Pour les deux solutions S1 = {5} et S1 = {1, 4}, la quantité
des données stockées est identique.
S[q] : ensemble des solutions faisables S telles que v (S) = q
q 0 1 2 3 4 5 6 7 8 9 10
S[q] ∅ {1} {4} {5} et
{4, 1}
Les ensembles {7, 5}, {7, 4} . . . ne sont pas des solutions
faisables.
13
Exemple
Considérons l’exemple où 4 programmes sont de tailles 4, 7, 1, 5 et
où D = 10.
Pour les deux solutions S1 = {5} et S1 = {1, 4}, la quantité
des données stockées est identique.
S[q] : ensemble des solutions faisables S telles que v (S) = q
q 0 1 2 3 4 5 6 7 8 9 10
S[q] ∅ {1} {4} {5} et {5, 1}
{4, 1}
Les ensembles {7, 5}, {7, 4} . . . ne sont pas des solutions
faisables.
13
Exemple
Considérons l’exemple où 4 programmes sont de tailles 4, 7, 1, 5 et
où D = 10.
Pour les deux solutions S1 = {5} et S1 = {1, 4}, la quantité
des données stockées est identique.
S[q] : ensemble des solutions faisables S telles que v (S) = q
q 0 1 2 3 4 5 6 7 8 9 10
S[q] ∅ {1} {4} {5} et {5, 1} {7} {7, 1} {5, 4} {5, 4, 1}
{4, 1}
Les ensembles {7, 5}, {7, 4} . . . ne sont pas des solutions
faisables.
13
Concept
L’algorithme proposé est basé sur concept de la programmation
dynamique.
Concept
L’algorithme proposé est basé sur concept de la programmation
dynamique.
Décomposer le problème en des sous-problèmes plus petits ;
I Pour cela, on va résoudre dans cet ordre les problèmes
• P1 = {4}, P2 = {4, 7}, P3 = {4, 7, 1}, P3 = {4, 7, 1, 5},
14
Concept
L’algorithme proposé est basé sur concept de la programmation
dynamique.
Décomposer le problème en des sous-problèmes plus petits ;
Considérer les problèmes Pi = {s1 , . . . , si }, i = 1, . . . , |P|
Concept
L’algorithme proposé est basé sur concept de la programmation
dynamique.
Décomposer le problème en des sous-problèmes plus petits ;
Considérer les problèmes Pi = {s1 , . . . , si }, i = 1, . . . , |P|
Calculer les solutions faisables de tous ces sous-problèmes.
Pour le sous-problème P1 = {4},
q 0 1 2 3 4 5 6 7 8 9 10
∅ {4}
Pour le sous-problème P2 = {4, 7},
q 0 1 2 3 4 5 6 7 8 9 10
∅ {4} {7}
Pour le sous-problème P3 = {4, 7, 1},
q 0 1 2 3 4 5 6 7 8 9 10
∅ {1} {4} {4, 1} {7} {7, 1}
Concept
L’algorithme proposé est basé sur concept de la programmation
dynamique.
Décomposer le problème en des sous-problèmes plus petits ;
Considérer les problèmes Pi = {s1 , . . . , si }, i = 1, . . . , |P|
Calculer les solutions faisables de tous ces sous-problèmes.
Calculer les tableaux Ti qui stockent
toutes les solutions faisables de Pi .
14
Concept
L’algorithme proposé est basé sur concept de la programmation
dynamique.
Décomposer le problème en des sous-problèmes plus petits ;
Considérer les problèmes Pi = {s1 , . . . , si }, i = 1, . . . , |P|
Calculer les solutions faisables de tous ces sous-problèmes.
Calculer les tableaux Ti qui stockent
toutes les solutions faisables de Pi .
Calculer les solutions faisables à partir des solutions faisables des
sous-problèmes
Trouver la relation entre les tableaux Ti et Ti+1
14
Principe et Notation
Ti : le tableau des sommes distinctes de tous les
sous-ensembles de Pi = {s1 , . . . , si }.
Ti [j] = 1 si et seulement si il existe une solution faisable S
telle que v (S) = j.
I Pour le sous-problème P3 = {4, 7, 1},
q 0 1 2 3 4 5 6 7 8 9 10
T3 [q] 1 1 0 0 1 1 0 1 1 0 0
∅ {1} {4} {4, 1} {7} {7, 1}
Si le problème Pi a une solution faisable S alors le problème
Pi+1 a
I la solution faisable S
I et aussi la solution faisable S ∪ {si+1 } si v (S) + v (si+1 ) ≤ D.
15
Algorithme dynamique
P : un ens. de programmes : P = {P1 , P2 , . . . , Pn }
Entrée : v : une valuation des éléments de P, v (Pi ) = si
D : Un entier
Sortie : un entier
1. pour j allant de 1 à D faire T0 [j] ← 0
2. T0 [0] ← 1 // la solution S = ∅ est une solution faisable
3. pour i allant de 1 à |P| faire
3.1 pour j allant de 1 à D faire
Ti [j] ← 1
3.1.1 si Ti−1 [j] == 1 alors
Ti [j + si ] ← 1 : si j + si ≤ D
4. retourner la plus grande valeur j telle que Tn [j] == 1
Algorithme dynamique
P : un ens. de programmes : P = {P1 , P2 , . . . , Pn }
Entrée : v : une valuation des éléments de P, v (Pi ) = si
D : Un entier
Sortie : un entier
1. pour j allant de 1 à D faire T0 [j] ← 0
2. T0 [0] ← 1 // la solution S = ∅ est une solution faisable
3. pour i allant de 1 à |P| faire
3.1 pour j allant de 1 à D faire
Ti [j] ← 1
3.1.1 si Ti−1 [j] == 1 alors
Ti [j + si ] ← 1 : si j + si ≤ D
4. retourner la plus grande valeur j telle que Tn [j] == 1
Complexité : O(D · |P|)
16
Remarque : Construction de la solution.
On peut construire en même temps la solution.
Ti un ens. de tableaux :
P : un ens. de programmes : P = {P1 , P2 , . . . , Pn }
Entrée :
v : une valuation des éléments de P, v (Pi ) = si
D : Un entier
Sortie : un ensemble d’entiers S
1. Trouver la valeur j telle que j = argmax{k : T|P| [k] = 1}
2. S → ∅
3. pour i allant de |P| à 1 faire
S ← S ∪ {si };
3.1 Si Ti−1 [j − v (si )] == 1 alors
j ← j − v (si );
4. retourner S
Plan
Suite de Fibonacci
version récursive
Version de la programmation dynamique
Un premier exemple : problème du stockage
Le plus court chemin dans un graphe
Récapitulatif
Codage des entiers
18
Plus court chemin dans un graphe
Données :
G = (V , E ) : un graphe orienté où chaque arc possède une
longueur non-négative.
Objectif : Calculer la longueur plus court chemin entre toutes
les paires de sommets.
Notation : On suppose que
V = {1, . . . , n}.
G est donné sous forme de matrice L[1...n, 1...n] :
I s’il n’y a pas d’arc allant de i à j, alors L[i, j] = ∞
I sinon L[i, j] correspond à la longueur de l’arc (i, j)
19
Principe
L’algorithme de Floyd-Warshall construit une matrice Dn qui donne
la longueur du plus court chemin entre chaque paire de sommets.
1. On initialise D0 à L ;
2. Après l’itération k, Dk donne la longueur du plus court
chemin lorsque l’on utilise que les sommets dans {1, . . . , k}
comme sommets intermédiaires (ou éventuellement aucun
sommet intermédiaire).
Définition : Dk est la matrice D après l’itération k.
20
Récurrence
Dk [i, j] = min(Dk−1 [i, j], Dk−1 [i, k] + Dk−1 [k, j])
Dans une séquence optimale de décisions, ou de choix,
chaque sous-séquence doit aussi être optimale.
En effet, si (1, 4), (4, 2) est le chemin le plus court entre 1 et
2, alors
(1, 4) est le chemin le plus court entre 1 et 4
et (4, 2) est le chemin le plus court entre 4 et 2.
Remarque : cela ne marche pas pour les chemins les plus
longs.
21
Algorithme de Floyd-Warshall
Entrée : L, la matrice du graphe G où L[i, j] correspond à la
longueur de l’arc (i, j).
Sortie : une matrice n × n
D0 ← L ;
Pour k allant de 1 à n faire
I Pour i allant de 1 à n faire
• Pour j allant de 1 à n faire
Dk [i, j] ← min(Dk−1 [i, j], Dk−1 [i, k] + Dk−1 [k, j])
Retourner Dn .
Complexité : O(n3 ) opérations
22
Plan
Suite de Fibonacci
version récursive
Version de la programmation dynamique
Un premier exemple : problème du stockage
Le plus court chemin dans un graphe
Récapitulatif
Codage des entiers
23
Récapitulatif
Calcul de la suite de Fibonacci
I Version récursive : O(φn ) opérations
I Programmation dynamique : O(n) opérations
Problème du stockage.
I Algorithme « force brute » : O(2|P| ) opérations
I Programmation dynamique : O(D · |P|) opérations
Le plus court chemin dans un graphe
I Programmation dynamique : O(n3 ) opérations
24
Plan
Suite de Fibonacci
version récursive
Version de la programmation dynamique
Un premier exemple : problème du stockage
Le plus court chemin dans un graphe
Récapitulatif
Codage des entiers
25
Remarque : Codage des entiers
Pour coder les données des instances du problème du
stockage,
Données :
P : un ensemble fini de programmes. ;
v : une valuation des éléments de P ;
D : un entier.
on a besoin de coder (n + 1) entiers.
En informatique, les données (les entiers) sont codées par des
0 et des 1.
Combien faut-il de « bits » pour coder un entier i ?
26
Remarque : Codage des entiers
Un entier i s’écrit en base b en utilisant des b chiffres allant
de 0 à b − 1 :
i s’écrit cn ...c2 c1 c0 en base b ssi i = cn bn + ... + c2 b2 + c1 b1 + c0 b0
Par exemple :
I 2406 = 2 · 103 + 4 · 102 + 0 · 101 + 6 · 100 (en base 10)
I 1001 = 1 · 23 + 0 · 22 + 0 · 21 + 1 · 20 (en base 2)
Un entier i entre 0 et bn − 1 peut être coder en n chiffres, ou
en
I dlogb (i + 1)e chiffres
I dlog2 (i + 1)e bits si b = 2
On peut le prouver par récurrence.
27
Le problème du stockage
L’instance du problème est codé avec
O((n + 1)D) bits si l’entier en codé en unaire,
O((n + 1)log2 D) bits si l’entier en codé en unaire,
L’algorithme basé sur la programmation dynamique se réalise en
O(D · |P|) opérations, c’est-à-dire
en temps polynomial si l’entier en codé en unaire
en temps exponentiel si l’entier en codé en binaire
car O(D) = O(2log2 D )
Remarque : l’algorithme s’exécute en temps polynomial si les
entiers sont « petits ».
28
Aujourd’hui
Programmation dynamique
Exemples : Suite de Fibonacci, problème du stockage, Le plus
court chemin dans un graphe
Le codage des entiers
La semaine prochaine :
introduction à la complexité et à la définition de problèmes
difficiles.
29
