Ein Baumsuchmechanismus, der Entscheidungsvariablen rekursiv Werte zuweist, Konsequenzen propagiert und Zuweisungen zurücknimmt (Backtracking), wenn ein Widerspruch oder eine Sackgasse erreicht wird, um systematisch alternative Belegungen zu erkunden.

Prinzip

Erkunde den Suchraum depth-first, treffe inkrementelle Entscheidungen, erkenne unlösbare Teilzweige frühzeitig und mache jüngste Entscheidungen rückgängig, um Alternativen zu versuchen und so einen kombinatorischen Raum zu durchqueren, ohne alle Belegungen gleichzeitig aufzulisten.

Demonstration

Beim Lösen eines CSP mit Variablen X, Y, Z: Setze X = a, propagriere Einschränkungen, um Ys Domain zu reduzieren, setze dann Y = b; wenn später eine Einschränkung mit Z widersprüchlich wird, backtracke, um Y oder X zu ändern und weitere Kombinationen zu prüfen.

Fehlanwendung

Naives Backtracking ohne Propagation oder Heuristiken (z. B. feste Variablenreihenfolge unabhängig von Restdomänen) führt zu überflüssigen Neuberechnungen und zur Erforschung irrelevanter Zweige.

Konsequenz

Backtracking liefert vollständige Entscheidungsverfahren für endliche CSPs und SAT und ermöglicht korrekte Lösungen in Kombination mit Beschneidungsstrategien; die Laufzeit hängt stark von Verzweigungsreihenfolge und Beschneidungswirkung ab.

Umkehrung

Das Gegenteil ist blinde Breitensuche oder ungeordnete Aufzählung aller Belegungen ohne Zurücksetzen; dies behält Vollständigkeit, opfert jedoch die gezielte Effizienz des Zurück- und Wiederversuchs.

Abgrenzung

Gilt für diskrete, endliche Entscheidungsräume, in denen Zuweisungen rückgängig gemacht werden können; schließt kontinuierliche Suche ohne Diskretisierung und Verfahren aus, die kein systematisches Rückgängigmachen erlauben (z. B. reine lokale Suche).

Semantische Spannung

Spannung zu lokalen Suchheuristiken: Lokalsuche verändert eine vollständige Belegung iterativ und erreicht oft schnell bessere durchschnittliche Laufzeiten, verliert dafür aber Backtrackings Vollständigkeit.

Synthese

Backtracking-Suche besteht darin, sich auf partielle Lösungen festzulegen, Deduktion zur Beschneidung unmöglicher Erweiterungen zu nutzen und diese Festlegungen rückgängig zu machen, um das kombinatorische Gelände methodisch zu durchqueren, bis Lösungen gefunden oder alle Optionen erschöpft sind.