Erstellen eines Labyrinth-Lösungsalgorithmus in Java
Mir wurde die Aufgabe zugewiesen, einen Labyrinthlöser in Java zu erstellen. Hier ist die Aufgabe:
%Vor%Das Zeichen 'X' steht für eine Wand oder eine blockierte Position und das Zeichen 'O' steht für ein freie Stelle. Sie können davon ausgehen, dass der Eingang zum Labyrinth immer in der unteren rechten Hand ist Ecke, und der Ausgang ist immer in der oberen linken Ecke. Ihr Programm sollte senden Ausgabe in eine Datei. Wenn ein Pfad gefunden wird, sollte die Ausgabedatei den Pfad enthalten. Wenn ein Pfad ist nicht gefunden, sollte eine Nachricht an die Datei gesendet werden. Bitte beachten Sie, dass ein Labyrinth mehr als haben kann ein Lösungsweg, aber in dieser Übung werden Sie nur gebeten, eine Lösung zu finden, nicht alle Lösungen.
Ihr Programm sollte einen Stapel verwenden, um den Pfad, den es gerade untersucht, aufzunehmen und zurückzuverfolgen erreicht eine blockierte Position.
Achten Sie darauf, einen vollständigen Algorithmus zu schreiben, bevor Sie Ihren Code schreiben. Fühlen Sie sich frei, irgendwelche zusätzlichen zu schaffen Klassen, die Ihnen helfen, die Aufgabe abzuschließen.
%Vor%Wie auch immer, was ich eingerichtet habe, ist eine Klasse Punkte, die Methoden für das Reisen in alle Himmelsrichtungen festgelegt / erhalten hat, die boolesche Werte wie folgt zurückgeben:
%Vor%}
Ich habe nur Probleme, die eigentliche Lösung hauptsächlich zu finden. Folgendes habe ich:
%Vor%Könnten Sie mir, abgesehen von Syntaxfehlern, Hilfe anbieten? Vielen Dank.
5 Antworten
Ich habe eine ähnliche Antwort hier Maze Solving Algorithm in C ++ eingereicht .
Um eine Chance zu haben, es zu lösen, sollten Sie:
- Erstellen Sie eine
Solve()-Routine und rekursiv selbst:- wenn 1., 2., 3., ... wahr sind
Solvehat erfolgreich eine Lösung gefunden - wenn 1., 2., 3., ... ein falsches enthält, muss es zurückgehen und einen anderen Weg finden
- wenn 1., 2., 3., ... wahr sind
- Sie müssen einen Puffer von Stellen erstellen, an denen Sie Endlosschleifen vermeiden wollten
- Wenn Sie Bewegungen ausführen, muss es darauf achten
- Wenn wir eine Sackgasse erreichen, müssen wir schlechte Züge löschen
- können wir das oben genannte implementieren, indem wir eine Schätzung einbrennen und sie entfernen, wenn sie falsch ist
Hier ist ein Pseudocode für die Lösung.
%Vor%Sie sollten wahrscheinlich Modul Ihr Programm - wie ich es verstehe, Sie lesen das Labyrinth aus Datei und versuchen zu löse es gleichzeitig.
Ein besserer Ansatz besteht darin, das Programm in zwei Teile aufzuteilen:
- lese die Eingabedatei und erstelle eine Matrix mit allen Daten
- löse das Labyrinth von der gegebenen Matrix
Dies wird Ihnen helfen, jedes Teil getrennt zu bauen und zu testen, was wahrscheinlich zu einem besseren, zuverlässigeren Programm führt.
Das Lösen des Labyrinths könnte durch ein einfaches BFS erfolgen, das dem ähnelt, was Ihr Algorithmus ursprünglich vorgeschlagen hat, Das ist ein DFS
Wie amit gesagt hat, sollten Sie zuerst das ganze Labyrinth lesen und es als zweidimensionales Array speichern. Dadurch können Sie das ganze Labyrinth sehen, ohne es Zeile für Zeile lösen zu müssen.
Da Sie zuerst die Größe des Arrays finden müssen, sollten Sie die Textdatei in eine Liste von Strings lesen.
%Vor%Die Größe der Liste gibt Ihnen die Anzahl der Zeilen und unter der Annahme, dass es immer ein Gitter ist, können Sie split (). length (Anzahl Leerzeichen + 1) verwenden oder die Symbole auf einem der Strings zählen Anzahl der Spalten.
Der einfachste Weg zum Speichern der Kartendaten ist ein 2D-Array von Booleschen Werten. Wo wahr ist eine Wand und falsch ist leerer Raum.
%Vor%Jetzt, da Sie die Kartendaten in einem Array gespeichert haben, ist es viel einfacher, die Karte zu durchlaufen und Ihre Auswahl zu treffen. Sie können entweder einen vorgefertigten Algorithmus verwenden (siehe Antwort von amit) oder Ihren eigenen erstellen. Da dies Hausaufgaben sind, sollten Sie versuchen, sich Ihre eigenen auszudenken.
Viel Spaß.
Sie müssen Ihr Programm in zwei Phasen trennen. Die erste ist die Initialisierung, wo Sie die Labyrinthbeschreibung und die Anfangsposition des Spielers lesen. Danach haben Sie eine Datenstruktur, um das Board zu repräsentieren. Der zweite ist das eigentliche Spiel, wo es 3 Abstraktionen geben sollte:
- Der Spielerstatus. In Ihrem Fall ist es ziemlich einfach, seine tatsächliche Position auf dem Brett.
- Das Labyrinth selbst, welches die Umgebung ist. Es sollte Funktionen haben, die dir sagen, ob du eine bestimmte Position besucht hast, um die Position zu markieren, die du besucht hast, wo das Ziel ist, die nächsten erreichbaren Zellen, etc ...
- Die Logik, die der Suchalgorithmus ist.
Irgendwelche von diesen sollten sich ohne viel Änderung der anderen ändern können. Beispielsweise werden Sie möglicherweise aufgefordert, Ihren Suchalgorithmus zu verbessern, oder ein Problem, bei dem Sie mehr als ein Ziel haben. Die Leichtigkeit, von dem gegenwärtigen Problem zu einem leicht modifizierten zu wechseln, ist die wahre Metrik eines Programmentwurfs.
Ich habe versucht, dies mit dem DFS-Algorithmus unter Verwendung einiger Java-OOP-Konzepte zu implementieren.
Siehe vollständige Lösung auf meinem github-Repository
%Vor%}