Backtracking
Das Backtracking bezeichnet einen englischen Begriff als "Rückverfolgung" für eine Problemlösungsmethode innerhalb der Programmierung.
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.
Table of contents |
2 Zeitkomplexität 3 Beispiele 4 Bedeutung |
Bei der Tiefensuche werden bei maximal möglichen Verzweigungen von jeder Teillösung aus und einem Lösungsbaum mit maximaler Tiefe von im schlechtesten Fall Knoten erweitert.
Die Tiefensuche und somit auch Backtracking haben im schlechtesten Fall mit eine exponentielle Laufzeit. Bei großer Suchtiefe n und Verzweigungsgrad dauert die Suche somit oft sehr lange. Daher ist das Backtracking primär für Probleme mit einem kleinem Lösungsbaum geeignet.
Es gibt jedoch Methoden, mit welchen die Zeitkomplexität eines Backtrackingalgorithmus verringert werden kann. Diese sind u.a.:
Das Backtracking-Verfahren hat besonders auf die Programmiersprache PROLOG großen Einfluss.
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
Beispiele
Bekannte Probleme, die sich mit Backtracking lösen lassen, sind u.a.:Springerproblem
Gegeben ist ein Schachbrett mit Feldern. Ein Springer kann 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 . Weiterhin sind 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 Länder, welche mit 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 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