Informatique -- Tronc Commun
TD 9 -- Parcours en profondeur : labyrinthes
Laurent Mauborgne, Dominique Rossin
23 janvier 2001
Le parcours en profondeur permet d'explorer un graphe en suivant ses arêtes.
Il est bien adapté à la recherche de chemins dans un graphe représenté par
listes de successeurs. On peut par exemple l'utiliser pour rechercher la
sortie d'un labyrinthe. Le but de ce TD sera non seulement de trouver une
sortie dans un labyrinthe, mais aussi d'utiliser un parcours en profondeur
aléatoire pour créer un joli labyrinthe ayant forcément une sortie.
1 Les labyrinthes
Les labyrinthes que nous allons construire auront l'aspect suivant :
Les labyrinthes sont donc constitués de noeuds identifiés par leurs coordonnées
et ayant au plus quatre voisins. Il est donc tout à fait logique de représenter
ces graphes par des listes de successeurs, et non par des matrices d'adjacence.
1.1 Structure de donnée
On propose de représenter un labyrinthe par un tableau de listes de successeurs,
tel qu'aux coordonnées i, j du tableau on ait les successeurs du
noeud i, j. Pour faciliter certains algorithmes, on pourra
utiliser un tableau avec une ligne de plus en haut et en bas et une colonne de
plus à gauche et à droite. Ainsi, pour un labyrinthe de taille nxm,
le noeud en haut à gauche sera aux coordonnées 1,1, en bas à droite,
n,m et le tableau sera de taille (n+2)x(m+2).
Ecrivez le type de donnée des listes de successeurs.
1.2 Labyrinthe aléatoire
Une façon simple de créer un labyrinthe aléatoire est de considérer au départ
un labyrinthe rempli de murs (aucun lien entre les cases), et de tirer au
hasard pour chaque mur entre les cases N et M pour savoir si
on doit rajouter un lien entre N et M. Il suffit pour cela
de comparer Math.random() à un nombre entre 0 et 1. Notez qu'à
chaque fois qu'on ajoute un lien entre N et M, il faut aussi
ajouter un lien entre M et N.
Le seul problème consiste à ne faire qu'un seul tirage par mur. Si on fait
un tirage pour chacun des quatre murs entourant une case, chaque mur sera
testé deux fois. Pour éviter cela, on peut par exemple ne tester que les
murs de droite et du bas.
Ecrivez un constructeur pour les labyrinthes qui crée un labyrinthe
aléatoire en tirant au hasard les liens entre les cases. Le constructeur
prendra en argument la taille du labyrinthe et un seuil.
1.3 Affichage
Ecrivez une fonction d'affichage du labyrinthe. On pourra utiliser les
procédures incomplètes fournies.
2 Trouver la sortie
On considère que l'entrée des labyrinthes se situe en haut à gauche, et la
sortie en bas à droite. Nous allons donc chercher la sortie en utilisant un
parcours en profondeur. Le parcours en profondeur est plus facile à écrire
récursivement : on regarde si le noeud N est le noeud de sortie.
Si oui, on termine la recherche, si non, pour tous les voisins de N
qui n'ont pas été visités, on fait le parcours en profondeur, jusqu'à ce que
l'un d'entre eux trouve la sortie.
Pour savoir si un noeud a déjà été visité, on pourra utiliser un tableau de
booléens que l'on met à jour au fur et à mesure du parcours. Pour savoir si
le parcours en profondeur d'un voisin a trouvé la sortie, il faudra que le
parcours retourne une valeur booléenne.
Ecrivez un programme qui recherche la sortie en partant du coin en haut à
gauche par un parcours en profondeur. Le programme pourra afficher le chemin
parcouru en utilisant la procédure dessine_chemin fournie.
3 Faire un joli labyrinthe
Les labyrinthes créés en tirant les murs au hasard ne sont pas jolis :
on a des grands vides, la sortie n'est pas forcément accessible... Il est
possible de créer de beaux labyrinthes tels qu'il existe un chemin entre tous
les points du labyrinthe en adaptant un peu l'algorithme précédent.
L'algorithme est le suivant : on considère le graphe constitué des
cases du labyrinthe toutes reliées à leur quatre voisines. On fait un parcours
en profondeur de ce graphe qui visite toutes les cases du labyrinthe (il ne
s'arrête pas à une éventuelle sortie). Les chemins du labyrinthe seront alors
exactement les chemins du parcours en profondeur.
Notez bien que nous avons deux graphes : le graphe dont toutes les cases
sont reliées à leur quatre voisines, pour lequel nous n'avons donc pas besoin
de listes de successeurs explicites, et le graphe correspondant au labyrinthe
que l'on crée, pour lequel nous allons petit à petit construire des listes
de successeurs.
3.1 Permutations aléatoires
Pour que le parcours soit aléatoire, il faudra que l'ordre de visite des
voisins d'un noeud soit déterminé aléatoirement. Comme chaque noeud a quatre
voisins, cela revient à déterminer une permutation aléatoire de ces quatre
voisins. Pour cela, on pourra utiliser un tableau de taille 4, initialement
vide. On tire un nombre entier entre 0 et 3 pour placer le voisin de droite
dans le tableau, puis un nombre entier entre 0 et 2 pour placer le voisin du
bas dans le tableau, puis un nombre entier entre 0 et 1 pour placer le voisin
de gauche, et enfin
on place le voisin du haut dans la dernière case libre du tableau. Pour
placer un voisin à la place i dans un tableau déjà partiellement
rempli, on parcourt le tableau en ignorant les cases remplies.
Ecrivez une fonction qui prend un tableau de voisins partiellement rempli
et une position i, et retourne la case vide numéro i du tableau.
Ecrivez une fonction qui retourne une liste aléatoire de voisins d'une
case.
3.2 Parcours en profondeur et création du labyrinthe
Pour ne pas avoir de cas particulier à tester au bord du labyrinthe, il faudra
commencer par marquer comme visités les lignes et colonnes qui bordent le
tableau représentant le labyrinthe. Il s'agit des lignes et colonnes 0 et
taille du labyrinthe +1. Ensuite, on fait un parcours en profondeur
partant de n'importe quelle case (entre 1 et taille du labyrinthe). Dans ce
parcours en profondeur, on utilise la liste de voisins dont l'ordre est
aléatoire, et si un voisin n'a pas déjà été visité, on rajoute le lien
dans le labyrinthe que l'on crée et on appelle récursivement la procédure sur ce
voisin. Notez que cette fonction n'a pas besoin de renvoyer de valeur.
Ecrivez une fonction de création de labyrinthe utilisant un parcours en
profondeur aléatoire du graphe sous-jacent. Affichez-le.