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