Backtracking arbeitet nach dem Prinzip der Tiefensuche

Das Backtracking bezeichnet einen englischen Begriff als "Rückverfolgung" für eine Problemlösungsmethode innerhalb der Algorithmik.

Backtracking ist eine Programmierstrategie, die nach dem Prinzip "Trial and Error" (Versuch und Irrtum) vorgeht. Unterschiedliche Algorithmen (je nach Problemstellung) wählen einen von mehreren Lösungswegen aus und verfolgen ihn über seine Entscheidungsknoten so lange, bis die Lösung gefunden worden ist, oder der Weg sich als definitiv falsch herausgestellt hat.

Ist dies der Fall, kehrt man zum letzten Entscheidungsknoten zurück und wählt einen anderen Weg. Auf diese Weise werden von Entscheidungsknoten zu Entscheidungsknoten so viele Wege ausprobiert, bis einer ans Ziel führt.

Allgemeiner Algorithmus

 Funktion FindeLoesung (Stufe, Vektor)
 1. wiederhole solange es noch neue Teil-Lösungsschritte gibt:
     a) wähle einen neuen Teil-Lösungsschritt schritt;
     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. Gibt es keinen neuen Teil-Lösungsschritt: return false // Keine Lösung!

Zeitkomplexität

Bei der Tiefensuche werden bei maximal z möglichen Verzweigungen von jeder Teillösung aus und einem Lösungsbaum mit maximaler Tiefe von N im schlechtesten Fall 1 + z + z² + z³ + ... + z^N Knoten erweitert.

Die Tiefensuche und somit auch Backtracking haben im schlechtesten Fall mit O(z^N) eine exponentielle Laufzeit. Bei großer Suchtiefe n und Verzweigungsgrad 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 Backtrackingalgorithmus verringert werden kann. Diese sind u.a.:

• Heuristiken
• Akzeptanz von Näherungslösungen & Fehlertoleranz
• Durchschnittliche Eingabemenge

Beispiele

Bekannte Probleme, die sich mit Backtracking lösen lassen, sind u.a.:

acht-Damenproblem

(verallgemeinert: n-Damenproblem)

Gegeben ist ein Schachbrett mit 64 Feldern (= acht Spalten bzw. Reihen). Man positioniere nun acht Damen so, dass sie sich nicht gegenseitig schlagen können.

Springerproblem

Gegeben ist ein Schachbrett mit B Feldern. Ein Springer kann N = 8 verschiedene Sprünge ausführen. Gesucht ist ein Weg, bei welchem alle Felder genau einmal besucht werden (Springerweg). Mit Hilfe von Backtracking können alle möglichen Wege systematisch "abgesprungen" werden. Ein Zug ist dabei gültig, wenn das neue Feld innerhalb des Spielfeldes liegt und unbesucht ist.

Rucksackproblem

Gegeben ist ein Rucksack mit der Tragfähigkeit B. Weiterhin sind N Gegenstände mit Werten und Gewichten gegeben. Nun sollen Gegenstände ausgewählt werden, die in der Summe einen maximalen Wert ergeben, aber deren Gesamtgewicht die Tragfähigkeit des Rucksacks nicht überschreitet.

Färbeproblem

Gegeben sind B Länder, welche mit 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.

Problem des Handlungsreisenden

Gegeben sind N Orte und die Entfernungen zwischen ihnen. Gesucht ist nun eine Rundreise, die alle Orte besucht, zum Ausgangspunkt zurückkehrt und dabei die eine minimale Gesamtlänge hat.

Bedeutung

Das Backtracking-Verfahren hat besonders auf die Programmiersprache PROLOG großen Einfluss. Backtracking ist in PROLOG schon 'eingebaut'.