Breite-zuerst Suche auf einem 8x8 Raster in Java

Sie müssen 2 Dinge in Ihrer Warteschlange speichern. Lassen Sie uns jedes Element in Ihrer Warteschlange einen Knoten nennen.

1. Position (die Sie bereits speichern)
2. count (Bewegungen, die benötigt werden, um von der Startposition zu dieser Position zu gelangen)

Sie beginnen damit, dass Sie die Anzahl Ihrer Startposition auf 0 setzen.

Die Funktionsweise des Algorithmus ist:

1. Sie knacken einen Knoten aus der Warteschlange
2. Sie bestimmen, wohin Sie von der Position springen können, die durch den gerade geklickten Knoten angegeben wurde. Das heißt, wenn Sie dies als "einen Baum im laufenden Betrieb erstellen" behandeln, bestimmen Sie die untergeordneten Elemente des Knotens, den Sie aus der Warteschlange ausgewählt haben
3. Sie fügen diese untergeordneten Elemente der Warteschlange hinzu.

Wenn Sie in Ihrem dritten Schritt ein untergeordnetes Knot zur Warteschlange hinzufügen, müssen Sie die Anzahl ermitteln, die diesem Knoten hinzugefügt werden muss. Diese Anzahl ist einfach die count of the parent node (that you popped in step 1) + 1

Schließlich ist Ihr Rückgabewert der Zählwert, der dem Knoten zugeordnet ist, der die Zielposition enthält.

Lassen Sie uns zum Beispiel mit einem 4x4-Gitter arbeiten, wobei Position [0,0] der Anfang und Position [0,3] das Ziel ist.

Zu Beginn wäre Ihre Warteschlange:

wobei der Wert innerhalb der () die Position ist und der zweite Wert innerhalb der {} die Anzahl.

Sie knacken diesen Knoten aus Ihrer Warteschlange und Sie bestimmen, dass Sie die Positionen (0,1) und (1,0) erreichen können. Daher fügen Sie der Warteschlange die Elemente {(0, 1), 1} und {(1, 0), 1} hinzu. Beachten Sie, dass der Zählerstand 1 ist, da der Wert des Popup-Knotens 0 war und wir diesen um 1 erhöht haben. Ihre Warteschlange sieht nun so aus:

Du platzierst das erste Element, erkennst, dass es keine brauchbaren Kinder hat, also gehst du weiter.

Sie poppen das verbleibende Element und finden heraus, dass es Ihnen einen Knoten gibt, den Sie erreichen können, an der Position (2, 0). Da der von Ihnen aufgerufene Knoten den Wert 1 hat, fügen Sie diese neue Position mit count = 1 + 1 = 2 zur Warteschlange hinzu.

Schließlich werden Sie den Zielknoten aus Ihrer Warteschlange entfernen, und die Zählung wird 9 sein.

Bearbeiten

Wenn Sie den Pfad von der Quelle zum Ziel abrufen möchten, funktioniert die aktuelle Codierung nicht so wie sie ist. Sie müssten ein separates 2D-Array der Größe 8x8 mit den Zählwerten verwalten, anstatt sie im Knoten selbst zu codieren. Und wenn Sie schließlich die Anzahl für das Ziel gefunden haben, fahren Sie mit dem 2D-Zählfeld vom Ziel zurück zur Quelle. Wenn Sie in 9 Zügen an das Ziel gelangen, können Sie in 8 Zügen zu einer der angrenzenden Positionen gelangen. Sie finden also die Position mit der Nummer 8, die neben dem Ziel liegt. Sie wiederholen dies iterativ, bis Sie zur Quelle gelangen.

Die von Ihnen beschriebene Methode, bei der Sie den Knoten ein zusätzliches Element hinzufügen, funktioniert nicht. Ich überlasse es dir herauszufinden, warum, denn das sind Hausaufgaben :)

Hier ist eine schöne kurze Alternative zu Ihrem Code. Genau die gleiche Idee, aber keine Notwendigkeit der so vielen 'Wenn'-Bedingungen, wo Sie die Gültigkeit jeder Koordinate überprüfen. Das alles kann in einem Rutsch erledigt werden. Guck mal.

Ich habe die Erklärung so oft kommentiert wie ich konnte. Es ist auch für Leute, die nicht wissen, lesbar. Ich bin zufällig auf Ihre Frage gestoßen, als ich eine Lösung für ein ähnliches (dasselbe?) Problem implementierte, bei dem ein in einem Labyrinth gefangener Typ seinen Weg finden musste. Es gab Fallen (B) und bewegliche Bereiche (E) im Gitter. Das Ziel war es, sein Ziel zu erreichen (G).

Wie auch immer, hier ist der verallgemeinerte Code. Ich nehme das Nein von Zeilen, Spalten und dann das komplette Raster auf. Ich drucke nur, ob es möglich ist, das Ziel zu erreichen oder nicht. Ich überlasse den Rest jemandem, der dies liest, um sicherzugehen, dass Sie den Code verstanden haben;)

Beachten Sie, dass das Hauptziel meiner Antwort darin besteht, Ihnen zu zeigen, dass die Größe Ihrer BFS-Funktion reduziert werden könnte . Ich poste meine gesamte Lösung, nur um die allgemeine Idee von BFS in einem Raster zu geben, da ich während des Lernens Schwierigkeiten hatte. Hoffentlich hilft das jemandem, der in derselben Situation steckt. Wenn Sie die Position oder den Pfad befolgen möchten, folgen Sie den Anweisungen aus den Antworten in dieser Frage. Mach es selbst;)

Code in Aktion: Ссылка

Irgendwelche Vorschläge sind sehr willkommen. Prost: D