Die iterative Tiefensuche findet Anwendungen in der Operations Research und in der Künstlichen Intelligenz. Dieses Verfahren kann etwa für zweidimensionale Pack-Probleme (Cutting-Stock Problem) [14] oder im Bereich des VLSI-Chip-Entwurfs (Floorplan-Area-Optimization) [15] angewendet werden.
Typische Anwendungen der iterativen Tiefensuche zeichnen sich durch die folgenden Eigenschaften aus:
Figure 1: Das 44- bzw. 15-Puzzle in einer beliebigen Ausgangsstellung (links)
und in der Zielstellung (rechts)
Eine einfache Anwendung mit den oben genannten Eigenschaften ist das
[8].
Das n
n -Puzzle besteht aus einem festen Rahmen der Größe n
n, in dem
sich n
-1 durchnumerierte Spielsteine befinden,
ein Feld ist leer.
In einem Zug kann nun ein zum leeren Feld benachbarter Spielstein auf dieses Feld
verschoben werden.
Die Lösung des n
n-Puzzles besteht darin, eine beliebige Ausgangsstellung mit
einer minimalen Anzahl von Zügen in eine definierte Zielstellung zu überführen.
Das n
n-Puzzle ist ein
-vollständiges Problem [9].
Der Algorithmus IDA* ist das bislang einzige Verfahren, welches kleinere Instanzen, wie
etwa das 44-Puzzle mit annehmbaren Ressourcen lösen kann.
Dabei werden bei 100 zufälligen Instanzen im Durchschnitt
Knoten
betrachtet [4].
Als Heuristik wird die Manhattan-Distanz verwendet, welche sich aus der
Summe der kürzesten Distanzen aller Steine von ihren Zielpositionen
berechnet.
Während der Fehler dieser Heuristik im Falle des 4
4-Puzzles noch relativ
gering ausfällt, hat sich diese Heuristik zur Lösung des 4
5-Puzzles als
nicht sehr geeignet erwiesen, da die sich ergebenden Suchbäume trotz der Verwendung
einer Heuristik noch sehr großsind [13].
So wurden bei der Lösung einer zufälligen Instanz dieses Problems mehr als
1.5 Billionen Knoten expandiert.