Comment sortir d'un labyrinthe ?

En général, les labyrinthes ont un tracé sinueux, muni ou non d'embranchements, d'impasses et de fausses pistes, destiné à perdre ou à ralentir celui qui cherche à s'y déplacer. Savez-vous qu'il existe des techniques pour sortir, à coup sûr, de certains d'entre eux ?...

On croit savoir, de façon pragmatique, que l'on trouve obligatoirement la sortie d'un labyrinthe si on longe systématiquement un mur en le gardant, sans jamais le lâcher, à main droite ou à main gauche. Cette idée est vérifiée dans le cas d'un labyrinthe parfait, mais elle peut conduire à explorer la totalité du labyrinthe, c'est-à-dire à passer au moins une fois dans toutes les cellules sans exception. Cela correspond à ce que l'on appelle le parcours de l'arbre en profondeur. 

La preuve de cette découverte empirique est très simple. Si on ne sort pas d'un labyrinthe [en tenant toujours la main sur un des murs depuis l'entrée], c'est qu'on est en train de "tourner en rond". Cette vérité est vraie pour tout labyrinthe, mais il est tout aussi vrai que cette méthode ne donne pas (nécessairement) le chemin le plus court.

Cette ruse a toutefois été déjouée par les concepteurs de labyrinthes, car dans les labyrinthes à îlots, tourner systématiquement à droite, ou systématiquement à gauche, peut conduire à tourner systématiquement en rond. L'exemple ci-dessous présente un labyrinthe à îlots imbriqués où la méthode de la main au mur est inopérante et où il faut passer à des méthodes plus évoluées. 

Exemple de labyrinthe à îlots imbriqués avec son graphe abstrait associé

Cette contre-ruse des concepteurs de labyrinthes ne concerne cependant pas ceux qui ont bien réalisé le raisonnement ci-dessus, qui suivent bien le même mur depuis l'entrée et qui n'ont donc pas été parachutés au milieu du labyrinthe. On peut en effet vérifier très facilement qu'il n'est pas possible ainsi d'arriver à tourner autour de l'îlot DEF de l'illustration sans "changer de mur" depuis l'entrée. En suivant le mur de gauche, on suit le chemin le plus court ABCBA. En suivant le mur de droite, on suit le chemin le plus court ABCBA aussi, mais dans l'autre sens. Cette image est une très bonne illustration dudit raisonnement.

La sortie d'un labyrinthe relève plus généralement de la recherche de chemin dans le graphe du labyrinthe. On distingue deux cas.

Dans le premier cas, on dispose d'une vue globale et on est capable de distinguer sans ambiguïté deux positions. De plus, on sait localiser la sortie. On peut alors utiliser toutes ces connaissances pour mesurer une distance (par exemple de Manhattan) par rapport à la sortie et déterminer le chemin pour l'atteindre.

Le second cas est celui de la vue locale, celle qu'aurait la personne qui serait placée dans le labyrinthe (toute autre perception que les murs avoisinants étant négligée). Cette personne ne dispose alors plus de moyen de distinguer un couloir ou un carrefour d'un autre. Dans ce cas, la sortie d'un labyrinthe ne relève guère plus de la chance pure, à moins d'exploiter une mémoire quelconque. L'explorateur peut utiliser ses propres ressources, en retenant les endroits déjà visités, les décisions prises et en dressant une carte au fur et à mesure. Il peut aussi marquer l'environnement en notant par exemple les directions déjà explorées aux carrefours. Le fameux Fil d'Ariane est lui-même la trace concrète que Thésée laisse derrière lui au fur et à mesure qu'il s'enfonce dans l'antre du Minotaure.

Texte sous licence CC BY-SA 3.0. Contributeurs, ici.

Pour partir en mission au milieu d'un labyrinthe de 900m2 :

91300 - LASER QUEST MASSY http://www.laser-quest-paris-massy.com