Algorithmique de graphes : Labyrinthes

par Pascal Vanier

Téléchargez l'archive labyrinthes.zip qui contient le code à compléter.

Qu'est-ce qu'un graphe

Un graphe est une structure de donnée permettant de représenter des "relations" entre des objets. Par exemple, imaginons que l'on veuille représenter les relations entre les copies de 5 étudiants : Alice, Bob, Charles, Denis et Ève :

Alice a copié sur Bob (mais elle a fait l'exercice 1 toute seule!),
Bob a copié sur Ève,
Ève a copié l'exercice 1 sur Alice,
Denis a copié sur Charles,
Charles a travaillé seul (mais avait envie de faire plaisir à Denis, il l'a laissé copier).

On peut représenter les relations de triche de manière visuelle : chaque élève est représenté par un noeud et la relation "a copié sur" par une flèche :

Un graphe est un couple $(V,E)$, où $V$ est l'ensemble des sommets (aussi appelés noeuds) et $E\subseteq V\times V$ est l'ensemble des arêtes.

Un graphe peut être orienté ou non orienté, dans le second cas, si $(x,y)\in E$, alors $(y,x)\in E$.

Il y a deux manières de représenter un graphe :

à l'aide de la matrice d'ajdacence, si l'on numérote les noeuds de $1$ à $n$, la case $(i,j)$ de la matrice contient le nombre d'arêtes entre le noeud $i$ et le noeud $j$. Le principal avantage de cette représentation est que $A^n$ contient alors le nombre de chemins de longueur $n$ entre les différents noeuds.
à l'aide de listes d'adjacence : le graphe est représenté plusieurs listes chaînées, une pour chaque noeud, contenant chacune la liste de ses voisins (pour le noeud $u$, la liste contient l'ensemble $\{ v\mid (u,v)\in E\}$).

Complétez la classe Graphe du fichier graphe.py. Vous utiliserez un dictionnaire pour stocker les listes chaînées.

Utiliser des dictionnaires nous permet d'avoir des noeuds qui ne sont pas forcément représentés par des entiers, toute valeur hachable (vous avez normalement vu les tables de hachage hier). En python, cela peut être par exemple un entier, une chaîne de caractères, un couple, un flottant, ou plus généralement, tout objet qui a une méthode __hash__.

Vous pourrez tester votre code avec la matrice d'adjacence suivante :

m = [[ 0, 1, 0, 0, 0],
     [ 0, 0, 0, 0, 1],
     [ 0, 0, 0, 0, 0],
     [ 0, 0, 1, 0, 0],
     [ 1, 0, 0, 0, 0]]

Quelle est la quantité d'information stockée dans les listes d'adjacence et dans la matrice d'adjacence ? Plus généralement, à quels cas sont adaptés chaque représentation ?

Algorithmes de graphes

Pour illustrer l'utilité des algorithmes de graphes, nous allons utiliser des labyrinthes. Notre première tâche va donc être de créer des labyrinthes.

Génération de labyrinthes

Une grille régulière

Pour générer nos labyrinthes, nous allons commencer par générer un graphe (non orienté) représentant une grille de sommets isolés.

Chaque sommet aura comme nom le couple $(i,j)$ représentant sa position dans la grille.

Modifiez le constructeur de la classe Labyrinthe afin que le graphe g contienne une grille de sommets isolés de hauteur hauteur et de largeur largeur. On fera bien attention à utiliser des couples $(i,j)$ comme noms de sommets.

Affichage

Nous allons maintenant écrire une fonction d'affichage de notre labyrinthe (qui n'en est pas encore vraiment un). Pour cela, nous allons utiliser des dièses "#" pour représenter les murs et des espaces " " pour représenter les noeuds et arêtes entre les noeuds.

Un graphe de hauteur $h$ et de largeur $l$ sera représenté par une chaine de caractères de hauteur $2h+1$ et de largeur $2l+1$. Les caractères sur les bords seront toujours des #. Chaque sommet $(i,j)$ sera représenté par le caractère à la position $(2i+1,2j+1)$, ces positions contiendront toujours un espace.

Une arête entre $(i,j)$ et $(i+1,j)$ sera représentée par un espace à la position $(2i+2,2j+1)$ et une arête entre $(i,j)$ et $(i,j+1)$ sera représentée par un espace à la position $(2i+1,2j+2)$.

Compléter la méthode __str__ de la classe Labyrinthe, afin qu'elle renvoie la chaîne de caractère que l'on vient de décrire. On utilisera des retours à la ligne \n pour changer de ligne.

Le résultat attendu pour la "grille" de hauteur $h=3$ et de largeur $l=6$ (print(Labyrinthe(6,3))) est le suivant :


#############
#.#.#.#.#.#.#
#############
#.#.#.#.#.#.#
#############
#.#.#.#.#.#.#
#############

La grille, c'est fini

Le "labyrinthe" que nous venons de générer n'est pas très intéressant, nous allons donc ajouter des passages entre les différentes "pièces" (nos noeuds). L'algorithme sera le suivant :

On génère une liste aléatoire tous les murs séparant les sommets du graphe (les arêtes entre $(i,j)$ et $(i+1,j)$, $(i,j+1)$), par exemple avec random.shuffle après avoir constitué la liste de toutes les arêtes.
Pour chaque arête de la liste, on vérifie si les deux sommets qu'elle relie sont déjà dans la même composante connexe :
1. Si oui, on oublie l'arête et on passe à l'arête suivante.
2. Si non, on ajoute l'arête au graphe.
L'algorithme s'arrête quand il n'y a plus d'arêtes dans la liste.

L'algorithme présenté ainsi est plutôt simple, cependant la vérification à l'étape 2 est plus subtile qu'il ne peut y paraître. Pour cela on va utiliser une structure de donnée appelée Union-Find qui permet des classes d'équivalence (c'est à dire des ensembles d'objets équivalents) :

find(u) trouve le représentant u. Deux objets sont équivalents si leur représentant est égal.
union(u,v) fait l'union des classes d'équivalence de u et v, c'est à dire que les objets équivalents à u ou à v ont maintenant tous le même représentant (find(u)==find(v)) à partir de maintenant.

Implémentez l'algorithme que l'on vient de décrire. Vous pourrez utiliser la classe UnionFind dont le code vous est donné pour faire l'étape 2 : quand on ajoute une arête (u,v) au graphe, on fait union(u,v), pour vérifier que deux sommets u et v sont dans la même composante connexe il suffit alors de vérifier que find(u)==find(v).

L'algorithme que nous venons d'implémenter est une variante de l'algorithme de Kruskal qui sert à trouver un arbre couvrant de poids minimal sur un graphe dont les arêtes ont des poids. La seule différence est l'étape 1 : au lieu de trier aléatoirement les arêtes comme on l'a fait, on les trie en fonction de leur poids.

Générez plusieurs labyrinthes et affichez les.

(Bonus) Ajouter des passages

Le labyrinthe que nous venons de générer correspond en fait à un arbre, étant donné que l'algorithme utilisé est une variante de l'algorithme de Kruskal. Si l'on souhaite que celui-ci ne soit pas toujours un arbre, on peut ajouter des passages de manière aléatoire.

Pour faire cela, on peut décider à l'étape 2.1 de l'algorithme de création de labyrinthe, d'ajouter de temps en temps, aléatoirement une arête au lieu de l'oublier.

Implémentez ce changement de l'algorithme : si l'argument bouclitude du constructeur est à une valeur autre que None (valeur entre 0 et 1), alors on ajoute l'arête avec probabilité bouclitude au lieu de ne pas l'ajouter systématiquement.

Voici un exemple de labyrinthe généré par Labyrinthe(10,20,bouclitude=.20).


█████████████████████████████████████████
█               █ █         █ █   █     █
█ █ █████ █ █ █ █ █ █ ███ █ █ █ █ █ █ █ █
█   █     █ █ █           █ █   █ █     █
███ ███ ███ █ █ █ █████ ███ █ ███ █████ █
█   █       █ █ █       █   █   █ █ █   █
█ █████ █ █████ █ ███ ███ ███ ███ █ █ █ █
█ █     █       █ █           █         █
███ █ ███████ ███ ███ ███ █████ ███ ███ █
█     █   █   █ █     █ █ █             █
█ ███ ███ █ ███ █ █ █ █ █ ███████ █ ███ █
█         █     █ █ █   █ █     █ █   █ █
█ █ ███ █ █ █ █ █ ███ █ █ █████ █ ███████
█       █   █       █ █ █ █     █ █   █ █
███ █ ███ █ █ ███ ███████ █ ███ ███ ███ █
█ █   █   █   █ █ █ █ █     █ █ █       █
█ █ ███████ █ █ █ █ █ ███ ███ █ █ █ █ ███
█ █ █                     █   █   █   █ █
█ █ █████ ███ █ ███ ███ █ ███ █ █ ███ █ █
█       █     █ █           █   █   █   █
█████████████████████████████████████████

Plus court chemin : parcours en largeur

On souhaite maintenant trouver le plus court chemin entre l'entrée, le sommet en haut à gauche, et la sortie, le sommet en bas à droite.

Pour faire cela, on va utiliser un parcours en largeur (BFS : Breadth First Search). L'idée est de partir d'un sommet et de trouver ses voisins, ceux-ci seront les prochains qui seront visités, une fois que l'on a visité ses voisins, on passe au voisins de ses voisins et ainsi de suite. Bien entendu, à chaque étape, on ne visite que les sommets que l'on a pas encore visités.

Plus formellement l'algorithme se déroule de la manière suivante :

Pour chaque sommet $s\in V$ on initialise deux tableaux ou dictionnaires :
1. $dist[s]=\infty$, qui contiendra le longueur du plus court chemin vers $s_0$
2. $prec[s]$ est indéfini, mais contiendra le prédécesseur de $s$ dans le plus court chemin vers $s_0$.
$dist[s_0]=0$
On initialise une file $F$ qui contient uniquement $s_0$.
Tant que $F$ n'est pas vide :
1. On prend $s$ le premier sommet de la file.
2. Pour chacun de ses voisins $v$, si $dist[s]+1\lt dist[v]$ alors :
  1. $dist[v]=dist[s]+1$.
  2. $pred[v]=s$
  3. on ajoute $v$ à $F$.

La longueur du plus court chemin entre $s_0$ et $s$ est dans $dist[s]$ à la fin de l'exécution de l'algorithme, et le plus court chemin peut être retrouvé en suivant la liste chaînée formée par $pred[s]$ jusqu'à tomber sur $s_0$.

Implémentez la méthode pcc(self,u,v) de la classe Graphe qui devra retourner un couple (l,c) où l est la liste des sommets, dans l'ordre, du plus court chemin entre u et v et l sa longueur. On pourra utiliser queue.SimpleQueue de la librairie standard de python pour implémenter la file.

Vous pouvez tester votre algorithme sur le graphe suivant (donné sous forme de matrice d'adjacence):


g = [[0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0], [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0]]

Le plus court chemin attendu est le suivant : ([0, 7, 28, 3, 2, 12], 5).

Sur le graphe suivant, le résultat attendu est ([0, 28, 8, 26, 17, 11, 10, 5, 31, 13, 12], 10) :


g = [[0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]

Donnez la complexité de cet algorithme en fonction du nombre d'arêtes et/ou de noeuds.

Implémentez la méthode solution(self) qui trouve le plus court chemin entre le pièce $(0,0)$ et la pièce $(l-1,h-1)$ du labyrinthe.

Cet algorithme de parcours est appelé parcours en largeur parce que les sommets sont parcourus dans l'ordre en cercles concentriques en partant du sommet de départ. Le parcours en profondeur est basé sur une stratégie différente : pour chaque sommet on explore son premier voisin, puis on explore le premier voisin de celui-ci jusqu'à arriver à un cul-de-sac, on revient alors au dernier choix de voisin possible et ainsi de suite.

L'implémentation est quasiment identique : il suffit de remplacer la file par une pile.

Chemins coûtants

Deux chemins de même langueur dans notre graphe étaient jusqu'à présent équivalents, on va maintenant ajouter une notion de coût à nos arêtes. On peut pour cela imaginer que certains chemins entre les différentes "pièces" (les noeuds) de notre labyrinthe sont plus difficiles à traverser que d'autres :

Un chemin normal a un coût de 1.
Certains chemins contiennent des éboulis, dans ce cas, ils ont un coût de 2.
Certains chemins contiennent des monstres, dans ce cas, ils ont un coût de 5.

On va donc modifier notre classe Graphe afin qu'elle puisse contenir des coûts en plus des arêtes. Un graphe qui contient des coûts est appelé un graphe pondéré.

Un graphe pondéré est un triplet $(V,E,\delta)$, $\delta:E\to \mathbb{R}^+$ est appelée la fonction de coût.

Sur un graphe pondéré, au lieu de chercher le chemin le plus court en terme de nombre d'arêtes, on est intéressé par le chemin de poids minimum.

La fonction $\delta$ est parfois définie de $E\to\mathbb{R}$ certains algorithmes ne fonctionnent plus dans ce cas : en particulier, lorsqu'un cycle de valeur négative est trouvé il peut ne pas y avoir de chemin de poids minimum entre deux sommets, mais une infinité de chemins de poids décroissants.

Modifiez la classe Graphe pour y ajouter les coûts des arêtes. On pourra utiliser un dictionnaire dont les clefs seront les arêtes et les valeurs les poids. On ajoutera également une méthode poids(self,u,v) qui renverra le poids de l'arête $(u,v)$. On modifiera la méthode ajouter_arete de manière à ce que si aucun poids n'a été spécifié, le poids soit de 1 par défaut.

Maintenant que l'on a une classe graphe permettant d'avoir des poids sur les arêtes, il faut modifier notre algorithme de génération de labyrinthes pour que celui-ci ajoute des poids.

Ajoutez la pondération des arêtes au constructeur de la classe Labyrinthe, on pourra ajouter un argument optionnel poids pour l'activer/désactiver. Lors de l'ajout d'une arête :

avec probabilité $.2$, le poids sera de 2.
avec probabilité $.07$, le poids sera de 5.
sinon, le poids sera de 1.

Modifiez la fonction d'affichage du labyrinthe pour que celle-ci affiche les différents obstacles : un "." pour un éboulis, et un "@" pour un monstre.

Voici un exemple de labyrinthe avec des obstacles


█████████████████████████████████████████
█     █     █         █ █ . █ █         █
█ ███ ███ █████ █████ █.█ ███ ███.█████ █
█   █ █         █ . █     @ █     @ @   █
█ ███ █ █ █ █ █ █ █ █ █ ███ █████ █ █ ███
█           █   █ █   █   █   .   . █ . █
█.█ █████████████████ ███ ███ ███████@███
█ █     . █         @ @ █   . █         █
█.█.█ ███@███.███ █.███ █ █ █████ █ ███ █
█   █ █     . █ █ █ █ @   █ █ .         █
███ █ █@█ █ █ █ ███ ███ █.█ ███████@███.█
█   █ █   █ █ . █ . @   █ █         █   █
█ ███ █ ███ █@███ █ █ █████.█ █ ███ █████
█       █     █ █ █ █ █ . @       . .   █
█.█ ███.███ █ █ ███.█ █ █████ █ ███ ███.█
█   █ █ █ █ █           █ █   @   . . . █
███ █ ███ █ ███ ███ █@█.█ █████ ███.█@█.█
█ █       █ . █       █ @   █     █   █ █
█ █.█.███ █ █████ ███ █ █ █ █████@█ █ █ █
█   . . . █     .     █   █     █       █
█████████████████████████████████████████

L'algorithme de parcours en largeur tel qu'implémenté précedemment ne permet pas directement d'obtenir le chemin de poids minimum. L'algorithme de dijkstra est une variante du parcours en largeur permettant de faire cela. La principale différence entre les deux est l'utilisation d'une file de priorité, une file dans laquelle chacun des éléments a un poids et où l'élément que l'on récupère à chaque extraction est celui de poids minimal.

Les deux étapes qui diffèrent sont donc les suivantes :

L'initialisation de la file : on initialise la file avec $s_0$ de poids 0.
L'étape 4.2.1 : on doit remplacer 1 par le poids de l'arête considérée, on teste donc si $dist[s]+\delta(s,v)\lt dist[v]$ et la mise à jour éventuelle ajoute le poids : $dist[v] = dist[s] + \delta(s,v)$.

Modifiez la méthode pcc afin qu'elle prenne en compte les poids. Pour cela on pourra utiliser le module heapq de python, on pourra utiliser un couple (poids,valeur).

Quelle est la complexité de cet algorithme ? Attention, celle-ci dépend de celle de la file de priorité utilisée.

Si vous le souhaitez, implémentez une méthode str_pcc(self) dans la classe Labyrinthe qui le labyrinthe avec le chemin le plus court entre la case en haut à droite et la case en bas à gauche à l'intérieur du labyrinthe (on pourra par exemple utiliser un nouveau caractère * ou bien les couleurs du terminal si vous êtes sous linux.