TD-7, Sortir du labyrinthe




Ce document est disponible à l'URL http://www.enseignement.polytechnique.fr/profs/informatique/Luc.Maranget/TC/TD-7

Envoyez vos programmes à Luc.Maranget@inria.fr. Les solutions sont ici.

1 Labyrinthes

1.1 Principe
Le TD de cette semaine porte sur l'étude des chemins dans un graphe. Pour faire plus amusant, ces graphes représentent des labyrinthes.

Un labyrinthe, composé de hauteur × largeur cases numérotées par des couples (i,j), est représenté en machine par un graphe (non orienté) dont les sommets sont étiquetés par des couples (i, j). Lorsqu'une case (i0, j0) communique avec une autre case (i1, j1), alors il existe un arc entre les sommets (i0, j0) et (i1, j1) du graphe. En outre, deux cases (et sommets) sont particuliers, ce sont l'entrée et la sortie du labyrinthe. Soit le labyrinthe suivant : 
+-+-+-+-+-+-+-+-+
|I| |     |     |
+ +-+ + + + +-+ +
|     | |     | |
+-+ +-+ +-+ + + +
| | | |       | |
+-+ +-+-+-+ + + +
| |     |   |  O|
+-+-+-+-+-+-+-+-+
Il est le graphe (non-orienté) :
Aller de l'entrée vers la sortie du labyrinthe revient donc à trouver un chemin dans le graphe d'un sommet vers un autre.

1.2 Implémentation
Afin que vous puissiez vous concentrer sur la programmation du parcours, le type des labyrinthes, ainsi que les fonctions d'entrée/sortie sont donnés.

Un sommet du graphe (une case du labyrinthe) est un objet de la classe Sommet : 
class Sommet {
  int i,j;

  Sommet (int i, int j) {
    this.i = i;
    this.j = j;
  }

  public boolean equals(Sommet s) {
    if (s == null)
      return false;
    else
      return (i == s.i && j == s.j);
  }

  public String toString() {
    return ("<" + i + ", " + j + ">") ;
  }
}
Les sommets sont regroupés en listes, à l'aide de la classe ListeSommets qui est classique. Les graphes sont représentés en machine en utilisant la technique les listes de voisins. La classe Laby définit la représentation interne des graphes et fournit un constructeur. 
class Laby {

  int hauteur,largeur ;
  Sommet entree,sortie ;
  ListeSommets [] [] voisins ;

  Laby(BufferedReader in) {
    ...
  }
}
Les labyrinthes ont une représentation externe (dans un fichier) et une représentation interne (comme un objet de la classe Laby). Le constructeur de la classe Laby prend un flot d'entrée Reader en argument. Donc, vous lirez un labyrinthe donné dans l'entrée standard par : 
  laby = new Laby (new BufferedReader (new InputStreamReader(System.in))) ;
Le constructeur de la classe Laby fait tout le travail : initialisation des champs hauteur et largeur, de l'entrée, de la sortie et surtout du tableau des listes des voisins. On trouvera les voisins d'un sommet donné s en laby.voisins[s.i][s.j]. Ainsi dans le cas du petit labyrinthe, le début du tableau des voisins sera comme ceci :

On remarquera le graphe représenté est en fait orienté, toutefois il sera toujours non-orienté dans la pratique, c'est à dire que si il y a un passage entre les sommets s et s', alors s appartient à la liste des voisins de s' et s' appartient à la liste des voisins de s.

1.3 Animation Graphique
Grâce à une animation graphique, vous allez pourvoir visualiser les parcours. La classe AnimLaby exporte les méthodes suivante :
1.4 Un exemple
Pour clarifier un peu voici un exemple d'utilisation : la recherche de la sortie par un parcours en profondeur d'abord. Ensuite, lancer l'exemple : 
maranget@manche ~/TD/TD-7 > java Test seeneeseneesss < petit.laby
Félicitations, vous avez trouvé la sortie.
En même temps, le chemin spécifié est dessiné dans la fenêtre graphique, à l'aide de la méthode AnimLaby.fleche. Cela devrait suffire pour comprendre comment utiliser l'animation graphique.

2 Trouver la sortie
Écrire une classe idoine qui trouve toute seule et dessine un chemin de l'entrée à la sortie. Il peut s'agir de trouver un chemin (et alors un parcours en profondeur d'abord s'impose, comme étant le plus simple à programmer), ou de trouver le chemin le plus court (parcours en largeur d'abord, avec une file).

Dans les deux cas, exploiter au mieux l'animation graphique. Pour le parcours en profondeur d'abord, cela pourra donner l'animation suivante :


Cliquez sur Stop pour interrompre, sur Reload pour reprendre.

Dans le cas du parcours en largeur d'abord on pourra utliser la méthode AnimLaby.colorieFleche qui prend une couleur (un int) en argument supplémentaire, pour dessiner l'arbre de recouvrement minimal.
Cette fois ci les flèches occupant une case pointent vers le père de cette case dans l'arborescence des plus cours chemins. La couleur traduit la distance minimale d'une case à l'entreé. Dans la pratique cet arbre de recouvrement peut se calculer comme le tableau des pointeurs de chaque case vers son père.

Essayez aussi avec le grand labyrinthe. Solution. en profondeur d'abord et Solution. qui donne le plus court chemin.

3 Promenade
Une promenade ça prend du temps. Dans cet esprit on cherche à trouver un chemin de l'entrée vers la sortie le plus long possible.

Une première idée, est d'écrire un programme qui énumère (et affiche au passage) tous les chemins à partir de l'entrée du labyrinthe et de garder la longueur du plus long parmi ceux qui atteignent la sortie. Bien entendu, un chemin ne comporte pas de cycle. 
maranget@manche ~/TD/TD-7 > java Tous < petit.laby
Plus grande longueur : 18
Le chemin le plus long étant celui-ci :

La classe Tous qui réalise cette opération est facile à écrire : c'est une petite modification de la classe Profondeur. On se rendra toutefois vite compte qu'elle est très inefficace. Par exemple en essayant le grand labyrinthe. Solution.

3.1 Promenade heuristique

Figure 1 : Promenade dans le grand labyrinthe

Lors du parcours du labyrinthe en profondeur, on essaie les voisins d'un sommet dans un certain ordre. Cet ordre est arbitraire, dans le sens que le coût du parcours, dans le cas le pire (le nombre de sommets) n'en dépend pas. On peut donc fixer cet ordre selon l'idée que l'on se fait du chemin à trouver.

Dans le cas d'une promenade, une idée est d'essayer les voisins qui nous éloignent de la sortie avant ceux qui nous en rapprochent. On a alors une bonne chance de suivre un chemin plutôt long. Informatiquement parlant, on effectue un parcours en profondeur d'abord, mais en essayant d'abord les voisins qui éloignent de la sortie, selon une distance à préciser (distance euclidienne, distance Max, distance Manhattan...). Dans la pratique on peut trier les listes de voisins du graphe avant de commencer le parcours. Écrire la classe Promenade qui réalise ce parcours que l'on espère buissonier. Dans le cas du grand labyrinthe, on obtiendra par exemple : 
maranget@manche ~/TD/TD-8 > java Promenade < grand.laby
Longueur : 295
Ainsi que le chemin de la figure 1.

Ce genre de technique aura des chances de succès avec de gros labyrinthes comprenant relativement peu de murs. Les résultats sont étonnants, dès que la taille des labyrinthes croît. Ce tableau donne les longueurs des chemins trouvés par Promenade et Profondeur dans la cas de tels labyrinthes :
Labyrinthe taille Promenade Profondeur optimal
petit.laby 4 X 8 16 12 18
b.laby 10 X 12 66 46 82
bi.laby 10 X 12 60 56 82
grand.laby 16 X 27 295 59 >= 337
a.laby 20 X 25 347 53 >= 391
c.laby 50 X 50 1804 122 >= 2036
e.laby 50 X 50 1795 1089 >= 1987
d.laby 60 X 60 1944 292 >= 2440

En revanche, l'heuristique peut mal se comporter, surtout si l'on construit des labyrinthes exprès. Essayez donc zoo.laby, foo.laby ou bar.laby. Solution.

3.2 Détours de la promenade
À l'oeil nu, on voit facilement que la promenade de la figure 1 peut être étendue par des détours. Par exemple, dès le départ on peut partir dans l'espace libre vers la droite :
  =>  
Écrire une classe Detour qui construit d'abord un chemin, puis itère la construction de détours, jusqu'à plus soif. On notera qu'un détour part du chemin initial pour y revenir par un chemin plus long. Solution.

4 Un autre problème
On se pose cette fois la question de trouver les composantes biconnexes des labyrinthes.

Personnellement, je trouve que ça n'a rien d'évident. Je donne donc à la demande une photocopie de l'article de Robert Tarjan décrivant son algorithme, à charge pour vous de comprendre le minimum nécessaire pour programmer (le programme est dans l'article, en pseudo-pascal).

En outre voici quelques définitions utiles. Un graphe est dit biconnexe quand, pour tout triplet de points v, a, w, il existe un chemin de v à w qui ne passe pas par a (on notera que selon cette définition les graphes à un ou deux sommets sont biconnexes). Lorsqu'un graphe n'est pas biconnexe, il contient au moins un point d'articulation, c'est à dire un sommet a, tel qu'il existe deux autres sommets v et w et que tous les chemins de v à w passent par a.

Une composante biconnexe, est un ensemble maximal d'arcs, tel que le sous-graphe induit par cet ensemble d'arcs est biconnexe. On peut montrer qu'il s'agit des classes d'équivalences de la relations definie sur les arcs par l'appartenance à un même cycle (chemin qui tourne en rond sans se recouper).

Du point de vue de la programmation, on affichera donc des ensembles d'arcs. On utilisera donc des couleurs pour distinguer les ensembles. On pourra par exemple obtenir, pour ce labyrinthe a trois composantes biconnexes, le résultat suivant :
On notera que les points d'articulation sont également indiqués, dans la même couleur que la composante biconnexe qui a été découverte en même temps qu'eux (voir l'article !). Ici, il y a donc trois composantes donc trois sous-graphes associés. Les point d'articulation appartenant à deux de ces sous-graphes (le point rouge aux sous-graphes verts et rouges ; le point bleu aux sous-graphes rouges et bleus). Il y a d'autres exemples à essayer, all2.laby (une seule composante), all3.laby (complexe, l'origine n'est pas un point d'articulation), all4.laby (complexe, l'origine est un point d'articulation).

Compte-tenu de l'algorithme de l'article, vous aurez besoin des classe Arc des arcs (une paire de sommets), et d'une classe Pile des piles d'arcs. Solution..

Pour les coloriages, on utilisera les méthodes suivantes de la classe AnimLaby : Le programme de test Couleur, à utiliser comme Test, vous donne une idée de comment utiliser les couleurs : 
maranget@manche ~/TD/TD-7 > java Couleur seeneeseneesss < petit.laby
Et ça donne :

Dernière modification : 2002-11-27
Ce document a été traduit de LATEX par HEVEA.