Hilfreiche Ratschläge

Wie man einen Weg aus dem Labyrinth findet

Pin
Send
Share
Send
Send




In Labyrinthen herrschte seit jeher ein Gefühl von Mysterium und Mysterium. Eines der ersten Labyrinthe, die der Menschheit bekannt sind, beschreibt Herodot - es war ein ägyptisches Labyrinth, in dem es 5.000 Räume gab. Im Laufe der Zeit verloren die Labyrinthe ihre religiöse und mystische Bedeutung und wurden zu Unterhaltungsobjekten, die sich in Gärten und Parks in Form von grünen Hecken komplexer Konfiguration verwandelten.

Das Lösen der Labyrinthe war schon immer eine faszinierende Tätigkeit, aber noch aufregender ist die Schaffung von Maschinen, die das Labyrinth durchdringen können.

Eine der einfachsten Regeln für das Durchlaufen eines Labyrinths ist die Einhandregel: Wenn Sie sich durch ein Labyrinth bewegen, sollten Sie die Wand immer mit der rechten oder linken Hand berühren. Dieser Algorithmus war wahrscheinlich den alten Griechen bekannt. Man muss einen langen Weg gehen, um alle Sackgassen zu erreichen, aber am Ende wird das Ziel erreicht. Obwohl diese Regel einen Nachteil hat, werden wir später darüber sprechen.

Versuchen wir, einen Roboter zu beschreiben, der nach der Regel der "rechten Hand" handelt.

Zu Beginn seiner Arbeit muss der Roboter die Wand finden, entlang der er folgen wird. Dazu kann er sich einfach vorwärts bewegen, bis er auf ein Hindernis stößt.

Nachdem der Roboter auf ein Hindernis gestoßen ist, beginnt er sich gemäß der Regel der "rechten Hand" zu bewegen.

Während der Bewegung entlang der Wand überwacht der Roboter, ob sich rechts ein Durchgang befindet. Wenn es einen Durchgang gibt, muss der Roboter daran entlang gehen, um sich nicht von der Wand nach rechts loszureißen.

Wenn es vor der Wand keinen Durchgang gibt, dreht sich der Roboter nach links. Wenn es wieder keinen Durchgang gibt, dreht es sich wieder nach links, also um 180 Grad, und geht in die entgegengesetzte Richtung.

Das Blockschaltbild des Algorithmus für einen Roboter, der nach der "Rechtsregel" arbeitet, ist in der Abbildung dargestellt.


Lassen Sie uns versuchen, die Funktionsweise dieses Algorithmus zu überprüfen und ein Programm dafür zu schreiben. Zu diesem Zweck wenden wir uns der GameLogo-Programmierumgebung zu. Diese Umgebung ist ein praktisches Werkzeug zur Modellierung verschiedener Algorithmen im Zusammenhang mit der Robotersteuerung. Es hat eine Darstellerschildkröte, die im Wesentlichen nichts anderes als ein echter Roboter ist. Die Schildkröte hat eine sehr bequeme Reihe von Befehlen - vorwärts, rechts, links, zurück. Außerdem befindet sich in der Mitte der Schildkröte ein Sensor, der je nach Farbton der Oberfläche, auf der er sich befindet, einen Wert zwischen 0 und 100 annimmt.

Der Sprachdialekt des Logos, das wir verwenden, ist sehr einfach und Basic ähnlich. Hier können Sie sich mit den Sprachbefehlen vertraut machen. Ein kostenloser Download der GameLogo-Programmierumgebung ist hier. Die Größe der Distribution ist klein - nur 1 MB.

Im Archiv mit GameLogo gibt es Hintergründe mit Labyrinthen, von denen wir eines verwenden werden.

Ganz am Anfang des Programms geben wir der Schildkröte den Befehl, die Feder zu heben (standardmäßig hinterlässt die Schildkröte eine Spur).

Die Größe des Feldes beträgt 800 mal 600 Pixel. Die Startposition für die Schildkröte befindet sich bei den Koordinaten 115, 545 (weißes Quadrat).

Die Farbe der Wege des Labyrinths ist hell, der Sensor auf ihnen nimmt Werte über 50 an. Die Farbe der Wände des Labyrinths ist dunkel, der Wert des Sensors ist kleiner als 50. Der Ausgang des Labyrinths wird durch ein schwarzes Quadrat dargestellt, dessen Sensorwert über 0 liegt.

Wir werden ein variables Flag deklarieren, mit dem wir kontrollieren, ob der Ausgang aus dem Labyrinth erreicht wird.

Wir werden das Programm schreiben und es mit Hilfe des großen roten Knopfes mit der Aufschrift "Run" starten.

Wenn bekannt ist, dass das Labyrinth keine getrennten Wände hat, das heißt, dass es keine geschlossenen Wege gibt, über die Sie zum Ausgangspunkt zurückkehren können, wird ein solches Labyrinth als einfach verbunden bezeichnet, und es kann immer vollständig umgangen werden, indem die "Einhand" -Regel angewendet wird.

Wenn das Labyrinth freistehende Wände enthält, ist es nach der Einhandregel nicht immer möglich, alle Gänge und Sackgassen zu durchlaufen. Labyrinthe mit getrennten Wänden und geschlossenen Wegen werden als mehrfach verbunden bezeichnet. In diesem Fall können die mehrfach verbundenen Labyrinthe in zwei Gruppen unterteilt werden: ohne eine „Schleife“ um das Ziel (eine geschlossene Route umgeht das Ziel nicht) und mit einer geschlossenen „Schleife“ um das Ziel (das Ziel kann durch eine geschlossene Route umgangen werden).

In den mehrfach verbundenen Labyrinthen der zweiten Gruppe funktioniert die Einhandregel nicht und mit ihr ist es unmöglich, das Ziel zu erreichen. Aber auch diese Labyrinthe können mit einem exakten Algorithmus überwunden werden.

Die Lösung des Problems solcher Labyrinthe stammt aus einer relativ späten Zeit, und der Anfang wurde von Leonard Euler gelegt. Nicht ohne Grund glaubte Euler, dass sich ein Weg aus einem Labyrinth auf relativ einfache Weise finden lässt.

Der universelle Algorithmus zum Durchlaufen von Labyrinthen wurde erst ein Jahrhundert später in dem 1882 erschienenen Buch des französischen Mathematikers E. Luke "Recreations matematiques" beschrieben. Interessanterweise wies Luke bei der Beschreibung des Algorithmus auf den Vorrang eines anderen französischen Mathematikers, M. Tremot, hin. So wurde der Algorithmus als Luc-Tremo-Algorithmus bekannt.

Tremo bietet die folgenden Regeln an: Verlassen Sie einen beliebigen Punkt des Labyrinths, markieren Sie seine Wand (Kreuzung) und bewegen Sie sich in eine beliebige Richtung bis zu einer Sackgasse oder Kreuzung. Gehen Sie im ersten Fall zurück und setzen Sie ein zweites Kreuz, um anzuzeigen, dass der Weg zweimal hin und her gegangen ist , und gehen Sie in eine Richtung, die noch nie gefahren wurde, oder einmal, in die zweite - gehen Sie in eine beliebige Richtung und markieren Sie jede Kreuzung am Eingang und Ausgang mit einem Kreuz. Wenn es bereits ein Kreuz am Kreuz gibt, sollten Sie einen neuen Weg gehen, wenn nicht t - der zurückgelegte Weg, markiert ihn mit einem zweiten Kreuz.

Wenn Sie den Tremo-Algorithmus kennen, können Sie das Verhalten des legendären Theseus anpassen. Inspiriert von der Gabe seiner geliebten Ariadne geht er selbstbewusst durch das Labyrinth. Plötzlich steht vor ihm eine Bewegung, entlang der bereits ein Faden gespannt ist. Was zu tun ist? Sie kreuzen es auf keinen Fall, sondern kehren auf dem bereits bekannten Weg zurück und verdoppeln den Faden, bis Sie einen weiteren unerfüllten Zug finden.

Claude Elwood Shannon, der Vater der Informationstheorie, baute unter Verwendung einer Variante des Tremo-Algorithmus einen der ersten selbstlernenden Roboter. Shannon gab ihm den klangvollen Namen "Theseus", aber in der Geschichte von "Theseus" wurde er besser als die "Maus" von Shannon bekannt. Die „Maus“ untersuchte zuerst das gesamte Labyrinth und ging dann (zum zweiten Mal) viel schneller, um die Bereiche zu vermeiden, die zweimal passiert wurden.

Heutzutage nehmen Roboter, die das Labyrinth durchqueren, an einem der interessantesten Wettbewerbe von Denkmaschinen teil, die in mehreren Ländern der Welt stattfinden. Diese Wettbewerbe werden gemeinsam als Micromouse-Wettbewerb bezeichnet und gehören hinsichtlich ihrer technischen Innovationen zu den führenden Robotersportarten.

Bei der ersten russischen Olympiade der Roboter wurden Wettbewerbe ausgetragen, deren Ziel es war, durch eine Art Labyrinth zu laufen: In kürzester Zeit musste der Roboter durch die "offenen Türen" in den Wänden vom Startpunkt zum Zielort gelangen. Der Roboter konnte seine Bewegung entlang schwarzer Linien steuern, die auf dem Boden des Labyrinths gezeichnet waren.

REGEL EINER HAND

Es gibt eine sehr einfache Möglichkeit, ein Labyrinth zu betreten, ohne Angst zu haben, sich darin zu verlieren. Mit dieser Regel können Sie immer einen Weg aus einem Labyrinth finden, egal wie verwirrt die Übergänge sind. Hier ist die Regel für sicheres Wandern in Labyrinthen:

Es ist notwendig, durch das Labyrinth zu gehen und ständig mit der gleichen Hand die Wand zu berühren.

Dies bedeutet, dass Sie am Eingang des Labyrinths seine Wand mit einer Hand berühren müssen (egal, ob rechts oder links) und zum Zeitpunkt des Einwanderns die Wand weiterhin mit derselben Hand berühren müssen.

Versuchen Sie - um diese Methode auszuprobieren - die "Einhandregel" für einen mentalen Spaziergang entlang des Hampton Maze-Plans anzuwenden. Stellen Sie sich vor, Sie betreten mit einem Streichholz dieses Gartenlabyrinth und berühren mit einer Hand die Wände. Sie werden ziemlich bald vom äußeren Eingang in die Mitte des Labyrinths gelangen. Lassen Sie Ihre Hand hier nicht sinken, bewegen Sie sich weiter, berühren Sie sie mit den Wänden, und Sie werden genau wieder aus ihren Ecken zum äußeren Eingang gelangen.

Woher kam diese bequeme Regel? Wir werden versuchen, das zu verstehen. Stellen Sie sich vor, Sie haben die Augen verbunden und betreten einen Raum mit nur einem Eingang. Was sollten Sie tun, um alles zu umgehen und wieder herauszukommen? Am einfachsten geht man an den Wänden entlang, ohne die Hände von der Wand zu nehmen. Dann erreicht man mit Sicherheit wieder die Tür, durch die man eingetreten ist. Hier ist die Rationalität der „Einhandregel“ selbsterklärend. Stellen Sie sich jetzt vor, dass die Wände des Raums Vorsprünge haben, wie in Abb. 4 und 5. Bevor Sie nicht mehr einfache Räume, sondern echte Labyrinthe sind. Aber die "Einhandregel" sollte natürlich und in diesen Fällen ihre Stärke behalten und Sie zuverlässig zum Ausgang des Geländes zurückführen.

Die "Regel der einen Hand" hat ihre Unannehmlichkeiten. Mit ihm können Sie jedes Labyrinth betreten und sicher wieder verlassen. Dies bedeutet jedoch nicht, dass Sie ausnahmslos alle Ecken des Labyrinths umrunden. Sie werden nur jene Orte besuchen, deren Wände irgendwie mit der Außenwand des Labyrinths verbunden sind - sozusagen mit seiner Fortsetzung. Aber Sie werden an den Abschnitten des Labyrinths vorbeigehen, deren Wände keine Verbindung zu seinen Außenwänden haben. Im Hampton-Gartenlabyrinth gibt es einen solchen Ort, und daher können Sie nach der Einhandregel nicht alle Wege dieses Labyrinths durchlaufen: Ein Weg bleibt unerforscht. In Abb. 6 gestrichelte Linien zeigen den Weg an den Wänden der Hecke entlang, wenn Sie die "Einhandregel" verwenden, und das Sternchen markiert diese Gasse, die gleichzeitig unentdeckt bleibt.

Pin
Send
Share
Send
Send