Labyrinth Lösen

Lösungs-Labyrinth

Die Frage muss in unseren cleveren Labyrinthrätseln gelöst werden. Tipp: Bringen Sie einen oder mehrere Stifte mit, um die Rätsel zu lösen. Der Weg im Labyrinth kann von einem "Off-Road"-Kinderwagen benutzt werden. Animierte Breitensuche: Das fertige Labyrinth:. Ein Maze-a-Pix kann zwischen fünf Minuten und mehreren Stunden dauern.

Labyrinthproblem - Computerwissenschaft

Sie wollen ein beliebiges Labyrinth verlassen, wenn es existiert. Hierzu benötigen Sie zunächst ein Labyrinth, das auch grafisch dargestellt werden kann. Jede beliebige Teillösungskombination wird in Rekursionen erprobt, bis eine lösungsorientierte Komplettlösung vorliegt oder klar ist, dass es keine gibt.

Beim Labyrinth-Problem ist ein Pseudocode-Algorithmus von Wirth vordefiniert: Zuerst wird eine Richtungsvorgabe getroffen, in die der Pfadfinder zuerst gehen soll. Der Suchvorgang ist als erfolglos gekennzeichnet. Die erste Stufe wird anhand der Initialisierungsrichtung angewählt. Falls ein eventueller Arbeitsschritt zum Ergebnis führen sollte, ist die Suche abgeschlossen und wird beendet.

Ansonsten gehen Sie einen weiteren Arbeitsschritt weiter und führen die gleiche Vorgehensweise erneut durch (rekursiv). Es werden die letzen drei Stufen so lange durchgeführt, bis der Output erreicht ist (erfolgreich) oder alle Himmelsrichtungen getestet wurden (keine weitere Möglichkeit). Es gibt zwei Möglichkeiten, den Auswahlprozess zu initialisieren, d.h. die Ausrichtung zu wählen, in die er zuerst gehen soll.

Zum einen kann man gezielt verfahren, d.h. an jeder Ecke immer zuerst in die selbe Fahrtrichtung gehen und dann die anderen Fahrtrichtungen im Uhrzeigersinn nachprüfen. Dies wäre wie die Suche nach dem Weg in einem Labyrinth mit einem Kompaß, zum Beispiel immer zuerst nach Süd oder Nord. Abhängig davon, wo sich das Target befindet und wie das Labyrinth aussieht, kann eine Seite sowohl hinsichtlich der Lösungslänge als auch der Suchdauer vorteilhafter sein als die andere.

Im Beispiel ist "nach links" die Ausrichtung, die eine kurze Lösung bietet und nur ein wenig vom Labyrinth sucht. "Up " bietet den gleichen Weg, hat aber zuvor das ganze Labyrinth durchsucht. Bei der zweiten Möglichkeit der Richtungsauswahl wird die erste Drehrichtung an jeder Schnittstelle nach dem Zufallsprinzip ausgewählt und dann im Uhrzeigersinn nachgestellt.

Im Pseudocode "Select first/next step off" wird ein Step aus der vorhergehenden Zeile fortgesetzt. Wenn Sie prüfen wollen, ob ein Step von der momentanen Stelle aus in eine gewisse Richtung möglich ist, ist es ratsam, eine GibStep-Abfrage zu erstellen, die im Fall eines Steps das zurückliefert, was an der nächstfolgenden Stelle sein würde.

Bei einer zweiten GibMöglich-Abfrage wird durch Vergleich des Wertes mit den zum Gehen freigegeben Werte bestimmt, ob der Arbeitsschritt möglich ist. Mit der oben genannten GibStep-Abfrage kann bestimmt werden, ob ein Step Erfolg reich zum Target hat. Weil der Rekursivaufruf von der neuen Stelle aus ausgeführt werden soll, ist es am besten, ihn sofort nach Ausführung des eigentlichen Schritts durchzuführen, da die neuen Positionen errechnet werden.

Der Rekursionsvorgang wird abgebrochen, wenn alle Möglichkeiten fehlgeschlagen sind oder das Target aufgedeckt wurde. Sie befinden sich im ersten Falle an einer Stelle, an der alle bisherigen Anrufe (alle Richtungen) bereits fehlgeschlagen sind. Wird die Destination ermittelt, muss diese an die vorhergehenden Anrufe zurückgesendet werden, die dies möglicherweise nicht wissen, so dass sie ebenfalls abgebrochen werden.

Die Erzeugung eines Labyrinthes ist im Grunde nur eine Erleichterung der Pfadsuche, da die Abortbedingung für das gefundene Target ausgelassen wird. Zuerst wird das Labyrinth vollständig mit Mauern ausgefüllt. Für ein brauchbares Labyrinth ist es zweckmäßig, wenigstens zwei Stufen auf einmal in die selbe Fahrtrichtung zu gehen, da dies besser ist.

In einem Labyrinth, in dem es keine "Schleifen" (die Möglichkeiten, im Kreise zu laufen) gibt, z.B. in einem wie oben beschriebenen Labyrinth, ist diese Verlängerung nicht besonders nützlich. Wie man hier sieht, ist das eigentliche Hauptproblem, dass zwar anerkannt wird, wenn ein Weg nicht zum Ziel führt, aber nicht, dass man bereits in dieser Lage war und dass sich nur der Weg zu dieser Lage geändert hat.

Markieren Sie jedoch den erfolglosen Pfad, so ist gewährleistet, dass er nur einmal pro Planstelle eingetragen wird. Das Ungeheuer, das den vorgefundenen Pfadfinder auffrisst, wandert wiederholt durch das Labyrinth. Die Zielscheibe des Ungeheuers verschiebt sich und so könnte im Falle einer Berufung ein soeben ohne Erfolg gegangener Weg im folgenden Augenblick gelingen.

Allerdings darf die Entscheidung, in welche Richtungen das Ungeheuer seinen Weg geht, nicht dem Schicksal des Ungeheuers überlassen werden. Das kann man z.B. so erreichen (konkretes Beispiel): Für ein Ungeheuer benötigt man auch eine Anfrage, die festlegt, ob ein Step möglich ist, da es auch erlaubt ist, den Pfad und die gekennzeichneten Bereiche einzugeben.

Es muss also einen Cache haben, der sich daran erinnert, was an der Stelle passiert ist, wo sich das Ungeheuer aufhält. Die Monsterkarte wird sowohl bei der Vorwärtsbewegung als auch bei der Rückwärtsbewegung platziert. Außerdem muss der Pfad-Suchalgorithmus um eine Beendigungsbedingung Eaten by monster ergänzt werden.

Der Erweiterungsbaustein, den Sie zuerst einen oder mehrere Tasten für das freizugebende Ergebnis ermitteln müssen, setzt sich im Wesentlichen aus zwei separaten Suchvorgängen zusammen. Zunächst werden alle Tasten durchsucht und die Abbruchbedingungen des Ziels unterdrückt. Sind alle Tasten vorhanden, wird die Suche abgebrochen und die Suche nach dem gewünschten Ort von Anfang an wiederaufgenommen.

In der Praxis werden Sie in der Regel glücklich sein, den Weg aus einem Labyrinth herausgearbeitet zu haben. Wie immer suchen Sie nach dem Exit, wenn Sie ihn finden, merken (speichern) Sie sich den Pfad und versuchen Sie, auf andere Weise wieder dahin zu kommen (Sie müssen vermeiden, die Abbruch-Bedingung des Ziels zu finden).

Mehr zum Thema