Upload
marjolaine-serra
View
108
Download
0
Embed Size (px)
Citation preview
Optimisation dans les réseaux
Recherche OpérationnelleGC-SIE
Le problème du plus court chemin
Plus courts chemins
Michel Bierlaire 3
Introduction
Plusieurs versions :– d’un nœud vers un nœud – de tous les nœuds vers un nœud – d’un nœud vers tous les nœuds– de tous les nœuds vers tous les nœuds
Nous allons étudier le problème du plus court chemin d’un nœud vers tous les autres.
Souvent, on supposera que =1.
Plus courts chemins
Michel Bierlaire 4
Introduction
Idée générale : Parcourir le réseau à partir de
l’origine Appliquer et mettre à jour des
étiquettes (d1,…,dN) à chaque nœud. Chaque étiquette est soit un
scalaire soit +.
Plus courts chemins
Michel Bierlaire 5
Conditions d’optimalité
Soient d1,d2,…,dN des scalaires tels que
dj di + aij (i,j) A Soit P un chemin entre un nœud et un
nœud . Si
dj di + aij (i,j) P Alors P est un plus court chemin entre
et .
Plus courts chemins
Michel Bierlaire 6
Conditions d’optimalité
Preuve : P est composé des arcs
(,i1),(i1,i2),…,(iP,) Longueur de P =
a,i1+ai1,i2
+…+aiP,
Comme aij = dj di (i,j) P, on a Longueur de P =
(d – diP) + (diP
– diP-1)+…+(di2
-di1)+(di1
-d)=
d-d
Plus courts chemins
Michel Bierlaire 7
Conditions d’optimalité
Soit Q un chemin quelconque entre et . Q est composé des arcs
(,j1),(j1,j2),…,(jQ,) Longueur de Q =
a,j1+aj1,j2
+…+ajQ,
Comme aij dj di (i,j) Q, on a Longueur de Q
(d – djQ) + (djQ
– djQ-1)+…+(dj2
-dj1)+(dj1
-d)=
d–d= Longueur de P.CQFD
Plus courts chemins
Michel Bierlaire 8
Algorithme générique
Idée : On démarre avec un vecteur d’étiquettes
(d1,…,dN) On sélectionne un arc (i,j) qui viole les
conditions d’optimalité, c-à-d tel que dj di + aij
On met à jour l’étiquette de jdj di + aij
Et ainsi de suite jusqu’à ce que tous les arcs vérifient la condition.
Plus courts chemins
Michel Bierlaire 9
Algorithme générique
A tout moment, l’étiquette d’un nœud i peut être interprétée comme la longueur d’un chemin reliant à i.
Si dj di + aij, cela signifie que le chemin arrivant en j à partir de i est plus court que le chemin actuel reliant à j.
Il est plus facile d’effectuer le traitement nœud par nœud.
Pour chaque nœud considéré, on traitera tous ses arcs sortant.
V= liste des nœuds à traiter
Plus courts chemins
Michel Bierlaire 10
Algorithme générique
Algorithme : Initialisation :
– V={}– d = 0, di = i
Itérations. Tant que V – Sélectionner un nœud i dans V et l’en retirer– Pour chaque arc (i,j) sortant de i,
Si dj di + aij, alors – dj di + aij
– Ajouter j à V
3
2
1 4
3
d2=+
1 1
1 3
2
d3=+
d4=+d1=0 1
Iter V d1 d2 d3 d4 traiter1 {1} 0 1
3
2
1 4
3
d2=3
1 1
1 3
2
d3=+
d4=+d1=0
Iter V d1 d2 d3 d4 traiter1 {1} 0 1
3
2
1 4
3
d2=3
1 1
1 3
2
d3=1
d4=+d1=0
Iter V d1 d2 d3 d4 traiter1 {1} 0 1
Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 3 1 2
3
2
1 4
3
d2=3
1 1
1 3
2
d3=1
d4=+d1=0
Iter V d1 d2 d3 d4 traiter1 {1} 0 1
Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 3 1 2
3
2
1 4
3
d2=3
1 1
1 3
2
d3=1
d4=+d1=0
Iter V d1 d2 d3 d4 traiter1 {1} 0 1
Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 3 1 2
3
2
1 4
3
d2=3
1 1
1 3
2
d3=1
d4=5d1=0
Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 3 1 2
Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 3 1 23 {3,4} 0 3 1 5 3
3
2
1 4
3
d2=3
1 1
1 3
2
d3=1
d4=5d1=0
Iter V d1 d2 d3 d4 traiter1 {1} 0 1
Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 3 1 2
Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 3 1 23 {3,4} 0 3 1 5 3
3
2
1 4
3
d2=3
1 1
1 3
2
d3=1
d4=4d1=0
Iter V d1 d2 d3 d4 traiter1 {1} 0 1
Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 3 1 2
Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 3 1 23 {3,4} 0 3 1 5 3
3
2
1 4
3
d2=2
1 1
1 3
2
d3=1
d4=4d1=0
Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 3 1 23 {3,4} 0 3 1 5 3
Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 3 1 23 {3,4} 0 3 1 5 34 {4,2} 0 2 1 4 4
3
2
1 4
3
d2=2
1 1
1 3
2
d3=1
d4=4d1=0
Iter V d1 d2 d3 d4 traiter1 {1} 0 1
Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 3 1 2
Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 3 1 23 {3,4} 0 3 1 5 3
Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 3 1 23 {3,4} 0 3 1 5 34 {4,2} 0 2 1 4 4
Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 3 1 23 {3,4} 0 3 1 5 34 {4,2} 0 2 1 4 45 {2} 0 2 1 4 2
3
2
1 4
3
d2=2
1 1
1 3
2
d3=1
d4=4d1=0
Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 3 1 23 {3,4} 0 3 1 5 34 {4,2} 0 2 1 4 4
Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 3 1 23 {3,4} 0 3 1 5 34 {4,2} 0 2 1 4 45 {2} 0 2 1 4 2
3
2
1 4
3
d2=2
1 1
1 3
2
d3=1
d4=4d1=0
Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 3 1 23 {3,4} 0 3 1 5 34 {4,2} 0 2 1 4 4
Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 3 1 23 {3,4} 0 3 1 5 34 {4,2} 0 2 1 4 45 {2} 0 2 1 4 2
3
2
1 4
3
d2=2
1 1
1 3
2
d3=1
d4=4d1=0
Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 3 1 23 {3,4} 0 3 1 5 34 {4,2} 0 2 1 4 45 {2} 0 2 1 4 2
Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 3 1 23 {3,4} 0 3 1 5 34 {4,2} 0 2 1 4 45 {2} 0 2 1 4 2
{} 0 2 1 4
3
2
1 4
3
d2=2
1 1
1 3
2
d3=1
d4=4d1=0
Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 3 1 23 {3,4} 0 3 1 5 34 {4,2} 0 2 1 4 45 {2} 0 2 1 4 2
{} 0 2 1 4
Plus courts chemins
Michel Bierlaire 25
Algorithme générique
Propriétés à la fin de chaque itération
Si dj < , alors dj est la longueur d’un chemin reliant à j.
Si i V, alors soit di = + , soit
dj di + aij j tel que (i,j) A
Plus courts chemins
Michel Bierlaire 26
Algorithme générique
Propriétés si l’algorithme se termine j t.q. dj < ,
– dj est la longueur du plus court chemin entre et j. – dj = min(i,j) A di+aij si j [Eq. de Bellman]– d = 0
dj = + ssi il n’y a pas de chemin reliant et j.
L’algorithme se termine ssi il n’y a aucun chemin commençant en et contenant un cycle à coût négatif
Plus courts chemins
Michel Bierlaire 27
Algorithme générique
Les équations de Bellman permettent de reconstituer les plus courts chemins à partir des étiquettes.
Le prédécesseur du nœud j dans le plus court chemin est celui qui réalise le minimum de l’équation de Bellman.
3
2
1 4
3
d2=2
1 1
1 3
2
d3=1
d4=4d1=0
3
2
1 4
3
d2=2
1 1
1 3
2
d3=1
d4=4d1=0
Plus courts chemins
Michel Bierlaire 29
Algorithme de Dijkstra
L’algorithme générique ne spécifie pas comment choisir dans V le nœud à traiter.
L’algorithme de Dijkstra impose que le nœud i à traiter soit tel que
di = minjV dj
Plus courts chemins
Michel Bierlaire 30
Algorithme de Dijkstra
Algorithme : Initialisation :
– V={}– d = 0, di = i
Itérations. Tant que V – Sélectionner un nœud i dans V tel que
di = minjV dj
– Retirer i de V– Pour chaque arc (i,j) sortant de i,
Si dj di + aij, alors – dj di + aij
– Ajouter j à V
3
2
1 4
2
d2=
1 1
1 3
1
d3=
d4=
d1=0 5
0
0
Iter V d1 d2 d3 d4 d5 traiter1 {1} 0 1
d5=
3
2
1 4
2
d2=
1 1
1 3
1
d3=
d4=
d1=0 5
0
0
Iter V d1 d2 d3 d4 d5 traiter1 {1} 0 1
d5=
3
2
1 4
2
d2=2
1 1
1 3
1
d3=
d4=
d1=0 5
0
0
Iter V d1 d2 d3 d4 d5 traiter1 {1} 0 1
d5=
3
2
1 4
2
d2=2
1 1
1 3
1
d3= 1
d4=
d1=0 5
0
0
Iter V d1 d2 d3 d4 d5 traiter1 {1} 0 1
d5=
Iter V d1 d2 d3 d4 d5 traiter1 {1} 0 12 {2,3} 0 2 1 3
3
2
1 4
2
d2=2
1 1
1 3
1
d3= 1
d4=
d1=0 5
0
0d5=
Iter V d1 d2 d3 d4 d5 traiter1 {1} 0 12 {2,3} 0 2 1 3
3
2
1 4
2
d2=2
1 1
1 3
1
d3= 1
d4=
d1=0 5
0
0d5=
Iter V d1 d2 d3 d4 d5 traiter1 {1} 0 12 {2,3} 0 2 1 3
3
2
1 4
2
d2=2
1 1
1 3
1
d3= 1
d4= 4
d1=0 5
0
0d5=
Iter V d1 d2 d3 d4 d5 traiter1 {1} 0 12 {2,3} 0 2 1 3
Iter V d1 d2 d3 d4 d5 traiter1 {1} 0 12 {2,3} 0 2 1 33 {2,4} 0 2 1 4 2
3
2
1 4
2
d2=2
1 1
1 3
1
d3= 1
d4= 4
d1=0 5
0
0d5=
Iter V d1 d2 d3 d4 d5 traiter1 {1} 0 12 {2,3} 0 2 1 33 {2,4} 0 2 1 4 2
3
2
1 4
2
d2=2
1 1
1 3
1
d3= 1
d4= 4
d1=0 5
0
0d5=
Iter V d1 d2 d3 d4 d5 traiter1 {1} 0 12 {2,3} 0 2 1 33 {2,4} 0 2 1 4 2
3
2
1 4
2
d2=2
1 1
1 3
1
d3= 1
d4= 3
d1=0 5
0
0d5=
Iter V d1 d2 d3 d4 d5 traiter1 {1} 0 12 {2,3} 0 2 1 33 {2,4} 0 2 1 4 2
3
2
1 4
2
d2=2
1 1
1 3
1
d3= 1
d4= 3
d1=0 5
0
0d5= 2
Iter V d1 d2 d3 d4 d5 traiter1 {1} 0 12 {2,3} 0 2 1 33 {2,4} 0 2 1 4 2
Iter V d1 d2 d3 d4 d5 traiter1 {1} 0 12 {2,3} 0 2 1 33 {2,4} 0 2 1 4 24 {4,5} 0 2 1 3 2 5
3
2
1 4
2
d2=2
1 1
1 3
1
d3= 1
d4= 3
d1=0 5
0
0d5= 2
Iter V d1 d2 d3 d4 d5 traiter1 {1} 0 12 {2,3} 0 2 1 33 {2,4} 0 2 1 4 24 {4,5} 0 2 1 3 2 5
Iter V d1 d2 d3 d4 d5 traiter1 {1} 0 12 {2,3} 0 2 1 33 {2,4} 0 2 1 4 24 {4,5} 0 2 1 3 2 55 {4} 0 2 1 3 2 4
3
2
1 4
2
d2=2
1 1
1 3
1
d3= 1
d4= 3
d1=0 5
0
0d5= 2
Iter V d1 d2 d3 d4 d5 traiter1 {1} 0 12 {2,3} 0 2 1 33 {2,4} 0 2 1 4 24 {4,5} 0 2 1 3 2 55 {4} 0 2 1 3 2 4
3
2
1 4
2
d2=2
1 1
1 3
1
d3= 1
d4= 3
d1=0 5
0
0d5= 2
Iter V d1 d2 d3 d4 d5 traiter1 {1} 0 12 {2,3} 0 2 1 33 {2,4} 0 2 1 4 24 {4,5} 0 2 1 3 2 55 {4} 0 2 1 3 2 4
Iter V d1 d2 d3 d4 d5 traiter1 {1} 0 12 {2,3} 0 2 1 33 {2,4} 0 2 1 4 24 {4,5} 0 2 1 3 2 55 {4} 0 2 1 3 2 4
{} 0 2 1 3 2
3
2
1 4
2
d2=2
1 1
1 3
1
d3= 1
d4= 3
d1=0 5
0
0d5= 2
Iter V d1 d2 d3 d4 d5 traiter1 {1} 0 12 {2,3} 0 2 1 33 {2,4} 0 2 1 4 24 {4,5} 0 2 1 3 2 55 {4} 0 2 1 3 2 4
{} 0 2 1 3 2
Plus courts chemins
Michel Bierlaire 46
Algorithme de Dijkstra
Propriété des étiquettes permanentes Si les coûts sur tous les arcs sont non
négatifs Considérons W={i¦di < et iV} Alors, pour chaque itération,
– aucun nœud appartenant à W au début de l’itération n’entrera dans V pendant l’itération
– à la fin de l’itération, didj si iW et jW.
Plus courts chemins
Michel Bierlaire 47
Notes
Si l’on désire calculer le plus court chemin de à , on peut arrêter l’algorithme de Dijkstra dès que le nœud est dans W.
Si au moins un arc a un coût négatif, rien ne garantit le caractère permanent des étiquettes
3
2
1 4
2
d2=
-2
1 1
1
d3=
d4=
d1=0
Iter V d1 d2 d3 d4 traiter1 {1} 0 1
3
2
1 4
2
d2=
-2
1 1
1
d3=
d4=
d1=0
Iter V d1 d2 d3 d4 traiter1 {1} 0 1
3
2
1 4
2
d2=
-2
1 1
1
d3=
d4=
d1=0
Iter V d1 d2 d3 d4 traiter1 {1} 0 1
3
2
1 4
2
d2= 2
-2
1 1
1
d3=
d4=
d1=0
Iter V d1 d2 d3 d4 traiter1 {1} 0 1
3
2
1 4
2
d2= 2
-2
1 1
1
d3= 1
d4=
d1=0
Iter V d1 d2 d3 d4 traiter1 {1} 0 1
Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 2 1 3
3
2
1 4
2
d2= 2
-2
1 1
1
d3= 1
d4=
d1=0
Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 2 1 3
3
2
1 4
2
d2= 2
-2
1 1
1
d3= 1
d4= 2
d1=0
Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 2 1 3
Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 2 1 33 {2,4} 0 2 1 2 2
3
2
1 4
2
d2= 2
-2
1 1
1
d3= 1
d4= 2
d1=0
Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 2 1 33 {2,4} 0 2 1 2 2
3
2
1 4
2
d2= 2
-2
1 1
1
d3= 1
d4= 2
d1=0
Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 2 1 33 {2,4} 0 2 1 2 2
3
2
1 4
2
d2= 2
-2
1 1
1
d3= 0
d4= 2
d1=0
Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 2 1 33 {2,4} 0 2 1 2 2
Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 2 1 33 {2,4} 0 2 1 2 24 {3,4} 0 2 0 2 3
Nœud 3 rentre à nouveau dans V
3
2
1 4
2
d2= 2
-2
1 1
1
d3= 0
d4= 2
d1=0
Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 2 1 33 {2,4} 0 2 1 2 24 {3,4} 0 2 0 2 3
3
2
1 4
2
d2= 2
-2
1 1
1
d3= 0
d4= 1
d1=0
Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 2 1 33 {2,4} 0 2 1 2 24 {3,4} 0 2 0 2 3
Iter V d1 d2 d3 d4 traiter1 {1} 0 12 {2,3} 0 2 1 33 {2,4} 0 2 1 2 24 {3,4} 0 2 0 2 35 {4} 0 2 0 1 4