2) Parcours de graphes
Listes d'adjacence - liste d'adjacence
Ce nom est trompeur, mais trÚs souvent utilisé.
On appelle souvent "listes d'adjacence", ou mĂȘme "liste d'adjacence", le dictionnaire dont les clĂ©s
sont les sommets du graphes, et les valeurs les listes (parfois tuples) des voisins associés à chaque sommet.
I. Introduction : modĂ©liser un labyrintheâïž
Considérons les problÚmes suivants :
- Comment rechercher le chemin le plus court entre deux stations dans le métro? Indépendamment de l'aspect ludique, c'est en fait un problÚme difficile qu'on aurait bien du mal à résoudre de façon raisonnable sur un gros graphe comme celui du métro.
- Comment trouver la sortie d'un labyrinthe?
Les labyrinthesâïž
Voici l'image d'un labyrinthe :
Ce labyrinthe peut ĂȘtre reprĂ©sentĂ© par le graphe suivant :
-
Chaque sommet du graphe correspond Ă une case du labyrinthe
-
une arĂȘte relie 2 cases voisines quand le passage est possible.
-
Si une paroie empĂȘche de passer on ne met pas l'arĂȘte.
Par exemple il n'y a pas d'arĂȘte entre les sommets (1,1) et (1,2) mais il y en a une entre (1,1) et (2,1).
Les noeuds
A quoi correspondent les deux chiffres des noeuds de cette représentation ?
Solution
Le premier chiffre est un numéro de ligne, le deuxiÚme un numéro de colonne.
Nous allons représenter ce graphe par le dictionnaire suivant :
graphe = {11: [21], 12: [], 13: [23, 14], 14: [13, 15, 24], 15: [14, 25], 16: [26, 17], 17: [16, 18], 18: [17, 28],
21: [11, 22], 22: [21, 23, 32], 23: [22, 13], 24: [14, 34], 25: [15, 26], 26: [25, 16, 36, 27],
27: [37, 26], 28: [18, 38], 31: [], 32: [22, 42], 33: [], 34: [24, 35], 35: [34, 36],
36: [26, 35, 46, 37], 37: [27, 36, 47], 38: [28, 48], 41: [], 42: [32, 43], 43: [42, 44], 44: [43],
45: [46], 46: [36, 45], 47: [37, 48], 48: [47, 38]}
Dessiner ce graphe avec netwoks
Dessiner ce graphe avec graphviz
Créer un fichier png de ce graphe avec graphviz
RĂ©soudre ce labyrinthe
Ce labyrinthe est assez simple, et une fois sa représentation en graphe tracée comme ci-dessus, il semble assez facile de résoudre ce labyrinthe, c'est à dire de trouver un chemin qui permette d'aller d'une case "entrée" à une case "sortie".
Supposons que la case "entrée" soit la case (1,1) et la case sortie la case (4,8). Cela correspond respectivement aux noeuds 11 et 48. Observons le graphe précédent. On voit assez facilement plusieurs chemins possibles. En donner trois possibles.
Solution
- 11-21-22-23-13-14-15-25-26-16-17-18-28-38-48
- 11-21-22-23-13-14-24-34-35-36-37-47-48
- 11-21-22-23-13-14-24-34-35-36-26-16-17-18-28-38-48
Quels parcours ?
Nous voulons Ă©crire un script Python qui permette de rĂ©soudre automatiquement, dans le cas oĂč c'est possible, n'importe quel labyrinthe, mĂȘme trĂšs compliquĂ©.
Pour cela on peut penser parcourir le graphe en partant de l'entrée, en suivant différents chemins, jusqu'à atteindre le sommet de sortie.
Plusieurs algorithmes "classiques" permettent de parcourir les graphes. Nous allons commencer par les étudier, puis nous essaierons de résoudre ce problÚme en choisissant l'algorithme le plus adapté à cette situation.
II. Les parcours de graphesâïž
Contrairement aux arbres, les graphes nâont pas de racine, de « dĂ©but ». On peut donc choisir nâimporte quel sommet pour commencer le parcours. Ceci dit, le parcours de certains graphes orientĂ©s demande un choix de sommet de dĂ©but rĂ©flĂ©chi.
đ La vidĂ©o suivante explique le principe des parcours. Pour bien justifier l'utilisation de la pile, la premiĂšre Ă©tape du premier parcours prĂ©sentĂ© n'est pas tout Ă fait celle du parcours en profondeur que nous verrons au IV.
A retenir
- Parcours en largeur : File
- Pacours en profondeur : Pile
III. Le parcours en largeurâïž
Parcours en largeur
parcours est la liste vide qui contiendra les sommets visités par parcours en largeur
F est une file vide
On enfile un sommet dans F
Tant que F n'est pas vide
S = TĂȘte de F
On défile F et on ajoute le sommet dans parcours
On enfile les voisins de S qui ne sont ni dans la file ni dans parcours
Fin Tant Que
đ 9 Ă©tapes :
Question
Ecrire le code d'une fonction parcours_en_largeur qui parcourt en largeur un graphe Ă partir du sommet depart et dont
sa liste d'adjacence est representée par un dictionnaire nommé graphe.
Cette fonction renverra la liste des sommets parcourus en partant du sommet depart.
Compléter le script ci-dessous :
Graphe du test :
Optimisation
Le coût d'une recherche dans une liste (pour tester si un sommet a déjà été visité) est beaucoup plus important que le coût de la recherche dans un ensemble (hors programme NSI), ou dans un dictionnaire. ( Les tables de hash)
Nous allons donc proposer une autre version pour améliorer l'efficacité de l'algorithme.
- Un sommet est "parcouru" lorsqu'il a été mis dans la liste
parcours - Un sommet est "en attente" lorqu'il est dans la file.
- Tous les autres sommets sont "pas vu".
Compléter le script suivant :
# Tests (insensible Ă la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)
Distances croissantes
On peut remarquer que l'algorithme de parcours en largeur permet de dresser la liste des sommets d'un graphe par distance croissante au sommet d'origine
A partir du sommet A représenté en bleu,on a par distance croissante :
- Les sommets à une distance de 1 du sommet A représentés en vert : B, D, E
- Les sommets à une distance de 2 du sommet A représentés en rouge : C, F, G
- Le sommet à une distance de 3 du sommet A représenté en jaune : H
On retrouve bien dans la liste renvoyée par la fonction de parcours en largeur à partir du sommet A les sommets classés par ordre de distance croissante au sommet A : ['A', 'B', 'D', 'E', 'C', 'F', 'G', 'H'].
Note
đĄ On peut se servir du parcours en largeur pour trouver un chemin de distance minimale entre deux sommets.
IV. Le parcours en profondeurâïž
1. Le parcours en profondeur rĂ©cursifâïž
Une premiĂšre approcheâïž
Parcours en profondeur
Parcours en profondeur ou DFS en anglais pour Depth First Search
Le parcours en profondeur est un parcours oĂč on va aller «le plus loin possible» sans se prĂ©occuper dans un premier temps des autres voisins non visitĂ©s :
On va visiter le premier des voisins du sommet non traitĂ©s, puis faire de mĂȘme avec lui (visiter le premier de ses voisins non traitĂ©s), etc. Lorsqu'il n'y a plus de voisin, on revient en arriĂšre pour aller voir le dernier voisin non visitĂ©.
Dans un labyrinthe, ce parcours s'explique trÚs bien : on prend par exemple tous les chemins sur la droite jusqu'à rencontrer un mur, auquel cas on revient au dernier embranchement et on prend un autre chemin, puis on repart à droite, etc. Attention, pour ne pas tourner en rond autour d'un bloc, il faut marquer les endroits par lesquels on est déjà passés.
C'est un parcours qui s'écrit naturellement de maniÚre récursive.
Méthode récursive
Lâensemble des sommets dĂ©jĂ visitĂ©s est stockĂ© dans un objet Python (liste, ou dictionnaire, ou ensemble).
La visite est relancée récursivement pour chaque voisin du sommet visité qui n'a pas déjà été visité.
A vous
Compléter le code de la fonction parcours_profondeur qui parcourt en profondeur un graphe à partir du sommet sommet
et dont sa liste d'adjacence est representée par un dictionnaire nommé graphe.
Cette fonction renverra la liste des sommets parcourus en partant du sommet depart.
đ” Il peut falloir plusieurs lignes de code pour remplacer les ...
Graphe du test :
# Tests (insensible Ă la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)
return ou pas return ?
Testons sur le graphe suivant :
graph LR
A --- B
B --- E
A --- CSans return pour l'appel récursif de la fonction
Avec return pour l'appel récursif de la fonction
Que s'est-il passé ?
Solution
Le return devant l'appel rĂ©cursif empĂȘche de remonter au sommet A, pour explorer la branche suivante.
On est coincé dans un cul de sac.
Optimisationâïž
Optimisation
Le coût d'une recherche dans une liste (pour tester si un sommet a déjà été visité) est beaucoup plus important que le coût de la recherche dans un ensemble (hors programme NSI), ou dans un dictionnaire.
Nous allons donc proposer une autre version pour améliorer l'efficacité de l'algorithme.
A vous
Compléter le script.
Graphe du test :
# Tests (insensible Ă la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)
Autre possibilité
On peut aussi construire le parcours par concaténation de listes.
Tester ci-dessous :
# Tests (insensible Ă la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)
Visualiser l'exécution
Vous pouvez voir l'exécution avec le graphe suivant ici :
graph LR
A --- B
A --- C
C --- D
D --- E
C --- F
F --- E2. Le parcours en profondeur itĂ©ratifâïž
Une premiĂšre approcheâïž
Algorithme itératif avec une pile
Comme nous l'avons vu dans la vidéo, on peut aussi utiliser une pile.
â A noter ... et Ă mĂ©moriser ... đ
parcours est la liste vide qui contiendra les sommets visités par parcours en profondeur
P est une pile vide
On empile un sommet dans P
Tant que P n'est pas vide
S = dépile(P)
On ajoute S Ă parcours
On empile les voisins de S qui ne sont ni dans la pile ni dans parcours
Fin Tant Que
đ 9 Ă©tapes :
A vous
Ecrire le code d'une fonction parcours_en_profondeur qui parcourt en profondeur un graphe Ă partir du sommet depart
et dont sa liste d'adjacence est representée par un dictionnaire nommé graphe
Cette fonction renverra la liste des sommets parcourus en partant du sommet depart.
Compléter le script ci-dessous de façon itérative :
Graphe du test :
# Tests (insensible Ă la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)
DiffĂ©rents parcours en profondeur ?âïž
Il y a souvent plusieurs possibilités
Observez les résultats obtenus pour le parcours en profondeur par algorithme récursif, ou itératif.
đ” Les parcours obtenus sont diffĂ©rents. De plus, suivant l'ordre des listes d'adjacences, on obtiendra aussi des rĂ©sultats de parcours diffĂ©rents.
đČ Dans la vidĂ©o d'introduction, on Ă©tait amenĂ© Ă faire des choix arbitraires.
Optimisationâïž
Optimisation
Le coût d'une recherche dans une liste (pour tester si un sommet a déjà été visité) est beaucoup plus important que le coût de la recherche dans un ensemble (hors programme NSI), ou dans un dictionnaire.
Nous allons donc proposer une autre version pour améliorer l'efficacité de l'algorithme.
A vous
- Un sommet est "parcouru" lorsqu'il a été mis dans la liste
parcours - Un sommet est "en attente" lorqu'il est dans la pile.
- Tous les autres sommets sont "pas vu".
Graphe du test :
# Tests (insensible Ă la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)
V. Bilanâïž
A retenir
-
Dans le parcours en largeur, on visite tous les sommets en «cercle concentriques» autour du sommet de dĂ©part : dâabord les voisins directs, puis les voisins des voisins directs etc, et on continue jusquâĂ ce quâil nây ait plus de sommets Ă visiter.
đ On utilise une file. -
Le parcours en profondeur dâun graphe Ă partir dâun sommet consiste Ă suivre les arĂȘtes arbitrairement, en marquant les sommets dĂ©jĂ visitĂ©s pour ne pas les visiter Ă nouveau. On avance le plus possible et on recule quand on est bloquĂ©.
đ On utilise un algorithme rĂ©cursif, ou une pile.
VI. Le labyrintheâïž
TP : résolution d'un labyrinthe
AprÚs avoir téléchargé le fichier, vous pourrez le lire à partir de Basthon
đ TD Ă tĂ©lĂ©charger : Fichier TP_resolution_labyrinthe_sujet.ipynb : "Clic droit", puis "Enregistrer la cible du lien sous"
đ La correction est arrivĂ©e :
đ Fichier TP_resolution_labyrinthe_corr.ipynb : "Clic droit", puis "Enregistrer la cible du lien sous"
VII. Remarqueâïž
Retour sur l'efficacité
đ” ma_liste.pop(0)
Pour une question de simplification des codes, Nous avons souvent utilisé ma_liste.pop(0)
Ce n'est pas une façon efficace de procéder, car le temps d'exécution est proportionnel à la taille de la liste ma_liste
Recopier dans votre éditeur Python (pas sur Basthon) le script suivant, puis l'exécuter :
import timeit
import matplotlib.pyplot as plt
def suppression_debut(lst):
lst.pop(0)
# différentes tailles de listes notées n dans la suite
abscisse = [(10**7)*i for i in range(1, 11)]
print(abscisse)
ordonnee = []
for n in abscisse:
temps = 0
for i in range(2):
ma_liste = [0]*n # Création de liste de tailles n
# Le chronométrage étant fait 2 fois, Il faut donc pour chaque mesure reprendre la liste initiale
temps += timeit.timeit("suppression_debut(ma_liste)", number=1, globals=globals())
ordonnee.append(temps)
# Graphique
plt.plot(abscisse, ordonnee, "ro") # en rouge
plt.show()
plt.close()
Résumé
đ Pour pallier Ă ce problĂšme, nous pouvons utiliser le deque du module collections
đŽ ma_liste.pop()
Recopier dans votre éditeur Python (pas sur Basthon) le script suivant, puis l'exécuter :
import timeit
import matplotlib.pyplot as plt
def suppression_fin(lst):
lst.pop()
# différentes tailles de listes notées n dans la suite
abscisse = [(10**7)*i for i in range(1, 11)]
print(abscisse)
ordonnee = []
for n in abscisse:
temps = 0
for i in range(2):
ma_liste = [0]*n # Création de liste de tailles n ne contenant que des 0
# Le chronométrage étant fait 2 fois, Il faut donc pour chaque mesure reprendre la liste initiale
temps += timeit.timeit("suppression_fin(ma_liste)", number=1, globals=globals())
ordonnee.append(temps)
# Graphique
plt.plot(abscisse, ordonnee, "go") # en vert
plt.show()
plt.close()
Résumé
Nous observons que ma_liste.pop() est beaucoup plus rapide que ma_list.pop(0). En effet, pour supprimer le premier élément d'une liste,
il faut tous les décaler d'un rang vers la gauche, alors que pour supprimer le dernier élément d'une liste, il suffit ... de supprimer
le dernier Ă©lĂ©ment de la liste đ
.
Voici les résultats obtenus par les deux méthodes pour 100 mesures (il faut plus de 10 minutes pour créer cette image)
- Les listes ont des tailles allant de \(1 \times 10^7\) Ă \(10 \times 10^7 = 10^8\)
- Les résultats sont exprimés en secondes
VIII. CrĂ©ditsâïž
Romain Janvier, Gilles Lassus, Hugues Malherbe, Nicolas Revéret, Jean-Louis Thirot.
# Tests(insensible Ă la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)