Tiefensuche und backtracking


Tiefensuche und Breitensuche bezeichnen Strategien zur Festlegung einer Reihenfolge bei diesem Ausprobieren. Bei der Tiefensuche wird immer ...

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 !