Program Dynamique PDF

Programmation
dynamique
Ahlem Ben Cherifa
-FST-
Programmation dynamique
• Programmation dynamique inventée par Bellman (~ 1954)
pour résoudre des pbs de chemins optimaux (longueur
max. ou min.)
• La programmation dynamique est une méthode de
construction d’algorithme très utilisée en optimisation
combinatoire (→ recherche de solution optimale dans un
ensemble fini de solutions mais très grand).
• Il s’agit d’une méthode d’énumération implicite : on retient
ou rejette des sous-ensembles de solutions mais on ne
construit pas toutes les solutions. On rejette certaines
solutions sans les avoir construites explicitement si elles
appartiennent à un sous-ensemble qui n’est pas
intéressant.
Programmation dynamique
Diviser-pour-régner:
1) on décompose un problème en sous-problèmes pertinents (dont la
taille est une fraction de celle de départ),
2) on résout les sous-problèmes,
3) on construit une solution pour le problème initial…
Approche “top-down”
Programmation dynamique:
1) on résout des sous-problèmes et on stocke leurs solutions,
2) on voit quels sous-problèmes sont pertinents et
3) on les utilise pour construire une solution pour le problème initial…
Approche “bottom-up”
Exemple : la suite de Fibonacci
F0=1 F1=1 Fn = Fn-1 + Fn-2
fib(n) = Si n=0 ou n=1 alors 1

sinon fib(n-1)+fib(n-2)
“top-down”
Exemple : la suite de Fibonacci
F0=1 F1=1 Fn = Fn-1 + Fn-2
fib(n) :
T [0]:=1
T [1]:=1
pour i de 2 à n
T[i]:=T[i-1]+T[i-2]
fpour
fib := T[n]
“bottom-up”
Comparaison avec diviser-pour-régner
• Diviser-pour-régner divise le problème en sous-problèmes
indépendants, résout-les et combine les solution en une
solution du problème de départ
• Diviser-pour-régner est une approche top-down
• Programmation dynamique calcule des solutions de petits
sous-problèmes pour les combiner en une solution d’un
problème plus grand. C’est donc une approche bottom-up.
• Contrairement à Diviser-pour-régner, les sous-problèmes sont
dépendants
• Principe d’optimalité : solution optimale d’un problème
contient des solutions optimales de tous les sous-problèmes
• Il reste de trouver une décomposition en sous-problèmes
• Les solutions des sous-problèmes sont mémorisées dans un tableau
Le problème du sac à dos
Le problème:
Input: un poids maximal M (entier), un ensemble de N objets
ayant chacun un poids et une valeur
Output: la valeur maximale pouvant être stockée dans le
sac (sans dépasser sa capacité !).
Trouver x1, x2, . . . , xN ϵ {0, 1} tels que :

• Σ xi * pi ≤ M, et 1≤i≤N
• Σ xi * vi est maximal
Exemple : i 1 2 3 4 5
p 1 2 5 6 7
Capacité du sac M = 11 v 1 6 18 22 28
i
Solutions :
{5, 2, 1} a un poids 10 et une valeur 35
{3, 4} a un poids 11 et une valeur 40
• soit F(k,m), 0 ≤ k ≤ n et 0 ≤ m ≤ M, le bénéfice
maximum qu’on peut obtenir avec les objets
1,. . . ,k et un sac de charge maximale m
• Deux cas :
 On ne sélectionne pas l’objet k : F(k,m) est le bénéfice maximum en
sélectionnant parmi les k − 1 premiers objets avec comme limite m
(F(k − 1,m))
 On sélectionne l’objet k : F(k,m) est la valeur de
l’objet k plus le bénéfice maximum en
sélectionnant parmi les k − 1 premiers objets
avec la limite m − pk
0 si i=0
F(k,m) = F(k-1,m) si pi > m
Max( F(k-1,m) , F(k-1,m-pk)+ vk sinon
0 si i=0
F(k,m) = F(k-1,m) si pi > m
i 1 2 3 4 5
Max( F(k-1,m) , F(k-1,m-pk)+ vk
sinon pi 1 2 5 6 7
vi 1 6 18 22 28
M 0 1 2 3 4 5 6 7 8 9 10 11
Ø 0 0 0 0 0 0 0 0 0 0 0 0
{1} 0 1 1 1 1 1 1 1 1 1 1 1
{1,2} 0 1 6 7 7 7 7 7 7 7 7 7
{1,2,3] 0 1 6 7 7 18 19 24 25 25 25 25
{1,2,3,4} 0 1 6 7 7 18 22 24 28 29 29 40
{1,2,3,4,5} 0 1 6 7 7 18 22 28 29 34 35 40
Solution optimale : {4, 3} Bénéfice : 22 + 18 = 40

KnapSack(P, V, N, M) : entier
Var F : tableau[0 . . N, 0 . .M] d’entier
Début
pour m de 1 à M faire
F[0,m]:=0
fpour
pour k de 1 à N faier
F[k, 0] := 0
fpour
pour k de 1 à N faire
pour m de 1 à M faire
Si P[k] > m
alors F[k,m] := F[k − 1,m]
sinon Si F[k − 1,m] > V[k] + F[k − 1,m − P[k]]
alors F[k,m] := F[k − 1,m]
sinon F[k,m] := v[k] + F[k − 1,m − P[k]]
fsi
fsi
fpour
fpour
KnapSack := F[N,M]
Fin
• Récupération des xi
• En remontant dans le tableau F :
X : tableau[1. . N] de booléen
KnapSack(P, V, N, M,X) : entier
Var F : tableau[0 . . N, 0 . .M] d’entier
Début
// Calculer F
...
// Récupérer la solution
m := M
pour k de N à 1 pas(-1) faire
si F[k,m] = F[k − 1,m]
alors x[k] := 0
sinon x[k] := 1
m := m − p[k]
fsi
fpour
Fin
Rod Cutting
 Soit une tige d’acier qu’on découpe pour la vendre morceau

par morceau
 La découpe ne peut se faire que par nombre entier de centimètre
 Le prix de vente d’une tige dépend (non linéairement) de sa longueur
 On veut déterminer le revenu maximum qu’on peut attendre de la
vente d’une tige de n centimètre
Problème algorithmique :
 Entrée : une longueur n > 0 et une table de prix pi, pour i = 1, 2,..., n
 Sortie : Le revenu maximum qu’on peut obtenir pour des tiges de

longueur n
Rod Cutting
Illustration:
 Soit la table de prix :
Longueur i 1 2 3 4 5 6 7 8 9 10
Prix pi 1 5 8 9 10 17 17 20 24 30
 Découpes possibles d’une tige de longueur n=4
9 1 8 5 5
8 1 1 1 5 1 5 1
5 1 1 1 1 1 1
Approche par force brute
 Enumérer toutes les découpes, calculer leur
revenu, déterminer le revenu maximum
 Complexité : exponentielle en n :
Il y a 2n-1 manières de découper une tige de
longueur n
Plusieurs découpes sont équivalentes (1+1+2 et
1+2+1 par exemple) mais même en prenant cela
en compte, le nombre de découpes reste
exponentiel
 Infaisable pour n un peu grand
Idée:
 Soit ri le revenu maximum pour une tige de longueur i
 Peut-on formuler rn de manière récursive ?
 Déterminons ri pour notre exemple :
i ri solution optimale
1 1 1 (pas de découpe)
4 10 2+2
5 13 2+3
7 18 1+6 ou 2+2+3
8 22 2+6 . . .
Formulation récursive de rn : version naïve
 rn peut être calculé comme le maximum de :
 pn : le prix sans découpe
 r1 + rn-1 : le revenu max pour une tige de 1 et une
tige de n – 1
 r2 + rn-2 : le revenu max pour une tige de 2 et une
tige de n – 2
 ...
 rn-1 + r1
 C’est à dire
rn = max(pn,r1 + rn-1,r2 + rn-2,...,rn-1 + r1)
Rod Cutting
Exemple:
Longueur i 1 2 3 4 5 6 7 8 9 10
Prix pi 1 5 8 9 10 17 17 20 24 30
Formule de récurrence :
r0 = 0
rn = max (pi + rn-i) 1≤ i ≤ n
Soit n = 8
i 0 1 2 3 4 5 6 7 8
p[i] 0 1 5 8 9 10 17 17 20
r[i] 0 1 5 8 10 13 17 18 22
s[i] 0 1 2 3 2 2 6 1 2
La solution est une découpe en 2 + 6 pour un gain de 22.

Solution par programmation dynamique:
Approche ascendante :
Principe : résoudre les sous-problèmes par taille
en commençant d’abord par les plus petits.
Cut-rod(p, n) : entier
R : tableau[0 . . n] d’entier
S : tableau[0 . . n] d’entier
Début
r[0] := 0
S[0] := 0
pour j de 1 à n faire
q := -∞
pour i de 1 à j
Si q < p[i] + R[j – i]
alors q := p[i] + R[j – i]
S[j] := i
fsi
fpour
R[j] := q
Fpour
//reconstructuion de la solution
i := n
Tant que i > 0 faire
ecrire ( S[i] )
i := i – S[i]
fait
Cut-rod := R[n]
UN AUTRE EXEMPLE: LA PLUS LONGUE SOUS-
SUITE COMMUNE
Le problème:
Une sous-suite d’un mot u est un mot w obtenu à partir de u
en effaçant des lettres:
aac est sous-suite de arracher, de avancer, de hamac...
Soient deux mots u et v. On cherche la longueur de la plus longue

sous-suite commune des deux mots ainsi qu’une telle sous-suite.
On notera lcs(u, v) cette longueur.
Par exemple, si u = acc et v = archi, ac est la sous-suite de longueur

maximale et donc lcs(u, v) vaut 2.
UN AUTRE EXEMPLE: LA PLUS LONGUE SOUS-
SUITE COMMUNE
Analyse du problème:
 Notons LCS(i, j) la longueur maximale d’une
sous-suite des mots u1..ui ( les i premières lettres
de u) et v1..vj ( les j premières lettres de v).
 On a donc:
 Les cas de base: LCS(i, 0) = 0 = LCS(0, j)
 la récurrence:
si ui = vj , LCS(i, j) = 1 + LCS(i − 1, j − 1)
si ui ≠ vj , LCS(i, j) = max(LCS(i − 1, j), LCS(i, j − 1))
Version récursive naïve
LCS( i, j) : entier
Si (i=0) alors LCS := 0
Sinon Si (j=0) alors LCS := 0
Sinon Si (u[ i ]= v[ j ])
alors LCS := 1+LCS(i-1, j-1)
sinon LCS := max (LCS(i-1,j), LCS(i, j-1))
fsi
fsi
fsi
Le nombre d’appels différents est au plus
longueur(u) ∗ longueur(v)
On est dans le cadre de la programmation dynamique!
Solution par la programmation dynamique
• Etant données les deux chaînes suivantes :
U = abcbdab et V = bdcaba,
construire, en utilisant la formule de récurrence
précédente, la PLSC.
j 0 1 2 3 4 5 6
i vj b d c a b a
0 ui 0 0 0 0 0 0 0
1 a 0 0 0 0 1 1 1
2 b 0 1 1 1 1 2 2
3 c 0 1 1 2 2 2 2
4 b 0 1 1 2 2 3 3
5 d 0 1 2 2 2 3 3
PLSC = bcba 6 a 0 1 2 2 3 3 4
7 b 0 1 2 2 3 4 4
LCS( u , v , n , m ) : entier // n = long(u) ; m = long(v)
T : tableau[0..n , 0..m] d’entier
//T[i,j] mémorisera LCS(u[0..i-1],v[0,..j-1])
//cas de base:
pour i de 0 n faire T[i,0] := 0 fpour
pour i de 0 m faire T[0,i] := 0 fpour
//la récurrence:
Pour i de 1 à n faire
pour j de 1 à m faire
Si u[ i ] = v[ j ] alors T[i , j] := 1+T[i-1 , j-1]
sinon T[i , j] := max(T[i , j-1] , T[i-1 , j])
fsi
fpour
Fpour
LCS := T[n , m]
La remontée, ou comment récupérer une sous-suite commune de longueur
maximale?
//Pré condition T[i , j]=LCS(i,j) pour les valeurs nécessaires
S :="" // S contiendra une sous-suite maximale
i := n // n : long(u)
j := m // m : long(v)
// on part de la case ‘‘finale’’
// et on remonte jusqu’au cas de base
tant que ((i>0) et (j>0)) faire
si u[ i ] = v[ j ]
alors S := S + u[ i ]
i := i – 1
j := j – 1
sinon si (T[i , j]=T[i-1 , j])
alors i := i – 1
sinon j := j – 1
fsi
fsi
Fait
QUAND PEUT-ON UTILISER LA
PROGRAMMATION DYNAMIQUE?
• La solution (optimale) d’un problème de taille
n s’exprime en fonction de la solution
(optimale) de problèmes de taille inférieure à
n "c’est le principe d’optimalité"
• Une implémentation récursive ”naïve” conduit
à calculer de nombreuses fois la solution de
mêmes sous-problèmes.
CONCEPTION D’UN ALGORITHME DE
PROGRAMMATION DYNAMIQUE
L’essentiel du travail conceptuel réside dans

l’expression d’une solution d’un problème en
fonction de celles de problèmes ”plus petits”!!!
COMMENT UTILISER LA
PROGRAMMATION DYNAMIQUE?
• On définit une table pour mémoriser les calculs
déjà effectués: à chaque élément correspondra
la solution d’un et d’un seul problème
intermédiaire, un élément correspondant au
problème final.
• Il faut donc qu’on puisse déterminer les sous-
problèmes qui seront traités au cours du calcul
• Ensuite il faut remplir cette table.
Principe de l’Algorithme
• On initialise les ”cases” correspondant aux cas de
base.
• On remplit ensuite la table selon un ordre bien
précis à déterminer: on commence par les
problèmes de ”taille” la plus petite possible, on
termine par la solution du problème principal:
il faut bien sûr qu’à chaque calcul, on n’utilise que
les solutions déjà calculées.
• Le but est bien sûr que chaque élément soit
calculé une et une seule fois.
Conclusion
 Solution : plutôt que de résoudre les mêmes
sous-problèmes plusieurs fois, s’arranger pour
ne les résoudre chacun qu’une seule fois
 Comment ? En sauvegardant les solutions dans

une table et en se référant à la table à chaque
demande de résolution d’un sous-problème déjà
rencontré
 On échange du temps de calcul contre de la mémoire
 Permet de transformer une solution en temps exponentiel

en une solution en temps polynomial

Program Dynamique PDF

Transféré par

Droits d'auteur :

Formats disponibles

Program Dynamique PDF

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Program Dynamique PDF

Transféré par

Droits d'auteur :

Formats disponibles

Programmation

F0=1 F1=1 Fn = Fn-1 + Fn-2

fib(n) = Si n=0 ou n=1 alors 1

Trouver x1, x2, . . . , xN ϵ {0, 1} tels que :

Solution optimale : {4, 3} Bénéfice : 22 + 18 = 40

 Soit une tige d’acier qu’on découpe pour la vendre morceau

 Sortie : Le revenu maximum qu’on peut obtenir pour des tiges de

La solution est une découpe en 2 + 6 pour un gain de 22.

aac est sous-suite de arracher, de avancer, de hamac...

Soient deux mots u et v. On cherche la longueur de la plus longue

On notera lcs(u, v) cette longueur.

Par exemple, si u = acc et v = archi, ac est la sous-suite de longueur

L’essentiel du travail conceptuel réside dans

 Comment ? En sauvegardant les solutions dans

 On échange du temps de calcul contre de la mémoire

 Permet de transformer une solution en temps exponentiel

Vous aimerez peut-être aussi