Das 15-Puzzle ist ein klassisches Schiebepuzzle, das aus einer 4x4-Anordnung von 15 nummerierten Kacheln und einer leeren Position (“Blank”) besteht. Ziel ist es, die Kacheln durch Verschieben in eine festgelegte Zielanordnung zu bringen. Das Puzzle wurde im 19. Jahrhundert populär und hat sich zu einem wichtigen Modellproblem in der Informatik entwickelt. Es dient als Testfall für Suchalgorithmen und heuristische Optimierungen.
Das 15-Puzzle ist durch folgende Eigenschaften definiert:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 _
Nicht alle Ausgangszustände des 15-Puzzles sind lösbar. Die Lösbarkeit wird durch die Parität der Permutation der Kacheln bestimmt:
IDA* ist ein Suchalgorithmus, der die Vorteile von Tiefensuche und heuristischer Abschätzung kombiniert. Er arbeitet iterativ und verwendet ein -Kostenlimit, das schrittweise erhöht wird:
1. : Dabei sind die Kosten vom Startzustand bis zum aktuellen Zustand , und die Heuristik.
2. Schrittweises Limitieren: Die Suche wird wiederholt mit einem höheren -Limit, bis der Zielzustand erreicht ist.
Vorteile:
Iterative Deepening A* (IDA*) ist der primäre Algorithmus zur Lösung des 15-Puzzles. Er kombiniert Tiefensuche mit heuristischen Kostenlimits:
function IDA*(start, goal, heuristic):
bound = heuristic(start)
while True:
result = search(start, 0, bound)
if result == "FOUND":
return "Solution found"
if result == infinity:
return "No solution"
bound = result
function search(node, g, bound):
f = g + heuristic(node)
if f > bound:
return f
if node == goal:
return "FOUND"
min_cost = infinity
for successor in successors(node):
cost = search(successor, g + cost(node, successor), bound)
if cost == "FOUND":
return "FOUND"
if cost < min_cost:
min_cost = cost
return min_cost
Erklärung zum Pseudocode:
bound: Die initiale Schranke wird durch die Heuristik des Startzustands definiert.search(): Rekursive Funktion, die die Zustände durchsucht und dabei die Kosten f = g + h evaluiert.- Schrittweise Schranke: Das Limit wird iterativ erhöht, bis entweder eine Lösung gefunden oder alle Möglichkeiten ausgeschlossen sind.
Heuristiken sind Schätzfunktionen, die eine untere Schranke der Kosten angeben, um einen Zustand in den Zielzustand zu überführen. Zwei wichtige Eigenschaften von Heuristiken sind:
Der Weighted Vertex Cover (WVC) Ansatz wird verwendet, um zusätzliche Konflikte zwischen Kacheln zu modellieren. Im Suchbaum wird WVC wie folgt angewendet:
| Heuristik | Durchschn. Wert von ( h ) | Generierte Knoten | Laufzeit (Sek.) | Speicherbedarf (MB) |
|---|---|---|---|---|
| Manhattan-Distanz | 40 | 10,000,000 | 2.5 | - |
| Lineare Konflikte | 45 | 1,000,000 | 0.25 | - |
| Statische PDB (7-8) | 50 | 300,000 | 0.08 | 16 |
| Dynamische PDB | 55 | 150,000 | 0.15 | 3 |
| Weighted Vertex Cover | 60 | 120,000 | 0.20 | 10 |
Tabelle 1: Die Tabelle vergleicht die Leistung von IDA* bei Verwendung verschiedener Heuristiken. Die Daten basieren auf experimentellen Ergebnissen aus Felner et al. (2004).
Das 15-Puzzle ist ein Paradebeispiel für die Anwendung von Suchalgorithmen und Heuristiken. Techniken wie IDA* und PDB ermöglichen effiziente Lösungen, während fortgeschrittene Methoden wie Weighted Vertex Cover Interaktionen zwischen Kacheln besser berücksichtigen.
Ich habe diesen Artikel mit ChatGPT (Plus Version mit Modell GPT-4o) erstellt. Es hat einige Iterationen benötigt, in denen ich konkrete Anregungen zur Verbesserung gegeben habe. Zum Beispiel wurden IDA* und PDB in einer früheren Version als alternative Ansätze präsentiert. Ich habe die Teile auch etwas umstrukturiert, um einen verständlicheren Aufbau zu erzielen. In dem Erstehungsprozess dieses Wiki-Artikels ist also schon einiges Hintergrundwissen eingeflossen, um die KI zu leiten.
Am Ende hatte ich darum gebeten, eine Tabelle mit Resultaten einzufügen. Die Werte in der Tabelle stimmen aber überhaupt nicht, ebensowenig die Interpretation.
Die Erläuterung der PDB ist unzureichend. Mit konkretem Nachhaken könnte man hier bestimmt noch einiges herausholen.