Résolution de labyrinthe
La résolution de labyrinthe est le problème algorithmique qui consiste à trouver la sortie d'un labyrinthe (modélisé mathématiquement).
Méthode de la main droite
[modifier | modifier le code]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.
![](http://178.128.105.246/cars-http-upload.wikimedia.org/wikipedia/commons/thumb/a/a2/Nested_Labyrinth.svg/400px-Nested_Labyrinth.svg.png)
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.
Différentes vues du labyrinthe
[modifier | modifier le code]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].
Algorithme de Pledge
[modifier | modifier le code]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
[modifier | modifier le code]![](http://178.128.105.246/cars-http-upload.wikimedia.org/wikipedia/commons/thumb/1/11/Tremaux_Maze_Solving_Algorithm.gif/220px-Tremaux_Maze_Solving_Algorithm.gif)
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:
- 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.
- Ne jamais entrer dans un chemin marqué.
- 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.
- 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 XIXe siècle est utilisé un siècle plus tard comme algorithme de parcours en profondeur.
Algorithme de Tes
[modifier | modifier le code]L'algorithme de Tes est une formule qui vérifie que tous les labyrinthes sont construits sur le même modèle physique et que pour s'en échapper, il suffit de tourner une fois du côté droit et la fois d'après du côté gauche à chaque intersection que l'on croise
Cette formule ne permet pas d'obtenir le chemin le plus court, et, peut dans certaines circonstances, être faillible.
Algorithme de Tarry
[modifier | modifier le code]Lorsque le voyageur est totalement égaré dans le labyrinthe, l'algorithme en profondeur du mathématicien français Gaston Tarry (cf Gaston Tarry, Le problème des labyrinthes, Nouvelles annales de mathématiques 3e série, tome 14 (1895), p. 187-190) est une double règle qui s'énonce comme suit :
À chaque carrefour du labyrinthe :
Règle no 1 : Ne reprendre le couloir de première visite de ce carrefour qu'en dernier recours.
Règle no 2 : Ne jamais prendre un couloir deux fois dans le même sens.
Cette règle générale permet au voyageur égaré de sortir à coup sûr du labyrinthe quand ce dernier possède une issue (entrée ou sortie) et, dans le cas contraire, de le visiter complètement avant de se retrouver à son carrefour de départ. Voir également Pierre Tougne, L'exploration d'un labyrinthe, Dossier Pour la science, avril/juin 2008).
Algorithme de Oystein
[modifier | modifier le code]Lorsque le voyageur égaré sait qu'il n'est pas trop éloigné de l'entrée du labyrinthe (à moins de 2 ou 3 carrefours par exemple), l'algorithme en largeur du mathématicien norvégien Oystein Ore (cf Oystein Ore, An excursion into labyrinths, in The Mathematics Teacher, p. 367-370, Vol. 52, No 5, May 1959) permet de rejoindre cette entrée par cercles concentriques depuis le carrefour de départ, sans besoin d'explorer le labyrinthe en profondeur.
La règle générale est alors la suivante (cf Jearl Walker, Comment traverser un labyrinthe sans se perdre ni tourner en rond, article de la revue Pour la science, rubrique Expériences d'amateur, février 1987) :
1. Depuis le carrefour de départ, parcourir un à un les couloirs menant à une distance de 1 carrefour, en marquant d'un trait chacune des deux extrémités de chaque couloir parcouru.
2. Condamner les deux extrémités du couloir en changeant les marques par une croix dans les quatre cas suivants :
A. le couloir marqué d'un trait est un cul-de-sac ; B. le couloir marqué d'un trait est une boucle reliant deux sorties du même carrefour ; C. le couloir marqué d'un trait mène à un carrefour déjà visité ; D. le couloir mène à un carrefour dont toutes les sorties sont condamnées.
3. Revenir au carrefour de départ en suivant les marques.
4. Recommencer l'opération en parcourant tous les couloirs non condamnés menant à une distance de 2 carrefours, en suivant les marques, et en ajoutant un trait à chacune des deux extrémités de chaque couloir lors de son parcours aller.
E. Le suivi des marques à l'aller et au retour est simple : leur nombre diminue de 1 à chaque carrefour traversé à l'aller et augmente de 1 à chaque carrefour traversé au retour.
5. Revenir au carrefour de départ en suivant les marques.
6. Recommencer l'opération autant de fois que nécessaire en allant à une distance de 3 carrefours, puis de 4, etc.
Cette règle générale permet au voyageur égaré de sortir à coup sûr du labyrinthe quand ce dernier possède une issue (entrée ou sortie) et, dans le cas contraire, de le visiter complètement avant de se retrouver à son carrefour de départ.
Modélisation d'un labyrinthe et chemin le plus court
[modifier | modifier le code]Lorsqu'on a une vue d'ensemble d'un labyrinthe, celui-ci peut se modéliser par une matrice d'incidence (M) dont les lignes et les colonnes sont les numéros de carrefour et dont chaque élément de la matrice indique la nombre de couloirs (0, 1, 2, etc.) reliant un carrefour à un autre [WAL].
La matrice d'incidence permet également de modéliser un labyrinthe comportant des couloirs à sens unique à condition que ces couloirs ne forment pas une boucle reliant deux sorties du même carrefour ou une boucle reliant deux carrefours.
Pour des besoins d'étude, tout labyrinthe peut être simplifié comme suit :
1. Tout cul-de-sac peut être supprimé en considérant qu'il est intégré (en tant que cul-de-sac peu profond) au carrefour y menant.
2. Toute boucle reliant deux sorties du même carrefour peut être supprimée en considérant qu'elle est intégrée (en tant qu'îlot de petite taille) au carrefour.
3. Toute boucle reliant deux carrefours peut être réduite à un seul couloir entre ces carrefours en considérant qu'elle est intégrée (en tant qu'îlot de petite taille) à ce couloir.
4. Tout carrefour dont le nombre de couloirs se réduit à 2 par l'une ou plusieurs des simplifications précédentes peut être supprimé en raccordant directement les deux couloirs.
5. Tout carrefour comportant n couloirs avec n > 3 peut être remplacé par un anneau formé de n carrefours comportant 3 couloirs chacun à condition d'accepter de violer la règle no 2 de Tarry dans le carrefour modifié afin de pouvoir parcourir l'anneau entre deux carrefours quelconques.
Si le voyageur sait traverser le labyrinthe modifié, alors il peut aussi trouver un chemin dans le labyrinthe original en rétablissant les carrefours et couloirs originaux.
La matrice d'incidence d'un labyrinthe permet également de trouver le nombre de couloirs du chemin le plus court reliant un carrefour à un autre. En multipliant la matrice M par elle-même, on obtient une nouvelle matrice (M2) dont les éléments indiquent le nombre de façons différentes d'aller d'un carrefour à un autre par un chemin constitué de 2 couloirs. En répétant n fois l'opération, on obtient une matrice (Mn) dont les éléments indiquent le nombre de façons différentes d'aller d'un carrefour à un autre par un chemin constitué de n couloirs [WAL].
Pour trouver le chemin le plus court reliant un carrefour à un autre, il suffit alors d'élever la matrice M à une puissance telle que l'élément correspondant à la liaison entre ces deux carrefours devienne non nul. La puissance donne alors le nombre de couloirs du chemin le plus court [WAL].
[WAL] Jearl Walker, Comment traverser un labyrinthe sans se perdre ni tourner en rond, article de la revue Pour la science, rubrique Expériences d'amateur, février 1987.
Notes et références
[modifier | modifier le code]- Jérôme Cottanceau, Le choix du meilleur urinoir : Et 19 autres problèmes amusants qui prouvent que les maths servent à quelque chose !, Paris, Belin, coll. « Science à plumes », , 216 p. (ISBN 978-2-7011-9766-1), chap. 18 (« À quoi servent les maths... À ne pas rester piéger dans un labyrinthe ? »).
- Nommé d'après Charles Pierre Trémaux, mathématicien français du XIXe siècle.
- « Labyrinthes et fil d’Ariane », (consulté le ).
- Rolf Klein et Tom Kamphans, « L’algorithme de Pledge », sur interstices, .
- Public conference, December 2, 2010 – by professor Jean Pelletier-Thibert in Academie de Macon (Burgundy – France) – (Abstract published in the Annals academic, March 2011 – (ISSN 0980-6032)) Charles Tremaux (° 1859 – † 1882) École Polytechnique of Paris (X:1876), French engineer of the telegraph
- Édouard Lucas: Récréations Mathématiques Volume I, 1882.