Résolution de labyrinthe

On peut essayer de trouver la sortie d'un labyrinthe en longeant systématiquement un mur en le gardant, sans jamais le lâcher, à main droite ou à main gauche. Cette idée est vérifiée seulement 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[1]. 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 ». C'est-à-dire qu'on tourne autour d'un îlot, comme un pâté de maisons, qu'on peut représenter de manière (topologiquement) équivalente par un carré, comme l'îlot DEF de l’illustration ci-dessous. Or, c'est évident, il est impossible d'arriver à un tel îlot ou carré en suivant toujours le même mur (sauf en partant d'un point de l'îlot). Donc, en suivant le même mur, on est certain de ne pas « tourner en rond » et donc de sortir du labyrinthe.

Ce résultat est vrai pour tout labyrinthe, mais il est tout aussi vrai que cette méthode ne donne pas (nécessairement) le chemin le plus court.

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

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-contre 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.

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[1]. 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. Cette dernière méthode, fonctionnant pour n'importe quel labyrinthe, est un résumé assez fidèle du fonctionnement de l'algorithme de Trémaux[2] - [3].

D'autres méthodes sont utilisées et implémentées sur des robots (donc avec une vue locale) afin de lui permettre de sortir du labyrinthe. L'algorithme de Pledge (en) par exemple, permet de retrouver la sortie de n'importe quel labyrinthe (où que l'on commence et même s'il y a des ilots) en demandant à garder en mémoire un unique entier[4]. Cet algorithme ne trouve cependant pas la sortie si celle-ci est une trappe dans le plafond plutôt qu'une porte au bout d'un couloir[1].

Algorithme de Trémaux's. Le point vert indique la position actuelle, les points bleus les marques simples, et les croix les marques doubles.Une fois la sortie trouvée, le chemin est marqué par les marques simples.

L'algorithme de Trémaux, inventé par Charles Pierre Trémaux[5], est une méthode efficace pour sortir d'un labyrinthe en marquant les chemins parcourus. Il fonctionne pour tous les labyrinthes qui ont des passages bien définis[6], mais ne donne pas forcément le chemin le plus court.

À chaque jonction, les chemins sont soit non marqués, soit marquées une fois ou marqués deux fois. L'algorithme fonctionne en suivant ces règles:

1. Marquez chaque chemin que vous parcourez une fois. Les marques doivent être visibles aux deux bouts du chemin, donc si ce sont des marques physiques plutôt que stockées dans un ordinateur, la même marque doit être faite aux deux extrémités du chemin.
2. Ne jamais entrer dans un chemin marqué.
3. Si vous arrivez à une jonction qui n'a pas de marque (à part celle du chemin par lequel vous êtes arrivé), choisissez un chemin non marqué au hasard, marquez-le et suivez-le.
4. sinon:
   • si le chemin par lequel vous êtes arrivé n'a qu'une marque, faites demi-tour et marquez-le une seconde fois. Ceci arrive en particulier lorsque vous atteignez un cul-de-sac.
   • sinon, choisissez un des chemins avec le moins de marques (zéro si possible, sinon une), prenez ce chemin en le marquant.

La règle 4.1 du demi-tour transforme efficacement n'importe quel labyrinthe contenant des circuits fermés en graphe simplement connexe : chaque fois qu'on trouve un chemin qui créerait une boucle, on le considère comme un cul-de-sac et on fait demi-tour. Sans cette règle, on peut s'empêcher de visiter une partie du labyrinthe.

Quand on atteint finalement la solution, les chemins marqués une seule fois indiquent le chemin de retour vers le départ. S'il n'y a pas de sortie, l'algorithme ramène au départ où tous les chemins sont marqués deux fois Dans ce cas, chaque chemin est parcouru deux fois, une dans chaque direction. Le parcours résultant est appelé "bidirectionnel double trace"[7] .

Essentiellement, cet algorithme découvert au XIX^e siècle est utilisé un siècle plus tard comme algorithme de parcours en profondeur.

L'algorithme de Tes est une formule qui dit que tous les labyrinthes sont construits sur le même modèle et que pour en sortir il suffit de tourner une fois à droite et une fois à gauche à chaque intersection. Cette formule ne permet pas d'obtenir le chemin le plus court.