Conseils utiles

Comment trouver un moyen de sortir du labyrinthe

Pin
Send
Share
Send
Send




Dans les temps anciens, les labyrinthes étaient porteurs de mystère et de mystère. L’un des premiers labyrinthes connus de l’humanité décrit Hérodote: c’était un labyrinthe égyptien dans lequel il y avait 5 000 chambres. Au fil du temps, les labyrinthes ont perdu leur signification religieuse et mystique et sont devenus des objets de divertissement, se transformant en jardins et parcs sous la forme de haies verdoyantes de configuration complexe.

Résoudre les labyrinthes a toujours été une activité fascinante, mais la création de machines pouvant traverser le labyrinthe est encore plus excitante.

L'une des règles les plus simples pour parcourir un labyrinthe est la règle «à une main»: lorsque vous vous déplacez dans un labyrinthe, vous devez toujours toucher le mur de la main droite ou gauche. Cet algorithme était probablement connu des Grecs anciens. Vous devez faire un long chemin, aller dans toutes les impasses, mais à la fin, l'objectif sera atteint. Bien que cette règle présente un inconvénient, nous en reparlerons plus tard.

Essayons de décrire un robot agissant conformément à la règle de la "main droite".

Au début de son travail, le robot doit trouver le mur le long duquel il suivra. Pour ce faire, il peut simplement avancer jusqu'à rencontrer un obstacle.

Lorsque le robot rencontre un obstacle, il commence à se déplacer conformément à la règle de la "main droite".

En se déplaçant le long du mur, le robot surveille s'il y a un passage à droite. S'il y a un passage, le robot doit le parcourir pour ne pas se déchirer du mur à droite.

S'il n'y a pas de passage - devant le mur - le robot tourne à gauche. S'il n'y a plus de passage, il tourne encore à gauche, tournant ainsi à 180 degrés, et va dans la direction opposée.

Le schéma de principe de l'algorithme d'un robot fonctionnant selon la "règle de la main droite" est présenté dans la figure.


Essayons de vérifier le fonctionnement de cet algorithme et écrivons un programme pour cela. À cette fin, nous nous tournons vers l'environnement de programmation GameLogo. Cet environnement est un outil pratique pour modéliser divers algorithmes liés au contrôle de robot. Il possède une tortue performante, qui n’est au fond qu’un véritable robot. La tortue a un ensemble de commandes très pratique - en avant, à droite, à gauche, à l'arrière. De plus, au centre de la tortue se trouve un capteur prenant une valeur de 0 à 100, en fonction du ton de la surface sur laquelle elle se trouve.

Le langage du logo que nous allons utiliser est très simple et similaire à Basic. Vous pouvez vous familiariser avec les commandes de langue ici. Un téléchargement gratuit de l'environnement de programmation GameLogo est ici. La taille de la distribution est petite - 1 Mo seulement.

Dans les archives avec GameLogo, il y a des fonds avec des labyrinthes, dont nous allons utiliser un.

Au tout début du programme, nous donnons la commande à la tortue de lever la plume (par défaut, la tortue laisse une trace).

La taille du champ est de 800 par 600 pixels. La position de départ de la tortue est située aux coordonnées 115, 545 (carré blanc).

La couleur des chemins du labyrinthe est claire, le capteur sur eux prendra des valeurs supérieures à 50. La couleur des parois du labyrinthe est sombre, la valeur du capteur sera inférieure à 50. La sortie du labyrinthe est représentée par un carré noir, la valeur du capteur au-dessus de 0.

Nous allons déclarer un indicateur de variable, avec lequel nous allons contrôler si la sortie du labyrinthe est atteinte.

Nous allons écrire le programme et le démarrer à l’aide du gros bouton rouge avec l’inscription «Run».

Si l’on sait que le labyrinthe n’a pas de murs séparés, c’est-à-dire qu’il n’existe aucun itinéraire fermé permettant de revenir au point de départ, un tel labyrinthe est appelé simplement connecté et il peut toujours être complètement contourné en appliquant la règle «à une main».

Si le labyrinthe contient des murs autoportants, en appliquant la règle du «à une main», il n’est pas toujours possible de traverser tous les couloirs et toutes les impasses. Les labyrinthes ayant des murs séparés et des routes fermées sont appelés connexions multiples. Dans ce cas, les labyrinthes connectés peuvent être divisés en deux groupes: sans "boucle" autour de la cible (un itinéraire fermé ne contourne pas la cible) et avec une "boucle" fermée autour de la cible (la cible peut être contournée par un itinéraire fermé).

Dans les labyrinthes du deuxième groupe, qui ont des liens multiples, la règle du «une main» ne fonctionne pas et, en l'utilisant, il est impossible d'atteindre l'objectif. Mais même ces labyrinthes peuvent être surmontés en s'appuyant sur un algorithme exact.

La solution au problème de tels labyrinthes appartient à une époque relativement tardive, et le début a été posé par Leonard Euler. Euler, non sans raison, pensait qu'il était possible de trouver un moyen de sortir de tout labyrinthe, mais aussi de manière relativement simple.

L'algorithme universel permettant de traverser n'importe quel labyrinthe n'a été décrit qu'un siècle plus tard dans le livre du mathématicien français E. Luke "Recreations matematiques", publié en 1882. Fait intéressant, dans la description de l’algorithme, Luke a souligné la primauté d’un autre mathématicien français, M. Tremot. Ainsi, l'algorithme est devenu l'algorithme de Luc-Tremo.

Tremo propose les règles suivantes: quitter n'importe quel point du labyrinthe, marquer son mur (croix) et aller dans une direction arbitraire vers une impasse ou une intersection, dans le premier cas, reculer, mettre une seconde croix pour indiquer que le chemin a été parcouru deux fois - aller et retour , et allez dans une direction qui n’a jamais été parcourue ou une fois, dans la seconde - allez dans une direction arbitraire, en marquant chaque intersection à l’entrée et en sortant avec une croix, s’il ya déjà une croix à la croix, vous devriez alors changer de chemin si pas t - ce chemin traversé, en le marquant avec une seconde croix.

Connaissant l'algorithme Tremo, vous pouvez ajuster le comportement du légendaire Theseus. Inspiré par le cadeau de sa chère Ariane, il traverse avec confiance le labyrinthe. Soudain, devant lui, il y a un mouvement sur lequel un fil a déjà été tendu. Que faire En aucun cas, vous ne le traversez, mais vous revenez par le chemin déjà connu, en doublant le fil, jusqu'à ce que vous trouviez un autre coup non accompli.

À l'aide d'une variante de l'algorithme Tremo, le père de la théorie de l'information, Claude Elwood Shannon, a construit l'un des premiers robots à auto-apprentissage. Shannon lui a donné le nom sonore "Theseus", mais dans l'histoire de "Theseus", il est devenu plus connu sous le nom de "souris" de Shannon. La «souris» a d'abord examiné le labyrinthe en entier, puis (pour la deuxième fois) est allée beaucoup plus vite, en évitant les zones passées deux fois.

De nos jours, les robots traversant le labyrinthe participent à l'un des concours les plus intéressants de machines à penser, qui se déroule dans plusieurs pays du monde. Ces compétitions sont collectivement appelées Micromouse et comptent parmi les leaders du sport robotique en termes d’innovations techniques.

Les compétitions se déroulaient lors de la première olympiade russe des robots, dont le but était de passer à travers une sorte de labyrinthe: le plus rapidement possible, en franchissant les "portes ouvertes" des murs, le robot devait se rendre du lieu de départ au lieu d'arrivée. Le robot pouvait contrôler son mouvement le long de lignes noires tracées sur le sol du labyrinthe.

RÈGLE D'UNE MAIN

Il existe un moyen très simple d'entrer dans n'importe quel labyrinthe sans craindre de s'y perdre. En utilisant cette règle, vous pouvez toujours trouver un moyen de sortir de tout labyrinthe, peu importe la confusion de ses transitions. Voici la règle pour errer en toute sécurité dans les labyrinthes:

Il est nécessaire de traverser le labyrinthe en touchant constamment son mur avec la même main.

Cela signifie qu’à l’entrée du labyrinthe, vous devez toucher le mur d’une seule main (de la même façon, à droite ou à gauche) et, au moment de vous y promener, continuez de toucher le mur avec la même main.

Essayez - essayez cette méthode - d’appliquer la «règle d’une seule main» pour une promenade mentale le long du plan Hampton Maze. Armé d'une allumette, imaginez que vous entrez dans ce labyrinthe de jardin et que vous touchez tout le temps ses murs avec une seule main. Vous obtiendrez bientôt de l'entrée extérieure au centre du labyrinthe. Ne baissez pas la main ici, continuez à avancer, en le touchant avec les murs, et vous sortirez avec précision de ses recoins vers l’entrée extérieure.

D'où vient cette règle commode? Nous allons essayer de comprendre cela. Imaginez que vous ayez les yeux bandés en entrant dans une pièce avec une seule entrée. Que devriez-vous faire pour tout contourner et en sortir à nouveau? Le plus simple est de marcher le long des murs sans lâcher le mur, vous rejoindrez certainement la porte par laquelle vous êtes entré. Ici, la rationalité de la «règle d'une seule main» s'explique d'elle-même. Imaginez maintenant que les murs de la pièce ont des protubérances, comme le montre la fig. 4 et 5. Avant vous n'êtes plus des chambres simples, mais de vrais labyrinthes. Mais la "règle à une main" devrait, bien sûr, et dans ces cas, maintenir sa force, vous ramenant de manière fiable à la sortie des lieux.

La "règle d'une main" a son inconvénient. En l'utilisant, vous pouvez entrer dans n'importe quel labyrinthe et en sortir. Mais cela ne signifie pas que vous ferez le tour de tous les coins du labyrinthe sans exception. Vous ne visiterez que les endroits dont les murs sont en quelque sorte reliés au mur extérieur du labyrinthe - pour ainsi dire à sa continuation. Mais vous passerez devant les sections du labyrinthe dont les murs n’ont pas de lien avec ses murs extérieurs. Dans le labyrinthe du jardin de Hampton, il existe un tel site. Par conséquent, si vous utilisez la règle «à une main», vous ne pouvez pas parcourir tous les chemins de ce labyrinthe: un chemin reste inexploré. Sur la fig. 6 lignes pointillées indiquent le chemin le long des murs de la haie, si vous utilisez la "règle à une main", et l'astérisque marque cette allée, qui en même temps reste non détectée.

Pin
Send
Share
Send
Send