Backtracking

Grundidee und Bedeutung

Backtracking, auf Deutsch Rücksetzverfahren oder Rückverfolgung, ist eine Problemlösungsmethode der Algorithmik. Es arbeitet nach dem Prinzip der Tiefensuche und nach Versuch und Irrtum („trial and error“): Eine Teillösung wird schrittweise erweitert, bis entweder eine vollständige Lösung entsteht oder erkennbar wird, dass der eingeschlagene Weg nicht zum Ziel führen kann.

Führt eine Wahl in eine Sackgasse, nimmt der Algorithmus den letzten Schritt oder mehrere Schritte zurück und versucht eine Alternative. Dadurch lassen sich systematisch alle infrage kommenden Lösungswege untersuchen. Dieses Vorgehen entspricht dem Prinzip des Ariadnefadens. Der Algorithmus findet eine vorhandene Lösung – möglicherweise erst nach sehr langer Laufzeit – oder stellt eindeutig fest, dass keine Lösung existiert.

Backtracking wird meist rekursiv umgesetzt. Rekursion bedeutet hier, dass die Suchfunktion sich selbst für die jeweils nächste Stufe des Lösungswegs aufruft.

Ablauf des Verfahrens

Der allgemeine Ablauf verwendet einen Vektor, der die bisher gewählten Teilschritte enthält:

• Solange noch nicht ausprobierte Teillösungsschritte vorhanden sind, wird ein neuer Schritt ausgewählt.
• Ist diese Wahl gültig, wird sie dem Vektor hinzugefügt.
• Ist der Vektor damit vollständig, wurde eine Lösung gefunden und die Funktion gibt „true“ zurück.
• Ist er noch nicht vollständig, wird die Suche rekursiv auf der nächsten Stufe fortgesetzt.
• Führt die Fortsetzung zu keiner Lösung, wird die letzte Wahl rückgängig gemacht. Anschließend wird eine andere Möglichkeit geprüft.
• Sind keine weiteren Teillösungsschritte vorhanden, gibt die Funktion „false“ zurück. Auf diesem Weg existiert dann keine Lösung.

Der Algorithmus baut somit einen Lösungsbaum auf: Jeder Knoten steht für eine Teillösung, jede Verzweigung für eine mögliche nächste Wahl und jede Sackgasse für einen Weg, der zurückgenommen werden muss.

Laufzeit und Grenzen

Bei maximal z möglichen Verzweigungen von jeder Teillösung aus und einer maximalen Tiefe N des Lösungsbaums werden im schlechtesten Fall 1 + z + z² + z³ + … + zᴺ Knoten erweitert. Für einen Verzweigungsgrad z > 1 ergibt sich die exponentielle Zeitkomplexität O(zᴺ).

Mit wachsender Suchtiefe dauert die Lösungssuche daher stark länger. Backtracking eignet sich vor allem für Probleme mit einem kleinen Lösungsbaum. Die Zeitkomplexität kann unter anderem durch Heuristiken, durch die Akzeptanz von Näherungslösungen und Fehlertoleranz sowie unter Berücksichtigung der durchschnittlichen Eingabemenge verringert werden.

Typische Anwendungen

Viele mit Backtracking lösbare Aufgaben sind Constraint-Satisfaction-Probleme, also Probleme, bei denen eine Belegung bestimmte Bedingungen erfüllen muss. Viele der genannten Probleme sind NP-vollständig.

Beim Damenproblem sollen auf einem Schachbrett mit n × n Feldern N Damen so angeordnet werden, dass keine Dame eine andere schlagen kann. Der Algorithmus setzt schrittweise Damen ein und nimmt eine Platzierung zurück, sobald sie keine gültige Gesamtlösung mehr zulässt.

Beim Springerproblem besitzt ein Schachbrett m × n Felder. Ein Springer kann von einer Position aus N = 8 verschiedene Sprünge ausführen, sofern sie nicht über den Brettrand führen. Gesucht wird ein Springerweg, der jedes Feld genau einmal besucht. Ein Zug gilt als gültig, wenn das Zielfeld innerhalb des Bretts liegt und noch nicht besucht wurde. Backtracking kann alle Wege systematisch prüfen, allerdings gibt es für dieses Problem deutlich effizientere Verfahren.

Beim Rucksackproblem sind ein Rucksack mit Tragfähigkeit B sowie N Gegenstände mit Werten und Gewichten gegeben. Gesucht ist eine Auswahl mit maximalem Gesamtwert, deren Gesamtgewicht B nicht überschreitet. Beim Färbeproblem sollen B Länder mit N Farben so eingefärbt werden, dass Länder mit gemeinsamer Grenze unterschiedliche Farben erhalten.

Weitere Anwendungen sind das Solitär-Brettspiel, bei dem von anfangs 32 Steinen in 31 Zügen jeweils einer durch Überspringen entfernt wird, sowie Sudoku und Str8ts. Bei beiden Rätseltypen werden die Zahlen 1 bis 9 nach bestimmten Regeln in ein 9 × 9-Feld eingetragen; beim Sudoku ist dieses zusätzlich in neun 3 × 3-Felder unterteilt. Backtracking kann außerdem Wege von A nach B in einem Graphen suchen, etwa Verbindungen in einem Fahrplan, Routen in einem Routenplaner oder Wege durch ein Labyrinth.

Backtracking in Prolog

Die Programmiersprache Prolog verwendet Backtracking zur Erzeugung von Antworten. Der Interpreter probiert dazu die möglichen Beweise der Reihe nach aus. Stellen, an denen alternative Fortsetzungen möglich sind, heißen Choice Points, also Entscheidungspunkte. Der Cut-Operator ! kann verwendet werden, um solche Choice Points zu verwerfen und damit bestimmte alternative Suchwege auszuschließen.