IN101 - cours 13 - 17 de19 ecembre 2010

Matthieu Finiasz

Description

Un probl`eme concretFonctionnemnt d’un GPSIN 101 - Cours 1316 d´ecembre 2011pr´esent´eparMatthieu FiniaszUn probl`eme concret Un probl`eme concretFonctionnemnt d’un GPS Fonctionnemnt d’un GPS On repr´esente chaque intersection par un nœud, On cr´ee ainsi un graphe orient´epond´er´e, les nœuds sont reli´es par des branches qui ont : le GPS cherche un plus court chemin dedansun sens optimiserunpoidssurunchemindeA`aB. des poids (distance, temps, vitesse...)MotivationsLes graphes mod´elisent : r´eseaux de communication (routes, t´el´ecoms, m´etro...), circuits ´electriques, tˆaches et d´ependances/ant´eriorit´e...Les graphes15438726D´ efinitions D´ efinitionsUn graphe orient´e G (directed graph) est un couple (S,A)ou:` Un graphe orient´e G (directed graph) est un couple (S,A)ou:`S est un ensemble de sommets (vertex/vertices), S est un ensemble de sommets (vertex/vertices),A est un sous ensemble de S ×S (les arcs). A est un sous ensemble de S ×S (les arcs).Une suite d’arcs est un chemin.1 15 54 43 3Sommets8 87 72 2Chemin deArcslongueur 46 6D´ efinitions D´ efinitionsUn graphe orient´e G (directed graph) est un couple (S,A)ou:` Mˆemes d´efinitions pour un graphe non-orient´e (undirected graph):S est un ensemble de sommets (vertex/vertices), les arcs s’appellent des arˆetes (edges).A est un sous ensemble de S ×S (les arcs).Un arbre (g´en´eral) est un graphe non-orient´e, sans cycle, connexeUne suite d’arcs est un chemin ...

Informations

• Publié par: Syaj
• Nombre de lectures: 10
• Langue: Français

Extrait

IN 101 - Cours 13 16d´ecembre2011

´ t´ ar presen e p Matthieu Finiasz

Unprobl`emeconcret Fonctionnemnt d’un GPS

O ´ nte chaque intersection par un nœud,  n represe  les nœuds sont reli´es par des branches qui ont :  un sens  des poids (distance, temps, vitesse...)

Un probl` t eme concre Fonctionnemnt d’un GPS

Unprobl`emeconcret Fonctionnemnt d’un GPS

 Oncr´eeainsiun grapheorient´epond´ere´ ,  le GPS cherche un plus court chemin dedans  optimiser un poids sur un chemin de A `a B.

Les graphes

D´efinitions

Un grapheoriente´ G ( directed graph ) est un couple ( S , A )ou`: S est un ensemble de sommets ( vertex/vertices ), A est un sous ensemble de S × S (les arcs ).

5 1 4 8 Sommets 3 7 2 Arcs

6

Motivations

Les graphes mod´elisent :  reseauxdecommunication(routes,t´ele´coms,metro...), ´ ´  circuitse´lectriques,  taˆchesetd´ependances/ant´eriorite... ´

5 1

4 8 3 7 2

6

D´finitions e

Un graphe orient´e G ( directed graph ) est un couple ( S , A )ou`: S est un ensemble de sommets ( vertex/vertices ), A est un sous ensemble de S × S (les arcs ). Une suite d’arcs est un chemin .

5 1 4 8 3 7 2 Chemin de longueur 4 6

D´efinitions

Un grapheoriente´ G ( directed graph ) est un couple ( S , A )ou`: S est un ensemble de sommets ( vertex/vertices ), A est un sous ensemble de S × S (les arcs ). Une suite d’arcs est un chemin . Un chemin qui  boucle  est un cycle .

5 1 4 8 3 7 2 Cycle de longueur 3 6

Repr´esentationenmachined’ungraphe

On ne peut pas utiliser une structure similaire `a celle d’un arbre : un sommet n’a pas un  pe`re  unique  impossibledefairecommeunarbreg´ene´ral, on veut pourvoir acc´eder directement `a un sommet donne. ´

Ilyaplusieursrepr´esentations,adapt´eesa`diff´erentsalgorithmes: matrice d’adjacence  plus bas´ee sur les sommets, listes de successeurs  plusbase´esurlesarcs.

D´efinitions

Meˆmesde´finitionspourun graphe non-orient´e ( undirected graph ) : les arcs s’appellent des areˆtes ( edges ). Unarbre(g´en´eral)estungraphenon-orient´e,sanscycle,connexe et dont on fixe un sommet comme racine.

5 1 Cycle de 4 longueur 5 Arêtes 8 Sommets 3 7 2 Chemin de longueur 3 6

Matrice d’adjacence

Onsupposelessommetsindex´esde1`a n : S = { 1, ..., n } et A ⊂ S × S . Ond´efinitunematrice M de taille n × n telle que : M i , j = 1 si ( i , j ) ∈ A , M i , j = 0 sinon. Complexite´spatialeen Θ  n 2   pas pour des algorithmes lin´eaires. 5 1  4 ⎛ 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 ⎞ 8 3 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 0 7 2 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 ⎝ ⎜ 0 0 0 0 0 0 1 0 ⎠ ⎟ 1 1 0 0 0 0 0 0 6

Listes de successeurs

Un tableau contenant la liste des successeurs de chaque sommet : tableau tab de n listeschaˆıne´es, tab[i] contient la liste des successeurs du sommet i . Complexit´e spatiale en Θ ( | S | + | A | ) ,  on ne peut pas faire mieux.

5 1 tab 1 4 2 3 7 6 8 3 3 4 6 4 3 1 7 2 5  7  8 6 2 7 7 6 8 1 2

Pourquoi faire un parcours ?

Danslesrepre´sentationspr´ec´edenteslessommetssontjustedes entiers { 1, ..., n } . `aquoisertunparcoursalors?

Eng´ene´ral,ungraphenesertpas`astockerdesdonn´ees: onconstruitungraphe`apartirdedonn´eesd´ej`astock´ees, onanalyselegraphepourend´eduiredespropri´ete´sdesdonn´ees.

Les parcours sont des fa¸cons d’analyser la structure du graphe : plus courts chemins, composantes (fortement) connexes, recouvrements...

Parcours de graphe

Recouvrement d’un graphe

Unparcoursserteng´ene´rala`produireun recouvrement d’ raphe un g par des arbres : sous-graphe dans lequel un sommet a au plus un pr edecesseur, ´ ´ s’il y a plusieurs arbres, on a une forˆet. Utile pour  simplifier  un graphe  garder uniquement l’information qui nous int´eresse. 5 1 4 8 3 7 2

6

Recouvrement d’un graphe

Unparcoursserteng´ene´ral`aproduireun recouvrement d’un graphe par des arbres : sous-graphedanslequelunsommetaauplusunpr´ed´ecesseur, s’il y a plusieurs arbres, on a une forˆet. Un tel recouvrement se stock av tableau d ` e ec un e peres .

5 1  1 4 4 2  6 8 3  3  2 4 3 7 5  - 2 6 - 7 2 8 5 6

´ Equivalent du parcours par niveaux des arbres : on part d un sommet, ’ on visite tous les voisins, on visite tous les voisins des voisins...

Parcours en largeur

On ne veut pas visiter deux fois un mˆeme sommet : on colorie les sommets  blanc = non visit´e, gris = en cours, noir = visit´e on stocke le  p`ere  de chaque sommet. on stocke aussi la distance au sommet de d´epart,

Recouvrement d’un graphe

Un parcours sert en g´eneral a produire un recouvrement d’un graphe ´ ` par des arbres : sous-graphedanslequelunsommetaauplusunpr´ed´ecesseur, s’il y a plusieurs arbres, on a une forˆet. Un tel recouvrement se stocke avec un tableau de p`eres .

1 5 1  4 4 2  6 2 Comment construire un tel recouvrement ? 3 Quel sens aura-t-il ? - - 7 2 8 5 6

Parcours en largeur

Initialement : un sommet est choisi comme point de d´epart (racine), sa distance est 0, il n’a pas de p`ere.

5 1 4 1 2 3 4 5 6 7 8 8 3 d 0 7 2 ¼ -

6

Parcours en largeur

Initialement : un sommet est choisi comme point de d´epart (racine), sa distance est 0, il n’a pas de p`ere. Tous ses voisins sont `a distance 1, la racine est leur p`ere.

5 1 4 1 2 3 4 5 6 7 8 8 3 d 0 1 1 7 2 ¼ - 5 5

6

Parcours en largeur

Initialement : un sommet est choisi comme point de d´epart (racine), sa distance est 0, il n’a pas de p`ere. Tous ses voisins sont `a distance 1, la racine est leur p`ere. On continue de voisin en voisin...

5 1 4 1 2 3 4 5 6 7 8 8 3 d 2 2 3  0  3 1 1 7 2 ¼ 8 8 2 - 2 5 5

6

Parcours en largeur

Initialement : un sommet est choisi comme point de d´epart (racine), sa distance est 0, il n’a pas de p`ere. Tous ses voisins sont `a distance 1, la racine est l ` eur p ere. On continue de voisin en voisin...

5 1 4 1 2 3 4 5 6 7 8 3 8 d 2 2 0 1 1 7 2 ¼ 8 8 - 5 5

6

Parcours en largeur

Initialement : un sommet est choisi comme point de d´epart (racine), sa distance est 0, il n’a pas de p`ere. Tous ses voisins sont `a distance 1, la raci t l ` ne es eur p ere. On continue de voisin en voisin...

5 1 4 1 2 3 4 5 6 7 8 3 8 d 2 2 3 4 0 3 1 1 7 2 ¼ 8 8 2 3 - 2 5 5

6

Parcours en largeur

On obtient une arborescence des plus courts chemins partant de la racine choisie, c’est un recouvrement si tous les sommets sont atteignables.

7

5 1 4 1 2 3 4 5 6 7 8 8 3 d 2 2 3 4 0 3 1 1 2 ¼ 8 8 2 3 - 2 5 5

6

Application du parcours en largeur Plus court chemin dans un labyrinthe

On veut trouver un chemin dans un labyrinthe depre´fe´renceonveutle plus court chemin .

Parcours en largeur Algorithme

Pour programmer un parcours en largeur on utilise un file F : F contient initialement un seul sommet s (la racine).

Tant que F n’est pas vide :  soit u le premier sommet de F  pour tout v voisinnon-visit´e(colorie´enblanc)de u  colorier v en gris  d [ v ] = d [ u ] + 1  π [ v ] = u  ajouter v dans F  colorier u en noir

Complexit´e en O ( | A | ) pour un structure en liste de successeurs.

Application du parcours en largeur Plus court chemin dans un labyrinthe

On veut trouver un chemin dans un labyrinthe depr´ef´erenceonveutle plus court chemin . Oncommenceparcr´eerungraphea`partirdulabyrinthe.

Application du parcours en largeur Plus court chemin dans un labyrinthe

On veut trouver un chemin dans un labyrinthe depre´f´erenceonveutle plus court chemin . On commence par cr´eer un graphe `a partir du labyrinthe. Parcours en largeur en partant du sommet vert.

Algorithme de Dijkstra Pluscourtchemindansungraphepond´ere´

On peut adapter le parcous en largeur pour un graphe pond´ere´ : on suppose que les arcs ont des poids positifs, il suffit de toujours extraire sommet en cours de visite le plus proche en premier  au lieu d’une file, on utilise un tas (le plus proche `a la racine) 5 1  1 2 3 4 5 6 7 8 3 1 4 4 5 d 8 1 8 3 ¼ 3 2 7 2 2 4 7 1 6

Application du parcours en largeur Plus court chemin dans un labyrinthe

On veut trouver un chemin dans un labyrinthe depre´fe´renceonveutle plus court chemin . On commence par creer un graphe a partir du labyrinthe. ´ ` Parcours en largeur en partant du sommet vert. On retrace le chemin en remontant les p`eres depuis l’arrivee. ´

Algorithme de Dijkstra Plus court chemin dans un graphe po d´e ´ n re

Ond´emarreen5: sa distance est 0 (tous les autres sont `a l’infini pour l’instant) il n’a pas de p`ere on le place dans le tas des sommets  en cours de visite 

0 5 1  1 2 3 4 5 6 7 8 1 4  3 4 5 d 1 1 1 1 0 1 1 1 8 1 8 3 ¼ - 7 2 3 2 0 2 4 tas 5 7 1 6

Algorithme de Dijkstra Pluscourtchemindansungraphepond´ere´

Comme pour le parours en largeur : on extrait le premier sommet  en cours de visite  (ici, le 5) onins`eretoussesvoisins(7et8)  onnoteleurpe`reetleursdistances.

0 5 1 1  2 3 4 5 6 7 8 1 4  3 4 5 d 1 1 1 1 0 1 8 1 8 1 1 8 3 ¼ - 5 5 8 7 2 3 2 1 2 4 tas 8 8 7 7 1 6

Algorithme de Dijkstra Pluscourtchemindansungraphepond´ere´

Le sommet le plus proche est 2 (`a distance 4)  on l’extrait.

0 5 5 1 1  2 3 4 5 6 7 8 3 1 4 4 5 d 5 4 1 1 0 1 8 1 8 1 1 8 3 ¼ 8 8 - 5 5 8 3 4 2 7 2 5 2 4 tas 8 1 7 7 1 6

Algorithme de Dijkstra Pluscourtchemindansungraphepond´ere´

Comme 8 est plus proche que 7, il est `a la racine du tas on extrait maintenant 8 onins`eresesvoisins  regles normales d’insertion/extraction dans un tas. `

0 5 5 1 1  2 3 4 5 6 7 8 1 4  3 4 5 d 5 4 1 1 0 1 8 1 8 1 1 8 3 ¼ 8 8 - 5 5 8 7 3 4 2 4 2 2 4 tas 8 2 5 1 7 7 1 6

Algorithme de Dijkstra Pluscourtchemindansungraphepond´er´e

Le sommet le plus proche est 2 (`a distance 4) : onins`erelepremiersuccesseur(ici6)  on note son p`ere et sa distance

0 5 5 1 1  2 3 4 5 6 7 8 3 1 4 4 5 d 5 4 1 1 0 11 8 1 8 1 1 8 3 ¼ 8 8 - 2 5 5 8 3 4 2 7 2 2 5 4 tas 1 8 11 1 7 11 7 6 6

Algorithme de Dijkstra Pluscourtchemindansungraphepond´er´e

Le sommet le plus proche est 2 (`a distance 4) : onins`ereledeuxi`emesuccesseur(ici3)  on note son pere et sa distance `

0 5 5 1 1  2 3 4 5 6 7 8 3 1 4 4 5 d 5 4 6 1 0 11 8 1 8 1 1 6 8 3 ¼ 8 8 2 - 2 5 5 8 4 2 7 2 3 5 2 1 4 tas 6 11 1 7 6 11 8 3 6 7

Algorithme de Dijkstra ´ Plus court chemin dans un graphe pond´ere

On continue le mˆeme algorithme jusqu’`a avoir vid´e le tas : on extrait 1.

0 5 5 1 1 2 3 4 5 6 7 8 3 4 d 0 1 4  5 5 4 6 1 11 6 1 8 1 1 6 8 3 ¼ 8 8 2 - 2 2 5 6 3 4 2 7 2 2 6 4 t 7 as 6 11 1 7 11 3 6 6

Algorithme de Dijkstra Plus court chemin dans un gr h pond´ ´ ap e ere

Le sommet le plus proche est 2 (`a distance 4) : letroisie`mesuccesseur(ici7)estd´eja`dansletas, on a trouv´e un chemin plus court pou l’ tteindre r a  onmeta`joursadistance(etsaplacedansletas)etsonp`ere

0 5 5 1 1  2 3 4 5 6 7 8 3 d 1 4 4 5 5 4 6 1 0 11 6 1 8 1 1 6 8 3 ¼ 8 8 2 - 2 2 5 8 6 3 4 2 7 5 2 2 4 tas 6 1 11 1 7 11 6 3 6 6 7

Algorithme de Dijkstra Pluscourtchemindansungraphepond´ere´

On continue le mˆeme algorithme jusqu’`a avoir vid´e le tas : on extrait 7.

0 5 5 1 1 2 3 4 5 6 7 8 1 4  3 4 5 d 5 4 6 1 0 11 6 1 8 1 1 6 8 3 ¼ 8 8 2 - 2 2 5 6 3 4 2 7 2 2 6 4 tas 11 3 7 11 6 1 6

Algorithme de Dijkstra Pluscourtchemindansungraphepond´er´e On continue le mˆeme algorithme jusqu’`a avoir vid´e le tas : on extrait 3 et on ins`ere 4  onmet`ajourladistancede6.

0 5 5 1 1 2 3 4 5 6 7 8 1 4  3 7 4 5 d 5 4 6 7 0 10 6 1 8 1 1 6 8 3 ¼ 8 8 2 3 - 3 2 5 6 7 3 4 2 2 2 7 4 tas 10 4 7 1 10 6 6

Parcours en profondeur

Fonctionne comme le parcours en profondeur des arbres on descend au plus profond en premier, on veut  survivre  aux cycles  on colorie encore les sommets en blancs/gris/noirs

On descend au plus profond en premier :  pas de garantie de plus court chemin, on ne stocke pas la distance des sommets, a`laplaceonstockelesdatesded´ebut/findevisite.  on conserve une variable de temps t .

Algorithme de Dijkstra Pluscourtchemindansungraphepod´re´ n e ` A la fin on a un recouvrement repr´esentant les plus courts chemins de5a`touslesautressommetsdugraphe. La complexit´e de l’algorithme est Θ ( | A | × log | S | )

0 5 5 1 1 2 3 4 5 6 7 8 3 4 7 d 5 4 6 7 10 1 4 5 0 6 1 8 1 1 6 8 3 ¼ 8 8 2 3 - 3 2 5 6 3 4 2 7 2 2 4 7 1 10 6

Parcours en profondeur Algorithme

Initialisation en partant d’un sommet s : t = 0, π [ s ] = − ` A partir d’un sommet s :  colorier s en gris  t = t + 1, beg [ s ] = t  pour tout v voisin non-visit´e (colori´e en blanc) de s  π [ v ] = s  parcourir re´cursivement le graphe en profondeur en partant de v  colorier s en noir  t = t + 1, end [ s ] = t

Complexite´en O ( | A | ) pour un structure en liste de successeurs.