Grenzen und Einschränkungen der Tiefensuche und damit der backtracking - Technik
- Tiefensuche ist unbrauchbar, wenn unendliche Rekursion nicht sicher ausgeschlossen werden kann. Ein nicht endlicher Suchraum macht eine einfache Tiefensuche prinzipiell unmöglich. Sie versagt in der Regel auch dann, wenn das Ziel real endlich erreichbar wäre.
- Tiefensuche eignet sich nicht oder nur sehr schlecht für die Aufgabe, von mehreren Lösungen eine oder mehrere optimale zu finden, z.B. den kürzesten Weg durch ein Labyrinth. Bei dieser naheliegenden Fragestellung ist Breitensuche prinzipiell überlegen. Bei der Tiefensuche müssten erst alle Wege untersucht werden und dabei die aktuell beste gespeichert werden. Sind mehrere Wege eventuell erfolgreich z.B. weil eine Bewertung erst am Schluss möglich ist, müssen diese alle gespeichert werden, bevor sie einer Bewertung unterzogen werden können.
- Hingegen ist Tiefensuche durchaus anwendbar, wenn sowieso alle Lösungen gefunden werden müssen, etwa bei der Suche des längsten Weges.
- Backtracking ist oft dadurch ineffizient, dass im Verlauf der Suche bereits als unlösbar erkannte Teilprobleme wieder "vergessen" werden, so dass Lösungsversuche unnötig wiederholt werden:
Ohne Krampf können Informationen nur "von oben nach unten" weitergegeben werden, "von unten nach oben" eigentlich nur die gefundene Lösung und die Tatsache, dass sie gefunden wurde oder im Falle des Scheiterns eben nicht.
Unter spezialisierenden Annahmen über das Suchproblem kann man versuchen, die Effizienz einer Tiefensuche zu steigern:
- Bei Labyrinthen ist etwa die Feststellung, dass von einem Knoten aus kein Erfolg möglich ist, unabhängig davon zu treffen, wie man zu diesem Knoten gelangt ist, so dass ein einmal entdeckter aussichtsloser Knoten von der weiteren Suche ausgeschlossen werden kann. (CLOSED - Liste)
- Ist vorab bekannt, in welcher Rekursionstiefe eine Lösung gefunden werden wird, dann ist vermutlich Tiefensuche mit begrenzter Suchtiefe die optimale Suchstrategie: Immer beim Erreichen der maximalen Suchtiefe wird ein Scheitern und damit ein backtracking ausgelöst. (Tiefensuche mit begrenztem Suchhorizont)
- Mit weiteren Fragen der Steigerung der Effizienz einer Suche, die auf dem Grundmuster der Tiefensuche beruht (z.B. Heuristik zur Festlegung der Reihenfolge, in der Möglichkeiten versucht werden) werden wir uns noch beschäftigen.