Verfolgen Sie die besuchten Staaten in der Breitensuche

Also habe ich versucht, BFS auf einem Sliding Blocks-Puzzle (Nummerntyp) zu implementieren . Die Hauptsache, die mir aufgefallen ist, ist, dass wenn Sie ein 4*4Board haben, die Anzahl der Zustände so groß sein kann, 16!dass ich nicht alle Zustände vorher aufzählen kann.

Meine Frage ist also, wie ich bereits besuchte Staaten im Auge behalten kann. (Ich verwende eine Klassenplatine. Jede Klasseninstanz enthält ein eindeutiges Kartenmuster und wird durch Auflisten aller möglichen Schritte aus dem aktuellen Schritt erstellt.)

Ich habe im Internet gesucht und anscheinend kehren sie nicht zum gerade abgeschlossenen vorherigen Schritt zurück, ABER wir können auch auf einem anderen Weg zum vorherigen Schritt zurückkehren und dann alle zuvor besuchten Schritte erneut aufzählen. Wie kann man also die besuchten Staaten verfolgen, wenn noch nicht alle Staaten aufgezählt wurden? (Der Vergleich bereits vorhandener Zustände mit dem aktuellen Schritt ist kostspielig).

Sie können a set(im mathematischen Sinne des Wortes, dh eine Sammlung, die keine Duplikate enthalten kann) verwenden, um bereits gesehene Zustände zu speichern. Die Operationen, die Sie ausführen müssen, sind:

• Elemente einfügen
• Testen, ob bereits Elemente vorhanden sind

Nahezu jede Programmiersprache sollte bereits eine Datenstruktur unterstützen, die beide Operationen in konstanter ( ) Zeit ausführen kann . Zum Beispiel:$O(1)$

• set in Python
• HashSet in Java

Auf den ersten Blick mag es so aussehen, als wäre das Hinzufügen aller Zustände, die Sie jemals zu einem solchen Set gesehen haben, in Bezug auf den Speicher teuer, aber es ist nicht schlecht im Vergleich zu dem Speicher, den Sie bereits für Ihre Grenze benötigen. Wenn Ihr Verzweigungsfaktor , wächst Ihre Grenze um b - 1 Elemente pro Knoten, den Sie besuchen (entfernen Sie 1 Knoten von der Grenze, um sie zu "besuchen", fügen Sie b neue Nachfolger / Kinder hinzu), während Ihr Satz nur um 1 zusätzliche wächst Knoten pro besuchtem Knoten.$b$$b - 1$$1$$b$$1$

Im Pseudocode könnte eine solche Menge (nennen wir sie closed_set, um mit dem Pseudocode auf Wikipedia übereinzustimmen, in einer Breitensuche wie folgt verwendet werden:

frontier = First-In-First-Out Queue
frontier.add(initial_state)

closed_set = set()

while frontier not empty:
    current = frontier.remove_next()

    if current == goal_state:
        return something

    for each child in current.generate_children()
        if child not in closed_set:    // This operation should be supported in O(1) time regardless of closed_set's current size
            frontier.add(child)

    closed_set.add(current)    // this should also run in O(1) time

(Einige Variationen dieses Pseudocodes funktionieren möglicherweise auch und sind je nach Situation mehr oder weniger effizient. Sie können beispielsweise auch closed_setalle Knoten enthalten, von denen Sie bereits Kinder zur Grenze hinzugefügt haben, und den generate_children()Anruf dann vollständig vermeiden wenn currentist schon in der closed_set.)

Was ich oben beschrieben habe, wäre die Standardmethode, um dieses Problem zu lösen. Intuitiv vermute ich, dass eine andere "Lösung" darin bestehen könnte, die Reihenfolge einer neuen Liste von Nachfolgestaaten immer zufällig zu ordnen, bevor sie zur Grenze hinzugefügt werden. Auf diese Weise vermeiden Sie nicht das Problem, gelegentlich Zustände hinzuzufügen, die Sie bereits zuvor an die Grenze erweitert haben, aber ich denke, dies sollte das Risiko, in unendlichen Zyklen stecken zu bleiben, erheblich verringern.

Seien Sie vorsichtig : Ich kenne keine formale Analyse dieser Lösung, die beweist, dass sie immer unendliche Zyklen vermeidet. Wenn ich versuche, dies intuitiv durch meinen Kopf zu "laufen", vermute ich, dass es irgendwie funktionieren sollte und keinen zusätzlichen Speicher benötigt. Es kann Randfälle geben, an die ich momentan nicht denke, daher funktioniert es möglicherweise auch nicht. Die oben beschriebene Standardlösung ist sicherer (auf Kosten von mehr Speicher).

Die Antwort von Dennis Soemers ist richtig: Sie sollten ein HashSet oder eine ähnliche Struktur verwenden, um die besuchten Zustände in der BFS-Diagrammsuche zu verfolgen.

Ihre Frage wird jedoch nicht ganz beantwortet. Sie haben Recht, im schlimmsten Fall müssen Sie bei BFS 16 speichern! Knoten. Auch wenn die Einfüge- und Überprüfungszeiten im Set O (1) sind, benötigen Sie dennoch eine absurde Menge an Speicher.

Verwenden Sie kein BFS, um dies zu beheben . Es ist für alle außer den einfachsten Problemen unlösbar, da es sowohl Zeit als auch Speicher benötigt , die in der Entfernung zum nächsten Zielzustand exponentiell sind.

Ein viel speichereffizienterer Algorithmus ist die iterative Vertiefung . Es hat alle wünschenswerten Eigenschaften von BFS, verwendet jedoch nur O (n) -Speicher, wobei n die Anzahl der Bewegungen ist, um die nächste Lösung zu erreichen. Es kann noch eine Weile dauern, aber Sie werden die Speichergrenzen lange vor den CPU-bezogenen Grenzen erreichen.

Besser noch, entwickeln Sie eine domänenspezifische Heuristik und verwenden Sie die A * -Suche . Dies sollte erfordern, dass Sie nur eine sehr kleine Anzahl von Knoten untersuchen und die Suche in einer Weise durchführen, die der linearen Zeit viel näher kommt.

Während die gegebenen Antworten im Allgemeinen zutreffen, ist ein BFS im 15-Puzzle nicht nur durchaus machbar, es wurde 2005 durchgeführt! Das Papier, das den Ansatz beschreibt, finden Sie hier:

http://www.aaai.org/Papers/AAAI/2005/AAAI05-219.pdf

Einige wichtige Punkte:

• Dazu wurde externer Speicher benötigt - das heißt, das BFS verwendete die Festplatte anstelle von RAM als Speicher.
• Es gibt tatsächlich nur 15! / 2 Zustände, da der Zustandsraum zwei für beide Seiten nicht erreichbare Komponenten hat.
• Dies funktioniert im Schiebepuzzle, da die Zustandsräume von Level zu Level sehr langsam wachsen. Dies bedeutet, dass der für jede Ebene erforderliche Gesamtspeicher weitaus kleiner ist als die volle Größe des Statusraums. (Dies steht im Gegensatz zu einem Zustandsraum wie Rubik's Cube, in dem der Zustandsraum viel schneller wächst.)
• Da das Schiebepuzzle ungerichtet ist, müssen Sie sich nur um Duplikate in der aktuellen oder vorherigen Ebene kümmern. In einem gerichteten Raum können Sie in jeder vorherigen Ebene der Suche Duplikate erzeugen, was die Sache viel komplizierter macht.
• In der Originalarbeit von Korf (oben verlinkt) wurde das Ergebnis der Suche nicht gespeichert - die Suche berechnete nur, wie viele Zustände sich auf jeder Ebene befanden. Wenn Sie die ersten Ergebnisse speichern möchten, benötigen Sie etwas wie WMBFS ( http://www.cs.du.edu/~sturtevant/papers/bfs_min_write.pdf ).
• Es gibt drei Hauptansätze zum Vergleichen von Zuständen aus den vorherigen Schichten, wenn Zustände auf der Festplatte gespeichert werden.
  • Der erste ist sortierungsbasiert. Wenn Sie zwei Nachfolgerdateien sortieren, können Sie sie in linearer Reihenfolge scannen, um Duplikate zu finden.
  • Der zweite basiert auf Hash. Wenn Sie eine Hash-Funktion verwenden, um Nachfolger in Dateien zu gruppieren, können Sie Dateien laden, die kleiner als der gesamte Statusbereich sind, um nach Duplikaten zu suchen. (Beachten Sie, dass es hier zwei Hash-Funktionen gibt - eine zum Senden eines Status an eine Datei und eine zum Unterscheiden von Status innerhalb dieser Datei.)
  • Die dritte ist die strukturierte Duplikaterkennung. Dies ist eine Form der Hash-basierten Erkennung, die jedoch so durchgeführt wird, dass Duplikate sofort beim Generieren überprüft werden können, anstatt nachdem sie alle generiert wurden.

Hier gibt es noch viel mehr zu sagen, aber die obigen Papiere enthalten viel mehr Details.

Ironischerweise lautet die Antwort: "Verwenden Sie ein beliebiges System." Ein HashSet ist eine gute Idee. Es stellt sich jedoch heraus, dass Ihre Bedenken hinsichtlich der Speichernutzung unbegründet sind. BFS ist bei solchen Problemen so schlecht, dass es dieses Problem für Sie löst.

Beachten Sie, dass Ihr BFS erfordert, dass Sie einen Stapel unverarbeiteter Zustände behalten. Während Sie das Rätsel lösen, werden die Zustände, mit denen Sie sich befassen, immer unterschiedlicher, sodass Sie wahrscheinlich feststellen werden, dass jede Lage Ihres BFS die Anzahl der zu betrachtenden Zustände mit ungefähr 3 multipliziert.

Dies bedeutet, dass Sie bei der Verarbeitung der letzten Lage Ihres BFS mindestens 16! / 3 Zustände im Speicher haben müssen. Unabhängig davon, welchen Ansatz Sie verwendet haben, um sicherzustellen, dass die Anpassung in den Speicher ausreicht, um sicherzustellen, dass Ihre zuvor besuchte Liste auch in den Speicher passt.

Wie andere bereits betont haben, ist dies nicht der beste Algorithmus. Verwenden Sie einen Algorithmus, der besser zum Problem passt.

Das 15-Puzzle-Problem wird auf einem 4x4-Brett gespielt. Die Implementierung im Quellcode erfolgt schrittweise. Zunächst muss die Game Engine selbst programmiert werden. Dies ermöglicht es, das Spiel von einem menschlichen Bediener zu spielen. Das 15-Puzzle-Spiel hat nur ein freies Element und auf diesem Element werden die Aktionen ausgeführt. Die Spiel-Engine akzeptiert vier mögliche Befehle: links, rechts, oben und unten. Andere Aktionen sind nicht erlaubt und es ist möglich, das Spiel nur mit diesen Anweisungen zu steuern.

Die nächste Ebene zum Spielen des Spiels ist eine GUI. Dies ist sehr wichtig, da hiermit die Spiel-Engine getestet und versucht werden kann, das Spiel von Hand zu lösen. Eine grafische Benutzeroberfläche ist ebenfalls wichtig, da wir potenzielle Heuristiken ermitteln müssen. Und jetzt können wir über die KI selbst sprechen. Die KI muss Befehle an die Spiel-Engine senden (links, rechts, oben und unten). Ein naiver Ansatz für einen Löser wäre ein Brute-Force-Suchalgorithmus, was bedeutet, dass die KI zufällige Befehle sendet, bis der Zielzustand erreicht ist. Eine fortgeschrittenere Idee besteht darin, eine Art Musterdatenbank zu implementieren, die den Zustandsraum reduziert. Die Breitensuche ist keine direkte Heuristik, sondern ein Anfang. Es ist gleichbedeutend mit der Erstellung eines Diagramms zum chronologischen Testen möglicher Bewegungen.

Das Verfolgen vorhandener Zustände kann mit einem Diagramm erfolgen. Jeder Status ist ein Knoten, hat eine ID und eine übergeordnete ID. Die KI kann Knoten im Diagramm hinzufügen und löschen, und der Planer kann das Diagramm lösen, um einen Pfad zum Ziel zu finden. Aus programmtechnischer Sicht ist eine Game-Engine des 15-Puzzles das Objekt und die Liste vieler Objekte ist eine Arrayliste. Sie werden in einer Diagrammklasse gespeichert. Dies im Quellcode zu realisieren ist etwas schwierig. Normalerweise schlägt der erste Versuch fehl und das Projekt führt zu vielen Fehlern. Um die Komplexität zu bewältigen, wird ein solches Projekt normalerweise in einem akademischen Projekt durchgeführt, dh es ist ein Thema zum Schreiben einer Arbeit darüber, die 100 Seiten und mehr umfassen kann.

Ansätze zum Spiel

$16!$

Diese trivialen Tatsachen sind jedoch nicht relevant, wenn das Ziel darin besteht, das Rätsel in den wenigsten Rechenzyklen zu lösen. Die Breitensuche ist kein praktischer Weg, um ein orthogonales Bewegungsrätsel zu lösen. Die sehr hohen Kosten einer umfassenden ersten Suche wären nur dann erforderlich, wenn die Anzahl der Züge aus irgendeinem Grund von größter Bedeutung ist.

Teilsequenz Abstieg

Die meisten Eckpunkte, die Zustände darstellen, werden niemals besucht, und jeder besuchte Zustand kann zwischen zwei und vier ausgehende Kanten haben. Jeder Block hat eine Anfangsposition und eine Endposition und die Platine ist symmetrisch. Die größte Wahlfreiheit besteht, wenn der offene Raum eine der vier Mittelpositionen ist. Das geringste ist, wenn der offene Raum eine der vier Eckpositionen ist.

Eine vernünftige Disparitäts- (Fehler-) Funktion ist einfach die Summe aller x Disparitäten plus die Summe aller y Disparitäten und eine Zahl, die heuristisch darstellt, welche der drei Ebenen der Bewegungsfreiheit aufgrund der resultierenden Platzierung des offenen Raums (Mitte, Kante) existiert , Ecke).

Obwohl sich Blöcke vorübergehend von ihren Zielen entfernen können, um eine Strategie zur Fertigstellung zu unterstützen, die eine Abfolge von Zügen erfordert, gibt es selten einen Fall, in dem eine solche Strategie acht Züge überschreitet und durchschnittlich 5.184 Permutationen erzeugt, für die die Endzustände verglichen werden können unter Verwendung der obigen Disparitätsfunktion.

Wenn der leere Raum und die Positionen der Blöcke 1 bis 15 als Array von Halbbytes codiert sind, sind nur Additions-, Subtraktions- und bitweise Operationen erforderlich, was den Algorithmus schnell macht. Das Wiederholen der Brute-Force-Strategien mit acht Zügen kann wiederholt werden, bis die Disparität auf Null fällt.

Zusammenfassung

Dieser Algorithmus kann nicht zyklisch arbeiten, da immer mindestens eine der Permutationen von acht Zügen vorhanden ist, die die Disparität unabhängig vom Anfangszustand verringert, mit Ausnahme eines bereits abgeschlossenen Startzustands.