Imaginons que nous nous trouvions à l’entrée d’un labyrinthe. Nous savons juste que il y a certainement une sortie le long du périmètre, mais nous ne savons pas où est trouvé. Si nous entrons dans ce labyrinthe, comment pouvons-nous être sûrs de pouvoir en sortir ? Et pourrions-nous trouver le chemin le plus court ? Si on ne peut pas voir le labyrinthe d’en hautil existe trois stratégies possibles que nous pouvons exploiter pour nous en sortir : la « règle demain droite», l’algorithme de Trémaux et les algorithmes de «recherche en largeur». Ces algorithmes de résolution de labyrinthes ne sont pas seulement des exercices d’orientation, mais sont également appliqués à l’informatique, à la robotique et aux jeux vidéo. Dans cet article, nous voyons comment ils fonctionnent et quelles sont les solutions possibles pour sortir d’un labyrinthe.
Sortie d’un labyrinthe, la règle de la main : on le pose sur le mur à l’entrée, puis on suit le mur
« La règle de la main droite (ou gauche) » nous permet de résoudre un labyrinthe même les yeux fermés. C’est l’un des algorithmes les plus simples : à l’entrée on décide quelle main utiliser et quel côté du mur suivre. Nous soutenons là main al mur et puis nous commençons à marcher sans jamais détache-le. Avec cette technique nous sommes sûrs de réussir trouver la sortie dans tous les labyrinthes qu’ils ont une seule entrée Et une seule sortie. Attention cependant à ce que nous ne pouvons pas l’utiliser si nous nous rencontrons déjà à l’intérieur le labyrinthe et nous y sommes perdu. Dans ce cas, nous pourrions accidentellement mettre la main sur un «faire du vélo» ou « île », c’est-à-dire une ensemble de murs déconnectés du mur principalcomme ceux colorés en bleu sur l’image. Si nous posions la main sur l’un de ces murs et continuions à le suivre en utilisant la règle de la main droite, nous nous retrouverions boucle sans jamais atteindre la sortie.
Une stratégie qui nous permet de trouver la solution dans tous les types de labyrinthes, même ceux dans lesquels il y a des boucles ou où le but n’est pas de trouver la sortie, mais une salle centrale avec un prix, est le Trémaux, une recherche en profondeur d’abord. algorithme.
On revient si on trouve une impasse, une intersection qu’on a déjà vue et on marque où on est déjà passé
Afin d’utiliser leAlgorithme de Trémauxnous devons apporter quelque chose avec nous pour marquer les intersections et les routes que nous rencontrons. En effet, avec cet algorithme, nous devons noter chaque carrefour, explorer chaque route à fond et, chaque fois que nous atteignons une impasse ou une boucle, revenir à la dernière intersection et essayer un itinéraire différent. Cette stratégie est connue sous le nom de «rechercher en profondeur» (recherche en profondeur) et se compose dealler le plus soigneusement possible dans le labyrinthe et ne reculer que lorsqu’il ne peut plus avancer.
Concrètement, ce qui se passe, c’est que commençons à marcher dans le labyrinthe en suivant la route jusqu’à arriver à un ciel de ruelle (dans ce cas on y retourne) ou un intersection. A ce stade, il y a trois possibilités :
- ET la première fois que nous arrivons à cette intersection : Si c’est la première fois que nous voyons cette intersection, nous marquons l’itinéraire d’où nous venons, puis choisissons arbitrairement une direction dans laquelle continuer et la marquons également.
- C’est la deuxième fois que nous arrivons à cette intersection, mais depuis une autre direction : Si nous avons déjà vu cette intersection mais que nous n’y sommes pas encore arrivés depuis cette direction, alors nous marquons la connexion entre la direction d’où nous venons et l’intersection avec deux panneaux (ou avec un « x ») et revenons ensuite en arrière. Un chemin avec deux panneaux est traité comme un mur et nous ne pouvons plus le parcourir. Ce mécanisme nous permet d’échapper aux boucles.
- Nous sommes déjà allés jusqu’à cette intersection et nous y arrivons depuis une route que nous avons déjà vue : Si l’intersection a déjà été visitée et que nous arrivons d’un itinéraire qui a déjà un panneau, alors nous le marquons une deuxième fois et choisissons arbitrairement une direction parmi les itinéraires sans panneaux, s’il y en a, ou parmi les itinéraires avec un seul panneau. . Dans tous les cas, on ajoute un panneau à la direction choisie.
Cet algorithme réussit à résolvez tous les types de labyrinthes et, en plaçant deux panneaux pour fermer les routes qui ne mènent pas à la solution, cela permet à ceux qui arrivent après nous de ne pas se perdre et d’atteindre la sortie, car ils savent qu’ils doivent traiter ces deux panneaux au sol comme s’ils étaient étaient des murs et ne suivaient les rues qu’avec un seul panneau. Cette méthode, cependant, ne garantit pas que le rue que nous montrerons aux autres sera le plus court. Pour ce faire, nous devons utiliser la recherche « en largeur d’abord », et non en profondeur.
Trouver le chemin le plus court : explorer la largeur, pas la profondeur
La « recherche en largeur » (recherche en largeur) est une stratégie liée à l’algorithme de Trémaux, mais, plutôt que d’explorer les itinéraires qu’il trouve jusqu’au bout, cet algorithme vise à explorer toutes les possibilités, pour ne pas rater la solution la plus courte, celle qui optimise l’itinéraire. Cet algorithme nous garantit que nous réussirons à trouver le chemin le plus court entre l’entrée et la sortiemais nous allons travailler dur très longtemps. Si nous suivons cette stratégie, nous marchons jusqu’à arriver à une intersection A, puis nous choisissons une direction arbitraire et continuons à marcher jusqu’à rencontrer une autre intersection (B). À ce stade, nous retournons vérifier la route que nous avions ignorée précédemment (la route restante à l’intersection A) et continuons jusqu’à trouver l’intersection C. Une fois que nous voyons l’intersection C, nous retournons à l’intersection B pour explorer les autres possibilités en faisant aller et retour plusieurs fois. Pour faire ce que nous avons décrit, l’algorithme réduit essentiellement le labyrinthe à un diagramme, puis trouve le chemin le plus court d’un bout à l’autre.
Pour ce faire, suivez toutes les rues jusqu’à trouver la sortie, en parcourant et en retraçant les chemins du labyrinthe/schéma des dizaines et des dizaines de fois. Comme on peut l’imaginer, cet algorithme n’est utile que si nous sommes marathoniens ou si nous pouvons faire des simulations informatiques et puis suivre le chemin le plus court ce qui nous indique.