Backtracking
aus Wikipedia, der freien Enzyklopädie
Der Begriff Rücksetzverfahren oder englisch Backtracking (engl. Rückverfolgung) bezeichnet eine Problemlösungsmethode innerhalb der Algorithmik.
Backtracking geht nach dem Versuch-und-Irrtum-Prinzip (trial and error) vor, d. h. es wird versucht, eine erreichte Teillösung schrittweise zu einer Gesamtlösung auszubauen. Wenn absehbar ist, dass eine Teillösung nicht zu einer endgültigen Lösung führen kann, wird der letzte Schritt bzw. die letzten Schritte zurückgenommen, und es werden stattdessen alternative Wege probiert. Auf diese Weise ist sichergestellt, dass alle in Frage kommenden Lösungswege ausprobiert werden können. Mit Backtracking-Algorithmen wird eine vorhandene Lösung entweder gefunden (unter Umständen nach sehr langer Laufzeit), oder es kann definitiv ausgesagt werden, dass keine Lösung existiert. Backtracking wird meistens am einfachsten rekursiv implementiert und ist ein prototypischer Anwendungsfall von Rekursion.
Inhaltsverzeichnis |
[Bearbeiten] Allgemeiner Algorithmus
Funktion FindeLoesung (Stufe, Vektor)
1. wiederhole, solange es noch neue Teil-Lösungsschritte gibt:
a) wähle einen neuen Teil-Lösungsschritt;
b) falls Wahl gültig ist:
I) erweitere Vektor um Wahl;
II) falls Vektor vollständig ist, return true; // Lösung gefunden!
sonst:
falls (FindeLoesung(Stufe+1, Vektor)) return true; // Lösung!
sonst mache Wahl rückgängig; // Sackgasse (Backtracking)!
2. Da es keinen neuen Teil-Lösungsschritt gibt: return false // Keine Lösung!
[Bearbeiten] Zeitkomplexität
Bei der Tiefensuche werden bei maximal Parser-Fehler (Das Zielverzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): z
möglichen Verzweigungen von jeder Teillösung aus und einem Lösungsbaum mit maximaler Tiefe von Parser-Fehler (Das Zielverzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): N im schlechtesten Fall Parser-Fehler (Das Zielverzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): 1+z+z^2+z^3+\ldots+z^N Knoten erweitert.
Die Tiefensuche und somit auch Backtracking haben im schlechtesten Fall mit Parser-Fehler (Das Zielverzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): O(z^N)
eine exponentielle Laufzeit. Bei großer Suchtiefe n und Verzweigungsgrad Parser-Fehler (Das Zielverzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): z>1 dauert die Suche somit oft sehr lange. Daher ist das Backtracking primär für Probleme mit einem kleinen Lösungsbaum geeignet.
Es gibt jedoch Methoden, mit welchen die Zeitkomplexität eines Backtracking-Algorithmus verringert werden kann. Diese sind u. a.:
- Heuristiken
- Akzeptanz von Näherungslösungen & Fehlertoleranz
- Durchschnittliche Eingabemenge
[Bearbeiten] Beispiele
Bekannte Probleme, die sich mit Backtracking lösen lassen, sind u. a.:
[Bearbeiten] Damenproblem
Gegeben ist ein Schachbrett mit n*n Feldern (je n Spalten und Reihen). Man positioniere nun n Damen so, dass sie sich nicht gegenseitig schlagen können. Das Damenproblem gehört zu der Klasse der Constraint-Satisfaction-Probleme.
[Bearbeiten] Springerproblem
Gegeben ist ein „Schachbrett“ mit Parser-Fehler (Das Zielverzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): m\times n
Feldern. Ein Springer kann von einer bestimmten Position aus Parser-Fehler (Das Zielverzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): N=8 verschiedene Sprünge ausführen, falls diese nicht über den Rand des Brettes hinausführen. Gesucht ist ein Weg, bei dem alle Felder genau einmal besucht werden (Springerweg). Mit Hilfe von Backtracking können alle möglichen Wege systematisch durchprobiert werden. Ein Zug ist dabei gültig, wenn das neue Feld innerhalb des Spielfeldes liegt und noch unbesucht ist. Es gibt jedoch weitaus effizientere Verfahren für die Lösung dieses Problems.
[Bearbeiten] Rucksackproblem
Gegeben ist ein Rucksack mit der Tragfähigkeit Parser-Fehler (Das Zielverzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): B . Weiterhin sind Parser-Fehler (Das Zielverzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): N
Gegenstände mit Werten und Gewichten gegeben. Nun sollen Gegenstände so ausgewählt werden, die in der Summe einen maximalen Wert ergeben, aber deren Gesamtgewicht die Tragfähigkeit des Rucksacks nicht überschreitet.
[Bearbeiten] Färbeproblem
Gegeben ist eine Landkarte mit Parser-Fehler (Das Zielverzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): B
Ländern, welche mit Parser-Fehler (Das Zielverzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): N verschiedenen Farben eingefärbt werden sollen. Gesucht ist eine Farbkombination, bei welcher alle Länder, die eine gemeinsame Grenze besitzen, unterschiedlich eingefärbt sind.
[Bearbeiten] Solitär-Brettspiel
Zu Beginn stehen 32 Steine (Stifte oder Kugeln) auf einem Brett; davon werden in 31 Zügen je einer entfernt, indem man ihn mit einem anderen Stein überspringt.
[Bearbeiten] Sudoku
Die Zahlen von 1 bis 9 sollen nach gewissen Regeln in ein 9*9-Feld (unterteilt in neun 3*3-Felder) eingetragen werden.
[Bearbeiten] Wegsuche von A nach B in einem Graphen
Backtracking wird auch eingesetzt für die Wegsuche von A nach B in einem Graphen, z. B. für die Suche nach Verbindungen in einem Fahrplan oder zum Bestimmen einer Route in einem Routenplaner oder eines Weges durch ein Labyrinth.
[Bearbeiten] PROLOG
Die Programmiersprache Prolog benutzt Backtracking zur Antwort-Generierung. Dabei probiert der Interpreter alle Beweismöglichkeiten der Reihe nach durch. Entscheidungspunkte werden dabei als Choice Point bezeichnet. Der sogenannte Cut-Operator ! kann benutzt werden, um Choice-Points zu verwerfen.
[Bearbeiten] Literatur
- Robert Sedgewick: Algorithmen, Pearson Studium, 2. Aufl. 2002, ISBN 3-8273-7032-9
- Niklaus Wirth: Algorithmen und Datenstrukturen Stuttgart: Teubner, 3. überarb. Aufl. 1983, ISBN 3-519-02250-8
