Algorithme de Tarry ou comment sortir d’un labyrinthe la première fois

Publié par Simon Taquet le décembre 4, 2018 | Maj le décembre 4, 2018

Cette situation peut être interprétée mathématiquement comme un graphique dans lequel chacun des nœuds représente l’un des districts de Königsberg séparés les uns des autres par la rivière, et les ponts sont compris comme les bords entre les nœuds respectifs. L’itinéraire que nous recherchons ne serait rien de plus qu’un chemin qui traverse tous les noeuds du graphique, ne passant qu’une seule fois par chaque coin et revenant au noeud initial (circuit eulérien). Euler a démontré qu’un tel cours existerait tant que le degré de chaque nœud (c’est-à-dire le nombre de bords qui y sont incidents) serait égal. En observant le graphique précédent décrivant la situation des ponts (les cercles sont les noeuds qui indiquent les différentes zones, et les bords représentent les ponts), on observe que tous les noeuds ont un nombre impair de bords. Par conséquent, selon le résultat précédent, il est impossible de faire un circuit eulérien.

comment sortir d’un labyrinthe la première fois ?

Si nous modifions les hypothèses initiales du problème en établissant que les points de départ et d’arrivée étaient différents, alors nous devrions chercher un chemin eulérien et les conditions pour son existence sont différentes. D’autre part, si nous étions à la recherche d’un itinéraire qui traverserait tous les noeuds du graphique en ne passant qu’une seule fois par chacun d’entre eux, nous serions alors confrontés à ce qu’on appelle un chemin ou circuit hamiltonien.

La détermination et la recherche de chemins ou circuits eulériens joue un rôle fondamental dans la résolution des différents problèmes qui se posent dans différentes disciplines et situations scientifiques telles que ? trouver la sortie d’un labyrinthe.

Mathématiquement, un labyrinthe est un graphique dans lequel les noeuds sont les pièces et chaque passage est représenté par deux bords entre les noeuds correspondants (un dans chaque direction). La condition établie par Euler peut être réécrite dans le cas de graphes dirigés en disant qu’il existe un circuit eulérien lorsque le nombre de bords atteignant chaque noeud coïncide avec le nombre de bords à partir de celui-ci. C’est précisément ce qui se passe dans le graphique dirigé qui représente le labyrinthe. Ainsi, il est possible de passer par toutes les pièces d’une même pièce, en ne passant par chaque passage qu’une seule fois dans chaque direction. Par conséquent, à un moment donné de ce voyage, nous devons rencontrer la sortie.

Maintenant, une fois que nous savons qu’un tel chemin existe, il serait nécessaire de trouver une procédure pour le parcourir d’une manière ordonnée. En ce sens, différentes méthodes ont été proposées en supposant que nous étions initialement dans un labyrinthe, dans un lieu inconnu, et que nous n’en connaissions pas le plan. Le plus simple est celui proposé par le mathématicien français Gaston Tarry en 1895. L’algorithme de

Tarry est basé sur la réflexion suivante : lorsque nous traversons un labyrinthe et que nous nous trouvons dans un passage immédiatement avant d’entrer dans une pièce ou immédiatement après en avoir quitté une, le nombre de fois que nous y sommes entrés ?à l’exception du bord de départ – est le même que le nombre de fois que nous les avons laissés (c.-à-d. que le nombre de bords que nous avons parcourus en entrant dans les nœuds doit être égal au nombre de bords que nous avons parcourus en sortant des nœuds). Par conséquent, une fois que nous sommes entrés dans une pièce (et que nous ne l’avons pas abandonnée), le nombre de bords parcourus vers un nœud (entrant dans le nœud) est supérieur d’une unité au nombre de bords parcourus depuis un nœud (sortant du nœud). Dans cette optique, Tarry s’est appuyé sur la règle suivante pour concevoir son algorithme : ne traversez plus jamais un passage qui vous a conduit dans une pièce pour la première fois, à moins qu’il n’y ait pas d’alternative. Ainsi, l’algorithme proposé par Tarry est le suivant :

  • – Chaque fois que nous entrons dans un passage pour la première fois nous devons faire deux marques à l’entrée.
  • – Chaque fois que nous arrivons dans une pièce nous devons laisser une marque à la sortie du passage qui nous y a conduit si cette pièce a déjà été visitée ou trois marques si elle ne l’a pas été.
  • – Chaque fois que nous quittons une pièce, nous devons choisir les passages inexplorés (ils n’ont pas de marques sur leur entrée) ou ceux qui ont été parcourus dans la direction de l’entrée (ils ont une marque).

Notez que, si un passage ne comporte aucune marque à son entrée, il est inexploré et peut être emprunté. Si vous avez une seule marque, elle a été utilisée pour entrer dans la pièce, alors elle peut être utilisée pour quitter la pièce. Si vous avez deux marques ne doit pas être utilisé comme il a déjà quitté la pièce par lui précédemment. Enfin, s’il a trois marques, c’est le passage qui a été utilisé pour entrer dans la salle pour la première fois et nous ne devrions pas l’utiliser à nouveau à moins que les autres passages menant à la salle aient aussi trois marques.

Cet algorithme apparaît (sous certaines licences littéraires faisant référence à sa datation et son efficacité) dans l’œuvre de Umberto Eco intitulée “The Name of the Rose”. Dans ce roman, qui se déroule au XIVe siècle dans une abbaye bénédictine des Apennins, les aventures policières du frère Guillaume de Baskerville et de son compagnon Adso de Melk sont racontées. Il contient le dialogue suivant entre les deux protagonistes principaux lorsqu’ils sont piégés dans la bibliothèque de l’abbaye :

Il n’y a qu’une seule façon, dit Guillermo, de sortir d’un labyrinthe. En arrivant à chaque nouveau nœud, c’est-à-dire jusqu’au moment non visité, trois signes seront faits sur le chemin de l’arrivée. Si des signes sont observés sur l’un des sentiers de nœuds, cela indiquera que le nœud a déjà été visité, et alors un seul signe sera marqué sur le sentier d’arrivée. Lorsque toutes les étapes d’un nœud sont déjà marquées, il faudra revenir en arrière. Mais s’il y a encore un ou deux pas non marqués, l’un sera choisi au hasard, et il sera marqué de deux signes. Lorsque vous choisissez une étape marquée d’un seul signe, deux autres seront marquées, de sorte qu’il y en a déjà trois. Si lorsque vous atteignez un nœud, vous ne trouvez que des marches marquées de trois signes, c’est-à-dire s’il n’y a plus de marches à marquer, cela indiquera que toutes les parties du labyrinthe ont déjà été couvertes.

L'actualité des Médias

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *