Aide à la décision

Aide à la décision

Bloc1 : Théorie des graphes et problèmes d’ordonnancement

Séance 2

Mohamed Ali [email protected]

Une partie de ces transparents a été élaborée en se basant sur le document de

Pierre Lopez, LAAS, Toulouse http://www.laas.fr/~lopez/cours/GRAPHES/graphes.html

mailto:[email protected]





Plan du cours

1. Qu’est ce qu’on peut faire avec la théorie des graphes ?

2. Concepts généraux en théorie des graphes

3. Le problème du plus court chemin

4. Problème central de l’ordonnancement

http://www.lamsade.dauphine.fr/~aloulou/cours/L3STCF_Bloc1_Graphes.pdf

2. Le problème du plus court chemin

• Définition du problème• Exemples de formulation avec pcch• Principe d’optimalité et conditions d’existence• Graphes sans circuit• Graphes à valuations positives

– Algorithme de Moore-Dijkstra (1959)

• Graphes à valuations quelconques– Contre-exemple– Algorithme de Bellman-Ford

• Le problème du plus court chemin

Définition du problème• Soit G=(X,U) un graphe sans boucle

• Pour tout arc u=(xi,xj)U on associe une valuation a(u) = aij : durée, distance ...

• La valeur d’un chemin :

v() = a(u), u

S

A

B

C

E

D

6

1

23

32

2

-4


Définition du problème• On peut s’intéresser aux problème

– de plus court chemin (valeur min)– de plus long chemin (valeur max)

S

A

B

C

E

D

6

1

23

32

2

-4


Exemples• Exemple 1 : Construire une autoroute entre

deux villes A et K– Arcs = tronçons possibles de l’autoroute– Valuation des arcs peut être

• coût de réalisation correspondant• longueur du trajet • …

A

B

C

D

E

F

H

I

J

K

G


Exemples• Exemple 2 : Chemin le plus fiable dans un

réseau de télécommunication– Arêtes = liens physiques– Valuation des arêtes (i,j) est pij: fiabilité du lien (la

probabilité pour que le lien fonctionne)

– La fiabilité d’un chemin est le produit des probabilités des liens qui le constituent

– Le problème devient un problème de pcch en remplaçant chaque probabilité par aij = - log pij


Les 3 types de problèmes1. Recheche des chemins extrêmaux d’un sommet

xk vers un sommet xj

2. Recherche des chemins extrêmaux d’un sommet xk vers tous les autres sommets

3. Recherche des chemins extrêmaux entre tout couple de sommets


Principe d’optimalité

• aij = longueur de l’arc (i,j) si l’arc existe sinon + • uj : longueur du pcch de l’origine 1 vers le sommet j• Equations de Bellman

– u1 =0– uj = min {kj, uk + akj}


Condition d’existence

• Condition d’existence Le graphe n’admet pas de circuit de longueur négative

i

j

k

w l(w)<0


Graphes acycliques

• Un graphe est acyclique ssi il existe une numérotation des sommets telle qu’un arc existe entre i et j seulement si i < j

• Les équations de Bellman deviennent

– u1 =0

– uj = min {k < j, uk + akj}

1

42

3 5

6

3

1

-6

3

-42

9

6

1

2

5


Graphes à valuations positives

• Algorithme de Dijkstra : plus court chemin de l’origine à tous les autres sommets– Utilise des labels pour les sommets

• Les labels permanents représentent la valeur du pcch de l’origine jusqu’au sommet correspondant

• Les labels temporaires représentent une borne supérieure de ce pcch

– A chaque itération un label temporaire est transformé en label permanent


Graphes à valuations positivesAlgorithme de Dijkstra

• Etape 0– u1 =0;– uj =a1j, pour j=2,…, n– P={1}, T={2, …, n}

• Etape 2 (Désignation du label permanent)– Déterminer kT, tq uk=min{j T, uj}– T=T\{k} et P=P{k}– Si T=vide, stop

• Etape 3 (Révision des labels temporaires)– uj=min{uj, uk+akj} pour tout j T– Aller à l’étape 1


Graphes à valuations positives

• Exemple

A

B

D

C

E

F H

G

2

4

4

32 2

1

2

3

25

3


Algorithme de Dijkstra et graphes à valuations quelconques

S

A

B

C

E

D

6

1

23

3

2

2

-4


Graphes à valuations quelconques

• Algorithme de Bellman-Ford– uj

(m) = longueur du pcch de 1 vers j tel que le chemin ne contient pas plus que m arcs

u1(1)= 0

uj(1) = a1j

uj(m+1) = min{uj

(m) , min{kj, uk(m) + akj}}

• Si le graphe ne contient pas de circuit de valeur négative alors uj = uj

(n-1)



Algorithme de Bellman-Ford• Etape 0

– u1(0)= 0, uj

(0) = + pour tout j1, m:=0

• Etape 1 (On modifie les marques à partir des marques de l’étaqe pécédente)Pour tout j1 uj

(m+1) = min{uj(m) , min{kj, uk

(m) + akj}}

• Etape 2– Si pour tout j, uj

(m+1) = uj(m) alors FIN

• Sinon Si m<n-1 alors poser m:=m+1 et aller à l’étape 1– Sinon Si m=n-1, alors G admet au moins un circuit

absorbant



• Plus court chemin entre tous les couples de sommets– Algorithme matriciel de Floyd-Warshall

Documents

Aide à la décision