Introduction
Notion de Programmation Dynamique Certaine
Houda Derbel
FSEGN
Décembre 2020
Houda Derbel Optimisation Décembre 2020 1/9
Introduction
Introduction
La PD est fondée sur le principe d’optimalité : toute partie d’un
chemin (sous-chemin) optimal est elle même optimal (Dém par
absurde)
Le terme programmation à l’époque (Bellman 1952) signifiait
planification et ordonnancement :”Une solution d’un problème dépend
des solutions précédentes obtenues des sous-problèmes”
Résoudre le problème d’un ordre donné en fonction de ses solutions
d’un ordre donné (relation de récurrence)
La programmation dynamique est une méthode dont les calculs se
font de bas en haut
Houda Derbel Optimisation Décembre 2020 2/9
Introduction
Illustration: Suite de Fibonacci
(
F (0) = 1, F (1) = 1
F (n) = F (n − 1) + F (n − 2)
1 Algorithme1:
int function Fibo(int n){
If (n ≤ 1)
return 1;
else return (Fibo(n − 1)+Fibo(n − 2))
}
En suupprimant la récursivité, cet algo. aura une forme typique de la
programmation dynamique:
2 Algorithme2:
int function Fib(int n){
F [1] = 1; F [2] = 1;
For (i = 2; i <= n; i + +)
F [i] = F [i − 1] + F [i − 2];
return (F [i]);
}
Houda Derbel Optimisation Décembre 2020 3/9
Introduction
Etapes de la PD
1 obtention de l’équation récursive : qui lie la solution d’un
problème à celle de sousproblèmes
2 initialisation de la table: conditions initiales de l’équation obtenue à
l’étape 1.
3 Remplissage de la table: résoudre les sous-problèmes de taille de
plus en plus grandes
4 Lecture de la solution: On fait un travail inverse en lisant dans la
table en partant de la solution finale et en faisant le chemin inverse
des calculs effectués en à l’étape 3.
Houda Derbel Optimisation Décembre 2020 4/9
Introduction
Définition
Dans un graphe orienté sans circuit le niveau d’un sommet xi est 0 s’il n’a
pas de prédecesseurs sinon son niveau est la longueur du plus long chemin
ayant xi comme extrêmité finale.
S’il existe un circuit on ne peut plus ordonnancer le graphe.
Ordonanncer un graphe = classer ses sommets par niveau.
Donner une représentation graphique telque les sommets soient de
niveaux croissants.
Si nous avons à construire une autoroute entre les villes A et K .
ayant un coût min.
-L’idée est de retenir à chaque fois les sous-chemins optimaux de
l’étape précedente.
-Les sommets intermidiaires seront classés par groupe de niveau.
∗
vk+1 (ik+1 ) = optk [vk+1 (ik , ik+1 ) + vk∗ (ik )]
vk∗ (ik ): valeur optimal des chemins entre A et les sommets dans le
niveau k
Houda Derbel Optimisation Décembre 2020 5/9
Introduction
Algo. de Floyd-Warshall (W) basé sur la récursion
précédente et le paradigme de la PD
Soit W = (wij )1≤i,j≤n la matrice des poids.
(k)
Soit dij le plus court chemin de i à j n’ayant des sommets
intermédiaires que dans {1, 2, ..., k}
(k)
Définissons d’une manière récursive dij :
(
(k) wij , si k=0
dij = (k−1) (k−1) (k−1)
min(dij , dik + dkj ), sinon
(k)
Soit D (m) = (dij )i,j
Houda Derbel Optimisation Décembre 2020 6/9
Introduction
Algorithme de Floyd
Algorithm 1: Floyd (W )
Result: D (n)
initialization: D 0 ← W ;
for k : 1 → n do
for i : 1 → n do
for j : 1 → n do
(k) (k−1) (k−1) (k−1)
dij ← min(dij , dik + dkj )
end
end
end
Application en classe
Houda Derbel Optimisation Décembre 2020 7/9
Introduction
Résolution du problème de sac à dos par la PD
Rappelons la définition du problème de sac à dos:
Etant donné n objets, chacun a un poids wi et gain vi et un sac de
capacité maximale W . Le problème consiste à choisir un ensemble d’objets
de façon à maximiser le gain total sans dépasser la capacité W du sac.
n
X
max vi xi
i
(P
n
i=1 wi xi≤W
s.c
xi ∈ {0, 1}, i = 1, ..., n
La programmation dynamique peut être développée en divisant le
problème en deux sous-problème comme suit :
Pij désigne le gain maximum généré par le choix des i premiers objets
dont la somme des poids ne dépasse pas j, alors résoudre le problème
revient à trouver la valeur de PnW
. Houda Derbel Optimisation Décembre 2020 8/9
Introduction
En calculant Pij , la séquence d’objets peut être divisée en deux : les
(i − 1) premiers objets et l’objet i. L’objet i est soit choisi soit ignoré
dans Pij
si l’objet i est choisi alors Pij = Pi−1,j−wi + vi
Sinon, on doit trouver la solution optimale parmi les (i − 1) premiers
objets, soit Pi−1,j
les relations récursives sont définies comme suit:
0, si i = 0 ou j=0
Pij = Pi−1,j j < wi , i > 0
max{Pi−1,j , Pi−1,j−wi + vi }
.
Houda Derbel Optimisation Décembre 2020 9/9
