Structures de données IFT-2000 Abder Alikacem Les graphes (3) Semaine 7 Département dinformatique et de génie logiciel Édition Septembre 2009

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.


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))



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.


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


a

db

f

c e

4 56

310

2

81 20

a b c d e f

0

- - - - - -

V, S, T

Y

P


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


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


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


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


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


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


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


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!


s

c

a3

53 -6


Soit le graphe G(V,E)


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


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



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



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


Cycle de coût négatif: réduction encore possible !


Bellman-Ford revu….

Soit le graphe G(V,E)


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


s

dc

b

a3

5

-3

1 -1 -1 3

5

5

5

3 8

4 7

0


s

dc

b

a3

5

-3

1 -1 -1 3

5

5

5

3 8

4 7

0


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


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;

}

Documents

Structures de données IFT-2000 Abder Alikacem Les graphes (3) Semaine 7 Département dinformatique et de génie logiciel Édition Septembre 2009