Tiefensuche und backtracking
Tiefensuche und Breitensuche bezeichnen Strategien zur Festlegung einer Reihenfolge bei diesem Ausprobieren.
Bei der Tiefensuche wird immer ...
- zuerst eine Auswahl getroffen und die anderen Möglichkeiten werden in geeigneter Weise für später aufgehoben ( STACK s.u. ),
- die einfache Teilaufgabe gelöst,
- für die verbleibende Restaufgabe wieder eine Auswahl unter Sicherung der übrigen Möglichkeiten getroffen ...
- ... bis nur noch ein triviales Restproblem übrig ist.
- Kann dies erfolgreich bearbeitet werden, so ist die Aufgabe nun gelöst, sonst wird jetzt eine der zuletzt gespeicherten Möglichkeiten ausprobiert (unter Speicherung der nun noch übrigen Möglichkeiten). Sollte auch diese versagen, probiert man ebenso die übrigen.
- Wenn alle zuletzt gespeicherten Möglichkeiten versagt haben, wird mit den als vorletzte gespeicherten begonnen usw ..., bis eine Lösung gefunden wurde oder schlimmstenfalls die Aufgabe endgültig als unlösbar erkannt ist.
Zum Speichern der Möglichkeiten muss demnach eine LIFO - Struktur ( = last in first out ) , also eine stack - Struktur benutzt werden. Diese Struktur kann explizit vom Programm verwaltet werden, es gibt jedoch eine einfachere Methode:
Eine funktionale Programmiersprache wie SCHEME stellt eine solche Struktur für die Parameter rekursiver Funktionsanwendungen sowieso zur Verfügung, so dass hier eine Tiefensuche mit der backtracking - Technik leicht zu verwirklichen ist. Das gilt besonders dann, wenn die eigentliche Problemlösung akkumulierend aus der Lösung einfacher Teilprobleme erzeugt werden kann.
Labyrinthe eigenen sich gut für eine Einführung in die backtracking - Technik, weil wir alle nach einiger Überlegung eine Tiefensuche mit backtracking anwenden würden, wenn wir tatsächlich den Ausweg aus einem Labyrinth finden müßten !