View
107
Download
2
Category
Preview:
Citation preview
Structures de donnéesIFT-2000
Abder AlikacemAbder Alikacem
Les graphes (3)
Semaine 7
Département d’informatique et de génie logiciel
Édition Septembre 2009
Plan
Tri topologique Connexité des graphesAlgorithme de DijkstraAlgorithme de Bellman-FordAlgorithme A*
Algorithme de Dijkstra
Se base sur le principe de la sous-optimalité Si p est le plus court chemin entre deux sommets i et j alors:
k, un sommet appartenant à p le sous-chemin de p (i, k) est optimal (le plus court) le sous-chemin de p (k, j) est optimal (le plus court)
3s
dc
b
a3
5
3
1 1 1
5
5
5s
dc
b
a3
5
3
1 1 1 3
5
5
5
3 8
4 9
0
Exemple. Plus court chemin entre s et i v (v : l’ensemble des sommets)
Pour chaque sommet i v , on maintient à jour un attribut yi : une estimation de la pondération d’un plus court chemin:
État initial : ys = 0 (s étant la source) yi = + avec i s
À chaque étape : essayer de minimiser les yi
État final : yi = lpcc(s,i) (lpcc: le plus court chemin)
L’algorithme est basée sur la technique de relâchement C’est une méthode qui diminue progressivement le poids du plus
cours chemin pour chaque sommet jusqu’à ce qu’il soit égal au poids du plus court chemin.
Algorithme de Dijkstra
RELÂCHER (a,b, c (a,b)) Si yb > ya + c (a,b) Alors yb ya + c (a,b)
ba
b
a
2
5 9
5 7
2
Relâcher(a,b, c(a,b))
ba
b
a
2
5 6
5 6
2
Relâcher(a,b, c(a,b))
Algorithme de Dijkstra
Algorithme de Dijkstra
Soit V l’ensemble des sommets d’un graphes
Initialiser yi = + pour tous les sommets i
Initialiser ys = 0.
Initialiser S à l'ensemble vide, T = V.
Tant que T n'est pas vide
1.Sélectionner le sommet j de T de plus petite valeur yi
2.Faire T = T \ j et S = S j
3.Pour tous les sommets k de T adjacents à j, faire RELÂCHER(j, k, c(j,k))
Fin Tant que.
RELÂCHER (a,b, c (a,b)) Si yb > ya + c (a,b) Alors
yb ya + c (a,b) P[b] a
Algorithme de Dijkstra et le chemin
f
dd
e
g
h
e
Pour aller d’un sommet A à un sommet B appliquer l’algorithme de Dijkstra tout conservant pour
chaque nœud le nœud origine à partir duquel sa plus petite distance de la source a été calculée.
Algorithme de Dijkstra
a
db
f
c e
4 56
310
2
81 20
a b c d e f
0
- - - - - -
V, S, T
Y
P
V: ensemble des sommetsS: les sommets solutionnésT: une file d’attente (suivant le coût)Y: tableau des coûtsP: tableau des sommets précédents
Algorithme de Dijkstra
a
db
f
c e
4 56
310
2
81 20
a b c d e f
0
- - - - - -
V, S, T
Y
P
Algorithme de Dijkstra
a
db
f
c e
4 56
310
2
81 20
2 (a)
4 (a)
a c b d e f
0 2 4
- a a - - -
V, S, T
Y
P
Algorithme de Dijkstra
a
db
f
c e
4 56
310
2
81 20
2 (a) 12 (c)
3 (c) 10 (c)
a c b d e f
0 2 3 10 12
- a c c c -
V, S, T
Y
P
Algorithme de Dijkstra
a
db
f
c e
4 56
310
2
81 20
2 (a) 12 (c)
3 (c) 8 (b)
a c b d e f
0 2 3 8 12
- a c b c -
V, S, T
Y
P
Algorithme de Dijkstra
a
db
f
c e
4 56
310
2
81 20
2 (a) 10 (d)
3 (c) 8 (b)
14 (d)
a c b d e f
0 2 3 8 10 14
- a c b d d
V, S, T
Y
P
Algorithme de Dijkstra
a
db
f
c e
4 56
310
2
81 20
2 (a) 10 (d)
3 (c) 8 (b)
13 (e)
a c b d e f
0 2 3 8 10 13
- a c b d e
V, S, T
Y
P
Algorithme de Dijkstra
a
db
f
c e
4 56
310
2
81 20
2 (a) 10 (d)
3 (c) 8 (b)
13 (e)
a c b d e f
0 2 3 8 10 13
- a c b d e
V, S, T
Y
P
s
c
b
a3
121 1
6
2
Algorithme de Dijkstra
Exercice
Appliquez l’algorithme de Dijkstra à ce graphe à partir du sommet s
s
c
b
a3
121
1
6
2
3,s 9,a
11,b
0
Algorithme de Dijkstra
Réponse
s
c
b
a3
121
1
6
2
Amusons nous!
0
Appliquons le principe du relâchement à chaque arc de ce graphe, l’ordredes arcs est choisi aléatoirement. Un arc relâché sera mis avec une autrecouleur.
s
c
b
a3
121
1
6
2
1er tour…
0
s
c
b
a3
121
1
6
2
0
1er tour…
s
c
b
a3
121
1
6
2
3
0
1er tour…
s
c
b
a3
121
1
6
2
3
0
1er tour…
s
c
b
a3
121
1
6
2
3
0
1er tour…
s
c
b
a3
121
1
6
2
3
0
1er tour…
On a relâché tous les arcs. Recommençons une nouvelle fois. Un arc relâché sera mis cette fois en bleu
s
c
b
a3
121
1
6
2
3
0
2ième tour…
s
c
b
a3
121
1
6
2
3
0
2ième tour…
s
c
b
a3
121
1
6
2
3 9
0
2ième tour…
s
c
b
a3
121
1
6
2
3 9
0
2ième tour…
s
c
b
a3
121
1
6
2
3 9
0
2ième tour…
s
c
b
a3
121
1
6
2
3 9
11
0
2ième tour…
s
c
b
a3
121
1
6
2
Un autre tour?
3 9
11
0
On arrête ce jeu!
s
c
b
a3
121
1
6
2
Un autre tour?
3 9
11
0
s
c
b
a3
121
1
6
2
3 9
11
0
Résultat suite à l’exécution de l’algorithme de Dijkstra
Résultat à l’issu de l’exécution de l’algorithme de notre jeu …Il s’agit en fait de la simulationDe l’algorithme de Bellman-Ford! Limité à des poids positifs
Poids positifs et négatifs
Problématique des arcs de poids négatifs Si un graphe ne contient aucun circuit de poids négatif
accessible à partir d’une origine s, alors, pour tout sommet i v, le poids du plus court chemin reste bien défini, même si sa valeur est négative.
Algorithme de Bellman-Ford
s
c
a3
56 -3
Problématique des arcs de poids négatifs S’il existe un circuit de poids négatif accessible depuis s,
le poids du plus court chemin n’est pas correctement défini. Aucun chemin entre s et un sommet du circuit ne peut être plus court, on peut toujours trouver un encore plus court!
Algorithme de Bellman-Ford
s
c
a3
53 -6
Algorithme de Bellman-Ford
Soit le graphe G(V,E)
Initialiser yi = + pour tous les sommets i
Initialiser ys = 0.
Répéter |V| - 1 FOIS
Pour tout arc (u,v) de E
faire RELÂCHER(u, v, c(u,v))
Pour tout arc (u,v) de E faire
Si yv > yu + c(u,v) Alors
Retourner FAUX
Retourner VRAI
Faire les étapes nécessaires pour faire converger le
poids des chemins sachant qu’un plus court chemin de s
à tout autre sommet est un chemin d’ordre au plus n -1 arcs.
Vérifier s’ils ont tous convergé.
Retourner VRAI si c’est le cas.
Retourner FAUX sinon.
s
dc
b
a3
5
3
1 1 1 -3
5
5
5
0s
dc
b
a3
5
3
1 1 1 -3
5
5
5
3 6
4 9
0
Étape 1 relaxation de tous les arcs dans l’ordre :(s,a) (s,c) (a,b) (a,c) (b,d) (c,a) (c,b) (c,d) (d,b) (d,s)
Exemple 1
Algorithme de Bellman-Ford
s
dc
b
a3
5
3
1 1 1 -3
5
5
5
3 4
4 7
0s
dc
b
a3
5
3
1 1 1 -3
5
5
5
3 6
4 9
0
Étape 2 relaxation de tous les arcs dans l’ordre :(s,a) (s,c) (a,b) (a,c) (b,d) (c,a) (c,b) (c,d) (d,b) (d,s)
Algorithme de Bellman-Ford
s
dc
b
a3
5
3
1 1 1 -3
5
5
5
3 2
4 5
0s
dc
b
a3
5
3
1 1 1 -3
5
5
5
3 4
4 7
0
Étape 3 relaxation de tous les arcs dans l’ordre :(s,a) (s,c) (a,b) (a,c) (b,d) (c,a) (c,b) (c,d) (d,b) (d,s)
Algorithme de Bellman-Ford
s
dc
b
a3
5
3
1 1 1 -3
5
5
5
3 0
4 3
0s
dc
b
a3
5
3
1 1 1 -3
5
5
5
3 2
4 5
0
Étape 4 relaxation de tous les arcs dans l’ordre :(s,a) (s,c) (a,b) (a,c) (b,d) (c,a) (c,b) (c,d) (d,b) (d,s)
Cycle de coût négatif: réduction encore possible !
Algorithme de Bellman-Ford
Bellman-Ford revu….
Soit le graphe G(V,E)
Initialiser yi = + pour tous les sommets i
Initialiser ys = 0.
K 1
Répéter
Stable VRAI
Pour tout arc (u,v) de E
faire RELÂCHER(u, v, c(u,v))
Si …Alors Stable FAUX
K k + 1
Tant que Stable est FAUX ET k < n+1
Si non Stable alors présence d’un circuit de poids négatif
s
dc
b
a3
5
-3
1 -1 -1 3
5
5
5
0
Exemple 2
Étape 1 relaxation de tous les arcs dans l’ordre :(s,a) (s,c) (a,b) (a,c) (b,d) (c,a) (c,b) (c,d) (d,b) (d,s)
s
dc
b
a3
5
-3
1 -1 -1 3
5
5
5
3 8
4 7
0
Algorithme de Bellman-Ford
s
dc
b
a3
5
-3
1 -1 -1 3
5
5
5
3 8
4 7
0
Étape 2 relaxation de tous les arcs dans l’ordre :(s,a) (s,c) (a,b) (a,c) (b,d) (c,a) (c,b) (c,d) (d,b) (d,s)
Pas de réduction possible : coûts corrects!
s
dc
b
a3
5
-3
1 -1 -1 3
5
5
5
3 8
4 7
0
Algorithme de Bellman-Ford
Recherche de chemins de coût minimal avec l’algorithme A*
Jeux vidéo• Animation des personnages non joueurs • Déplacement réaliste d’un personnage contrôlé par le joueur
vers un objectif désigné par le joueur
Simulation – vie artificielle• Etude du comportement d’une foule, du trafic automobile, …• Effets spéciaux (scènes de bataille, …)
Algorithme A*
Coût total (F) = Coût depuis la source(G) + Coût vers la destination(H)
G : Coût depuis la source• Algorithmes classiques (Ford, Bellman, Dijkstra)
H : Coût vers la destination• Difficile puisque le reste du chemin est encore inconnu.
Principe général : évaluation du coût total d’un sommet
Pourquoi évaluer un coût vers la destination ?Afin de resserrer l’ensemble des sommets à explorer en privilégiant les sommets « qui semblent » nous rapprocher de la destination.
RemarqueDans le cas d’un algorithme de recherche plus classique (Dijsktra), on effectue une recherche exhaustive parmi TOUS les sommets candidats.
Conséquencel’algorithme A* est plus performant que n’importe quel autre algorithme puisqu’il diminue l’ensemble des sommets à explorer.
Algorithme A*
Comment évaluer un coût vers la destination ?En utilisant des heuristiques (prédictions) afin d’évaluer un coût vers la destination INFERIEUR au coût réel (encore inconnu). À ce titre, A* est un algorithme dit optimiste.
RemarqueSi l’heuristique était supérieur au coût réel, on risquerait de générer un chemin qui ne soit pas minimal.
On utilise généralement deux heuristiques, la distance euclidienne et la distance de Manhattan
Algorithme A*
Distance euclidienne
S
D
40
H 20
Théorème de Pythagore
H 2 = (Coté oppose) 2 +
(Coté adjacent) 2
H 2 = 40 2 + 20 2
= 2000
H = 20 x (5) 1/2
Algorithme A*
Distance de Manhattan
S
D
Nombre de cellules, en horizontal et en vertical entre la source et la destination.
Plus conforme à la nature des déplacements autorisés (haut, bas, gauche, droite)
Graphe, lab#7/** * Algorithme de Warshall
*/template <typename T>Graphe<T> fermetureGraphe(Graphe<T> g)throw(logic_error);
Graphe (int nbSommet);Graphe (const Graphe&); Graphe(const Graphe& g, std::vector<T>&);~Graphe (); Graphe& operator = (const Graphe&);void ajouterSommet(T s) ;void ajouterArc (T s1, T S2);void enleverArc (T s1, T s2);void enleverSommet ( T s);bool sommetExiste(T s);bool arcExiste ( T s1, T s2);int nbSommets();void affiche();std::vector<T> listerSommetsGraphe();int ordreEntreeSommet(T sommet);std::vector<T> listerSommetsAdjacents(T sommet);int ordreSortieSommet(T sommet) ;
Algorithme de Warshall{Soit A, un graphe orienté}
P APour k = 1, 2, ..., n Pour i = 1, 2, ..., n Pour j = 1, 2, ..., n
Pij Pij ou (Pik et Pkj)
Graphe, lab#7
Algorithme de Warshall{Soit A, un graphe orienté}P APour k = 1, 2, ..., n Pour i = 1, 2, ..., n Pour j = 1, 2, ..., n
Pij Pij ou (Pik et Pkj)
template <typename T>Graphe_Lab7::Graphe<T> fermetureGraphe (Graphe_Lab7::Graphe<T> g) { Graphe<T> fermG(g); vector<T> v = fermG.listerSommetsGraphe(); int nb = fermG.nbSommets(); for (int k = 0; k < nb; k++)
for (int i = 0; i < nb; i++)for (int j = 0; j < nb; j++)
if (fermG.arcExiste(v[i], v[j]) == false){
if ((fermG.arcExiste(v[i], v[k]) == true) && (fermG.arcExiste(v[k], v[j]) == true)){
fermG.ajouterArc(v[i], v[j]);}
}return fermG;
}
Recommended