¶ Fifteen-Puzzle
Das 15-Puzzle, auch als Schiebepuzzle oder Schieberätsel bekannt, ist ein klassisches Rätselspiel. Es besteht aus einem 4x4-Rahmen mit 15 verschiebbaren, quadratischen Spielsteinen. Ein Feld bleibt immer leer, um die Bewegung der Steine zu ermöglichen.[1]
¶ Spielregeln des 15-Puzzles:
Beim 15-Puzzle beginnt das Spiel mit einer zufälligen Anordnung der 15 Spielsteine innerhalb eines Rahmens, wobei ein Feld frei bleibt, um die Bewegung der Steine zu ermöglichen. Das Ziel des Spiels ist es, diese Steine in aufsteigender numerischer Reihenfolge von 1 bis 15 zu ordnen. Dabei soll die Anordnung mit der Zahl 1 in der oberen linken Ecke beginnen und mit der Zahl 15 in der unteren rechten Ecke enden, direkt neben dem leeren Feld.
Um die Steine zu bewegen, schieben die Spieler jeweils einen Stein, der direkt an das leere Feld angrenzt, in dieses Feld. Dies ermöglicht es, einen Stein nach dem anderen zu verschieben. Wichtig ist dabei, dass immer nur ein Stein gleichzeitig bewegt werden kann und dass nur die Steine beweglich sind, die unmittelbar neben dem leeren Feld liegen.
¶ Lösbarkeit
Ein wichtiger Aspekt beim Lösen des 15-Puzzles ist die Erkenntnis, dass von den 15! möglichen Konfigurationen nur die Hälfte lösbar ist. Die Lösbarkeit eines Puzzles wird durch das Paritätskriterium bestimmt. In diesem Zusammenhang beschreibt Parität, ob die Anzahl der Vertauschungen, die notwendig sind, um die Kacheln von einer beliebigen Startkonfiguration in die Zielanordnung zu überführen, gerade oder ungerade ist. Eine Permutation der Kacheln im 15-Puzzle wird als lösbar eingestuft, wenn sie eine gerade Parität aufweist. Zusätzlich muss die Taxicab Distanz, also die Anzahl der horizontalen und vertikalen Bewegungen, die notwendig sind, um das leere Feld von seiner Position in der Anfangskonfiguration zur unteren rechten Ecke des Spielfelds zu bewegen, in die Gesamtparität einbezogen werden. Ein Puzzle ist demnach lösbar, wenn die Gesamtparität aus der Permutation der Kacheln und der Taxicab Distanz des leeren Feldes gerade ist.[2] [3]
¶ komplexität
Das 15-Puzzle, stellt eine Herausforderung für Suchalgorithmen dar. Es wurde festgestellt, dass das Puzzle aus jeder Startposition in maximal 80 Zügen lösbar ist, wobei der durchschnittliche Lösungsweg etwa 52,6 Züge umfasst. Darüber hinaus ist das allgemeinere Problem, die minimale Anzahl von Zügen für die Lösung eines n x n-Puzzles zu finden, als NP-schwer
klassifiziert.[1:1]
¶ Lösungsansätze
Im Bereich der heuristischen Suchalgorithmen sind der A*- und der IDA*-Algorithmus zwei führende Methoden für heuristische Suchvorgänge. Sie werden oft verwendet, um Lösungen für das Fünfzehn-Puzzle zu finden, ein Spiel, bei dem es darum geht, eine Anordnung von Zahlen in eine bestimmte Reihenfolge zu bringen. [4]
Der A*-Algorithmus ist besonders bekannt für seine Fähigkeit, den kürzesten Weg oder die geringste Anzahl von Zügen von einem Startzustand zu einem Zielzustand zu ermitteln. Ein Hauptnachteil des A*-Algorithmus ist jedoch sein hoher Speicherbedarf. Bei komplexen Puzzles, wo Milliarden von möglichen Zügen berücksichtigt werden müssen, speichert A* jeden einzelnen untersuchten Knoten (Zustand des Puzzles) im Speicher. Dies kann zu einem enormen Speicherverbrauch führen. [5]
Der IDA*-Algorithmus stellt eine Abwandlung des A*-Algorithmus dar, die sich für die Lösung des 15-Puzzle eignet und implementiert werden kann. Eine Eigenschaft von IDA* ist, dass es keine erweiterten Knoten im Speicher ablegt. Diese Vorgehensweise führt zu einem geringeren Speicherbedarf und ermöglicht es IDA*, Knoten schneller zu erweitern im Vergleich zum A*-Algorithmus.[6]
¶ A* Anwendung auf 15-Puzzle
Beim Anwenden des A*-Algorithmus auf das 15-Puzzle werden spezifische Anpassungen für das Puzzle vorgenommen.
Dabei wird jeder Zustand des Puzzles als ein Knoten im Graphen betrachtet. Der A*-Algorithmus sucht den kürzesten Weg vom Startzustand zum Zielzustand.
A* verwendet eine Bewertungsfunktion , wobei:
-
die Anzahl der Züge, die benötigt werden, um von der Anfangsanordnung zu einem bestimmten Knoten n zu gelangen.
-
st eine Schätzung der verbleibenden Züge vom aktuellen Knoten zum Ziel. Eine gängige Heuristik hierfür ist die Summe der Manhattan-Distanz aller Kacheln zu ihren Zielpositionen.
Der Algorithmus erweitert die Knoten mit den niedrigsten -Werten und führt dies fort, bis die Zielanordnung gefunden ist. A* ist effektiv in der Lösung von 15-Puzzle-Problemen, wenn eine geeignete Heuristik verwendet wird, die die Anzahl der verbleibenden Züge nicht überschätzt.[5:1]
¶ bidirektionale A*-Algorithmus (BA*)
Der bidirektionale A*-Algorithmus, kurz BA*, ist eine Variante des klassischen A*-Suchalgorithmus. Bei BA* wird gleichzeitig von zwei entgegengesetzten Endpunkten - dem Start- und Zielzustand - gesucht, um einen Pfad zwischen ihnen zu finden. Dieser Ansatz kann effizienter sein, da die beiden Suchvorgänge sich treffen sollen und dadurch möglicherweise die Gesamtgröße des zu durchsuchenden Suchraums reduziert wird.
¶ Pseudocode (angepasst)
Dieser Pseudocode ist aus dem Werk von Hasan, Dler O., et al.[7]
function BA* (StartState, GoalState)
Initialise:
IteratorF to control the loop
OpenListF to store the states to be traversed
ClosedListF to store already traversed states
OpenListB to store the states to be traversed
ClosedListB to store already traversed states
if IteratorF = 0 then
set depth cost of StartState (g(s) in Equation (2)) to zero
calculate HH value from StartState to GoalState. Equation (3)
calculate evaluation function for StartState. Equation (2)
add StartState into OpenListF and ClosedListF
while OpenListF is not empty do
CurrentStateF is state with lowest evaluation function value (Equation (2)) in OpenListF
remove CurrentStateF from OpenListF
if CurrentStateF is GoalState then
reconstruct the solution path from StartState to CurrentStateF, and terminates the loop
for each NeighboringStateF of CurrentStateF do
if NeighboringStateF is not in ClosedListF then
depth cost of NeighboringStateF is equal to the depth cost of CurrentStateF plus one
calculate HH value from NeighboringStateF to GoalState. Equation (3)
calculate evaluation function for NeighboringStateF. Equation (2)
add NeighboringStateF into ClosedListF
add NeighboringStateF into OpenListF
if NeighboringStateF is in ClosedListB then
reconstruct the solution path from the two searches: from StartState
to NeighboringStateF
and from NeighboringStateF to GoalState, and terminates the loop
increase IteratorF by 1
if IteratorF mod 15000 is equal to 0 after the first step of the cycle or IteratorF mod 75000
is equal to 0 then
->Expand in the backward direction, analogously
¶ Erklärung
Initialisierung:
- Der Algorithmus initialisiert zwei Listen für die Vorwärts- ( und ) und zwei für die Rückwärtssuche ( und ).
- Die Open Lists speichern Zustände, die betrachtet, aber noch nicht erweitert wurden.
- Die Closed Lists speichern Zustände, die bereits erweitert wurden.
- Es wird ein Iterator benutzt, um die Anzahl der Iterationen oder Zyklen zu verfolgen.
Start der Suche:
- Zu Beginn der Suche wird der Startzustand mit einer Bewertungsfunktion versehen, die HH-Heuristik und den Tiefenkosten basiert.
- Der Startzustand wird zur entsprechenden Open List und Closed List hinzugefügt.
Suchprozess:
- In jedem Schritt wählt der Algorithmus den Zustand mit dem niedrigsten Bewertungsfunktionswert aus der Open List, um ihn zu erweitern.
- Wenn dieser Zustand der Zielzustand ist, wird der Pfad rekonstruiert und der Prozess beendet.
- Wenn nicht, werden alle Nachbarzustände (NeighboringState) des aktuellen Zustands betrachtet.
- Nachbarzustände, die noch nicht in der Closed List sind, erhalten eine Bewertung und werden zur Open List hinzugefügt.
Bidirektionale Suche:
- Die Suche wechselt zwischen Vorwärts- und Rückwärtssuche, wobei die Anzahl der Zyklen durch den Iterator bestimmt wird.
- Wenn ein Zustand in der Closed List der entgegengesetzten Suche gefunden wird, bedeutet das, dass sich die beiden Suchen getroffen haben. Der Algorithmus rekonstruiert dann den kompletten Pfad.
Spezielle Bedingungen:
- Nachdem eine bestimmte Anzahl von Iterationen durchlaufen wurde (durch mod 15000 oder mod 75000 überprüft), wird die Suche in der rückwärtigen Richtung (von GoalState zu StartState) analog zur Vorwärtssuche durchgeführt. Dies ermöglicht die Suche in beiden Richtungen gleichzeitig und kann die Effizienz des Algorithmus verbessern.
¶ HH Heuristik
Die HH-Heuristik im Pseudocode bezieht sich auf eine "Hybridized Heuristic" [7:1], die für den Bidirektionalen A*-Algorithmus verwendet wird. Diese Heuristik kombiniert drei verschiedene Heuristikmethoden: Manhattan-Distanz (MD), Lineare Konflikte (LC) und Walking-Distanz (WD). Das Ziel dieser Hybridisierung ist es, die Effizienz des Algorithmus zu verbessern, indem die Anzahl der generierten Zustände reduziert wird. Jede der Heuristiken hat ihre eigenen Stärken, und durch ihre Kombination wird eine umfassendere und genauere Schätzung der verbleibenden Distanz zum Zielzustand erreicht. Diese Kombination ermöglicht es dem Algorithmus, entweder optimale oder nahezu optimale Lösungen effizienter zu finden.[7:2]
Die Manhattan-Distanz ist eine Heuristik, die häufig in Rätseln und Problemen der Wegfindung verwendet wird. Sie misst den Abstand zwischen zwei Punkten in einem Raster, wobei nur horizontale und vertikale Bewegungen erlaubt sind.[8]
Im Kontext des Fünfzehner-Puzzles wird die Manhattan-Distanz berechnet, indem für jede Kachel die Anzahl der Schritte gezählt wird, die benötigt werden, um sie von ihrer aktuellen Position in die Zielposition zu bewegen, ohne diagonale Bewegungen zu berücksichtigen. Für jede Kachel wird die Distanz in horizontaler und vertikaler Richtung einzeln berechnet und dann addiert. Die Summe dieser Distanzen über alle Kacheln gibt an, wie "weit entfernt" die aktuelle Konfiguration des Puzzles von der Zielkonfiguration ist.[7:3]
Der lineare Konflikt ist eine weitere Heuristik, die über die Manhattan-Distanz hinausgeht. Er tritt auf, wenn zwei Kacheln in derselben Reihe oder Spalte sind, um ihr Ziel zu erreichen, aber in der falschen Reihenfolge stehen und sich gegenseitig blockieren.
Zum Beispiel, wenn in einer Reihe die Kacheln 1 und 2 in der Zielkonfiguration nebeneinander stehen sollen, aber in der Reihenfolge 2-1 angeordnet sind, besteht ein linearer Konflikt. Um diesen Konflikt zu lösen, muss mindestens eine der Kacheln aus der Reihe bewegt werden, was zusätzliche Züge erfordert. Der lineare Konflikt addiert für jedes Paar von Kacheln, das in Konflikt steht, eine bestimmte Anzahl von Zügen zur Gesamtschätzung der Manhattan-Distanz hinzu, um eine realistischere Einschätzung der benötigten Züge zu geben.[7:4]
Während die Manhattan-Distanz die Bewegungen jeder Kachel unabhängig betrachtet, berücksichtigt die Walking Distance die Tatsache, dass die Bewegung einer Kachel die Bewegung einer anderen beeinflussen kann.
Die Grundidee ist, dass, wenn eine Kachel bewegt wird, um sie näher an ihre Zielposition zu bringen, dies möglicherweise eine andere Kachel von ihrer Zielposition wegbewegt. Die Walking Distance versucht, diese gegenseitigen Abhängigkeiten in die Berechnung der Distanz einzubeziehen. Es ist eine komplexere Heuristik, die schwieriger zu berechnen ist, aber in vielen Fällen genauere Schätzungen über die Anzahl der benötigten Züge liefert.[7:5]
¶ Resultate
Um die Wirksamkeit und Leistung des BA*-Algorithmus zu beurteilen, werden in diesem Abschnitt verschiedene Vergleiche angestellt. Zuerst vergleichen wir BA* mit HH in Bezug auf die Einhaltung der Anforderungen des ABC-Algorithmus (siehe Tabelle 1). Danach betrachten wir BA* im Vergleich zu UA* bezüglich der Richtungsorientierung, um zu demonstrieren, dass die bidirektionale Suche effektiver ist als die unidirektionale, besonders unter der Voraussetzung, dass sich die beiden Suchrichtungen nicht verfehlen (siehe Tabelle 2). Zum Schluss führen wir die BA*-Suche auf den 30 von 100 Korf-Instanzen durch und vergleichen sie mit der IDA*-Suche, ebenfalls im Kontext von HH[7:6] (siehe Tabelle 3).
Tabelle 1: Vergleich der BA*-Suche und der UA*-Suche für die 28 schwierigen Fünfzehn-Puzzle-Instanzen, die 80 Züge erfordern.
Tabelle 2: Vergleich der Ergebnisse zwischen BA*-Algorithmus und ABC-Algorithmus.
Tabelle 3: Vergleich des IDA*-Algorithmus mit MD und des LC- und BA*-Algorithmus mit HH für die 30 von 100 Korf-Instanzen. (in Anlehnung an Dler O., et al.[7:7])
¶ Referenzen
¶ Bildquellen
Abb. 1: Zufällige Anfangsstellung pdf
Abb. 2: Zielstellung pdf
¶ Tabellenquellen
Tabelle 1: Vergleich der BA*-Suche und der UA*-Suche für die 28 schwierigen Fünfzehn-Puzzle-Instanzen, die 80 Züge pdf
Tabelle 2: Vergleich der Ergebnisse zwischen BA*-Algorithmus und ABC-Algorithmus.pdf
Tabelle 3: (modifiziert) Vergleich des IDA*-Algorithmus mit MD und des LC- und BA*-Algorithmus mit HH für die 30 von 100 Korf-Instanzen.pdf
¶ Literaturverzeichnis
Aaron F. Archer (1999) A Modern Treatment of the 15 Puzzle, The American Mathematical Monthly, 106:9, 793-799, URL ↩︎
P. E. Hart, N. J. Nilsson and B. Raphael, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths," in IEEE Transactions on Systems Science and Cybernetics, vol. 4, no. 2, pp. 100-107, July 1968, URL ↩︎
Culberson, Joseph, and Jonathan Schaeffer. "Efficiently searching the 15-puzzle." (1994). URL ↩︎ ↩︎
Korf, R.E. Depth-first iterative-deepening: An optimal admissible tree search. Artif. Intell. 1985, 27, 97–109. URL ↩︎
Hasan, D. O., Aladdin, A. M., Hardi, S. T., Tarik, A. R., & Mirjalili, S. (2023). The fifteen Puzzle—A new approach through hybridizing three heuristics methods. Computers, 12(1), 11. URL ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎