Comment sortir d’un labyrinthe?

D’Homère à JK. Rowling, de Rick Riordan à James Dashner, les labyrinthes ont fasciné et impressionné. La littérature les présente comme des problèmes métaphoriques dont la sortie n’est que pure chance. Mais, qu’en dit la mathématique ?

Une fois de plus, les mathématiciens se sont armés de concepts pour atteindre la solution. Ils ont premièrement défini le labyrinthe. Il s’agit d’une structure connexe – d’un seul tenant – pouvant avoir deux formes (ou topologies) différentes. LabyrinthesTout d’abord, le labyrinthe dit parfait se caractérise par un chemin unique passant par toutes les sections du labyrinthe. Ce-dernier est qualifié d’imparfaits quand il contient des ilots – formés par un chemin se recoupant – parfois inaccessibles.

Mais avant de tenter de trouver la sortie, comment créer un labyrinthe? Il existe de nombreuses méthodes pour parvenir à cela mais concentrons nous sur les deux principales.
Le cas des labyrinthes parfaits est très simple et pour créer un labyrinthe imparfait il suffit de partir du résultat précédent et de détruire aléatoirement des murs.

Il existe une méthode de construction appelée Fusion aléatoire des chemins. Elle consiste en l’attribution d’un nombre unique à chacune des cellules du quadrillage. A chaque étape on choisit aléatoirement un mur qu’on détruit. Il faut cependant que les cellules séparées par le mur en question aient un nombre différent.

  • Si les identifiants sont identiques, c’est que les deux cellules sont déjà reliées et appartiennent donc au même chemin. On ne peut donc pas ouvrir le mur.
  • Si les identifiants sont différents, le mur est ouvert, et l’identifiant de la première cellule est affecté à toutes les cellules du second chemin.
flash

Algorithmes de génération par Adrien Béraud

Après n*m-1 étapes le labyrinthe est terminé et chaque cellule est reliée à toutes les autres, et ce, de manière unique; définition même du labyrinthe parfait.
L’algorithme d’exploration exhaustive propose lui aussi de tracer un quadrillage de n * m cases. Au départ, toutes les cellules sont marquées comme non visitées puis on choisit arbitrairement une cellule et on la marque comme visitée. On regarde ensuite quelles sont les cellules adjacentes non visitées. S’il y a au moins une possibilité, on en choisit une au hasard, on ouvre le mur et on recommence avec la nouvelle cellule. S’il n’y en pas, on revient à la case précédente et on recommence. Lorsque l’on est revenu à la case de départ et qu’il n’y a plus de possibilités, le labyrinthe est terminé.

Dans ce cas, quel algorithme choisir? En réalité cela dépend du résultat souhaité.le premier génère un algorithme dont l’arbre (voir ci-dessous) est statistiquement mieux équilibré. Tous les murs ont approximativement autant de chances d’être ouverts favorisant l’apparition de bifurcations. A contrario, le second privilégie les chemins et plus un chemin est généré tôt, et plus il a de chances d’être long cause du manque d’équilibre de l’arbre. Le labyrinthe final sera composé de quelques chemins assez longs avec peu de ramifications, courtes qui plus est. En somme, un labyrinthe don la sortie est pus simple à trouver intuitivement. On peut noter que cette différence est particulièrement marquée sur les grands labyrinthes mais négligeable sur ceux de taille moindre. Cependant, l’algorithme par fusion aléatoire des chemins sera plus lent à exécuter. Vous pouvez visualiser l’action de ceux-ci:

Maintenant que nous savons cela, comment sortir du dit labyrinthe? Il existe en fait une solution très simple: longer un mur. Cette stratégie fonctionne pour tout labyrinthe parfait. Et il est possible de le démontrer. Comme le labyrinthe est fini, si cette méthode ne mène pas à la sortie, le chemin alors emprunté forme une boucle. Or, il est impossible d’arriver à un tel îlot en suivant toujours le même mur. Donc, nous arrivons à une contradiction et ce raisonnement par l’absurde nous permet d’infirmer l’hypothèse selon laquelle la stratégie n’est pas fonctionnelle. La solution donnée n’est cependant pas toujours la plus rapide et peut conduire à explorer tout le labyrinthe. On peut également démontrer qu’elle fonctionne pour les labyrinthes imparfaits à condition que l’entrée et la sortie soit sur le même mur. Si vous êtes parachutés au milieu d’un labyrinthe imparfait, il est fort possible que vous ne parveniez à trouver la sortie ainsi. Thésée ne pourra donc sortir de son labyrinthe à ilots imbriqués de cette façon.

GrapheLes mathématiciens ont donc mis au point des algorithmes de « Maze solving » ou résolution de labyrinthe pour palier à ce manque. Il existe un domaine de recherche appelé théorie des graphes, un graphe étant une structure constituée de points reliés entre eux par des arcs. et un labyrinthe peut très bien être représenté par un graphe en arbre, chaque croisement correspond à l’intersection entre deux branches et un cul-de-sac correspond à l’extrémité d’une branche. Ainsi toutes les propriétés des graphes peuvent être appliqués aux labyrinthes. Lorsque le labyrinthe est parfait le graphe est acyclique et dans le cas contraire il possède autant de cycles que d’ilots et ne correspond plus à un arbre pouvant être exploré en « longeant » les branches.

Voyons ensemble les aboutissements de cette théorie. Tout d’abord l’algorithme Pledge – découvert par Jon Pledge d’Exeter à l’âge de 12 ans – est conçu pour contourner les obstacles. On compte les changements de direction en augmentant d’un lorsque l’on tourne à gauche et en diminuant d’un lorsque l’on tourne à droite. Au début, le décompte est à zéro. Les deux instructions sont alors les suivantes :

  1. Aller tout droit jusqu’au mur, passer à l’instruction 2
  2. Longer le mur par la droite jusqu’à ce que le décompte des changements de direction atteigne zéro, passer à l’instruction 1

Cet algorithme fonctionne dans tous les cas quelque soit le labyrinthe. On peut à nouveau raisonner par l’absurde mais cette fois la démonstration ici présente ne sera qu’une explication générale en raison de la complexité de celle-ci.

Si on pouvait suivre une boucle sans fin, celle-ci devrait se dérouler dans le sens des aiguilles d’une montre. Alors, à chaque nouveau passage au même sommet, le décompte diminuerait de 4, de sorte que sa valeur resterait toujours négative et ne prendrait jamais la valeur 0. On longerait donc constamment le même mur en le gardant à main gauche, sans jamais pouvoir s’en écarter. Cela signifie que dans ce cas, on aurait buté sur un mur d’enceinte sans aucune ouverture. Il n’y aurait aucun moyen de sortir, ni d’ailleurs d’entrer dans le labyrinthe !

Algorithmus der Woche, 2006

ezgif.com-resize

Algorithme de Trémaux

Cependant, si vous n’êtes pas à l’aise avec la manipulation de chiffres à chacun de vos croisements, l’algorithme de Trémaux permet des résultats analogues en dessinant vos chemins à l’aide d’une craie et en suivant les instructions suivantes pour tout croisement (ou sommet) x:

  1. S’il existe des successeurs de x encore non visités (aucun trait à la craie ne le relie à x) en choisir un y et s’y rendre en marquant le chemin
  2. S’il n’en existe pas, alors revenir sur ses pas jusqu’à ce que la règle 1 s’applique
  3. Si on est au sommet de départ et que la règle 1 ne s’applique pas, le parcours est terminé

Ainsi, Thésée pourra enfin échapper au minotaure.

Il existe cependant d’autres types de labyrinthes qui depuis quelques années fleurissent au sein des concours de mathématique ludique. Un quadrillage est présenté, un nombre étant inscrit dans chacune des cases. De plus, chaque déplacement doit se faire selon un « pas » prédéfini. C’est à dire qu’on peut passer d’une case à une autre si et seulement si la différence entre deux cases consécutives est une constante. On pourra donc suivre le chemin 1-3-5-7-9 mais pas le chemin 2-6-7-9-13. Pour résoudre mathématiquement ce genre de labyrinthe il faut tout d’abord définir les chemins – chaque chemin correspondant à un pas particulier. Une fois cela fait vous pouvez utiliser l’une des méthodes décrites ci-dessus pour en sortir; en effet tous les chemins (et donc celui que vous trouverez comme étant celui menant à la sortie – respectera la règle du pas. Pour générer un tel labyrinthe il suffit de générer un labyrinthe puis d’inscrire les chemins à l’aide de nombres suivant une suite arithmétique. Enfin, les murs sont abattus. Dans les cas des labyrinthes parfaits, un chemin peut-être scindé en deux du point de vue numérique car dans le cas contraire, l n’en existerait qu’un remettant en cause l’utilité du du caractère numérique de ce casse-tête.

Il est donc possible de générer une infinité de labyrinthes tous plus complexes les uns que les autres mais la mathématique trouvera toujours la sortie. Alors, si vous projetez d’enfermer dans un labyrinthe littéraire un groupe de personnes, vérifiez qu’il ne contient pas de mathématiciens.

Notes

Cet article a en partie contribué à celui présent sur www.wikipedia.com.

Sources

Pour aller plus loin…

Publicités

3 réflexions sur “Comment sortir d’un labyrinthe?

  1. Pingback: L’informatique du Rubik’s Cube – Algorithmes de Dieu et… du Diable | Abstraction mathématique

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s