Das Backtracking oder Backspace ( auf Englisch auch Backtracking genannt ) ist eine Familie von Algorithmen zur Lösung algorithmischer Probleme , einschließlich der Erfüllung von Einschränkungen (Optimierung oder Entscheidung). Diese Algorithmen ermöglichen es, alle möglichen Zuordnungen des Problems systematisch zu testen. Sie bestehen darin, eine Variable des Problems auszuwählen und für jede mögliche Zuordnung dieser Variablen rekursiv zu testen, ob aus dieser Teilzuordnung eine gültige Lösung konstruiert werden kann. Wenn keine Lösung gefunden wird, gibt die Methode die zuvor vorgenommenen Zuweisungen auf und kehrt zu ihnen zurück (daher der Name der Rückgabe bei Ablaufverfolgung).
Mit anderen Worten, der Traceback ist eine eingehende Reise in den Entscheidungsbaum des Problems.
Zufriedenheitsprobleme sind Probleme mit einer vollständigen Lösung, bei denen keine natürliche Reihenfolge der Elemente existiert. Diese Probleme bestehen aus einer Reihe von Variablen, deren Werte problemspezifischen Einschränkungen unterliegen. Die Hauptidee ist, jede Möglichkeit (Kombination) auszuprobieren, bis Sie die richtige gefunden haben. Dazu untersuchen wir die unmittelbaren Möglichkeiten, und wenn keine Blockade auftritt, fahren wir mit den folgenden Möglichkeiten fort; Wenn eine Blockade auftritt, dh wenn keine Möglichkeit besteht, kehren wir zum letzten untersuchten Fall zurück, in dem eine andere Möglichkeit bestand, und fahren mit diesem Fall fort. Die deklarativen Programmiersprachen wie Prolog ermöglichen es, diese Einschränkungen direkt auszudrücken und diese Suche automatisch durchzuführen.
In einem Spiel, das wir programmieren, können wir eine bestimmte Bewegung und ihre Folgen berücksichtigen. Eine der Fortsetzungen ist möglicherweise nicht glücklich. Wir kehren dann zu einem bestimmten Punkt zurück und betrachten eine andere Bewegung.
Der Stack ist eine grundlegende Datenstruktur für die Rückgabe bei Ablaufverfolgung. Sie ermöglicht es, die hergestellten Verbindungen zu speichern (zu stapeln) und während einer Rückgabe zu aktualisieren (zu entstapeln). Die natürlichste Implementierung des Algorithmus verwendet rekursive Aufrufe und damit den Ausführungsstapel .