Chronologisches Backtracking nimmt u.U. Werte von
Variablen zurück, die nicht am aufgetretenen Konflikt beteiligt sind.
Wenn z.B. für eine Variable keine konsistente Belegung
gefunden werden kann, geht chronologisches Backtracking
zurück zu
und versucht für diese Variable eine alternative
Wertebelegungen zu finden. Existiert allerdings kein Constraint
zwischen
und
, wird diese Maßnahme nicht zum
gewünschten Erfolg führen: Der Algorithmus geht alle alternativen
Werte für
durch und trotzdem liegt bei
jedes mal ein
illegaler Zustand vor. Erneutes Backtracking und Aufspannen des
nachfolgenden Suchbaums wird solange notwendig, bis für diejenige
Variable eine alternative Wertebelegung gewählt wird, die tatsächlich
für die Inkonsistenz verantwortlich ist.
Backjumping (BJ), eingeführt von John Gaschnig, versucht dies zu verhindern, indem in einer Konfliktsituation nicht, wie beim chronologischen Backtracking, nur jeweils ein Schritt zurückgegangen wird. Stattdessen wird versucht zu ermitteln, welche Variablenbelegung ,,schuld`` an dem aufgetretenen Konflikt ist. Bis zu dieser Variable wird ,,zurückgesprungen`` (engl. to jump back) und deren Wert direkt geändert (vgl. Gaschnig, 1979)5.42. Damit werden u.U. sehr viele, in diesem Fall sinnlose, Backtracking-Schritte vermieden, denn im Normalfall würde beim chronologischen Backtracking zuerst der Wert der letzten Variable verändert werden, dann der vorletzten etc. Der Algorithmus von Gaschnig führt ein Backjumping allerdings ausschließlich in Konfliktsituationen in Blättern des Suchbaums durch. Anderenfalls, d.h. wenn nach dem ersten Rücksprung aufgrund fehlender, konsistenter Werte wiederholt Backtracking in internen Zuständen notwendig ist, wird ausschließlich chronologisches Backtracking angewandt (vgl. Dechter und Frost, 2002, S. 158 ff.). Gaschnigs Algorithmus führt Rücksprünge durch, indem mit jeder Variable zusätzlich zur Laufzeit ein Zeiger verwaltet wird, der auf die jeweils letzte Variable verweist, die mit einem Wert der aktuellen Variable inkonsistent war. Sollte Backtracking notwendig werden, kann auf diesen Zeiger zurückgegriffen werden und ein Rücksprung zur den Konflikt auslösenden Variable erfolgen. Die Verwaltung dieser zusätzlichen Zeiger benötigt allerdings bei jedem Konsistenztest etwas vermehrten Berechnungsaufwand (vgl. Dechter, 1992, S. 283).
Eine effiziente Variante ist das graphenbasierte
Backjumping (engl. graph-based backjumping, GBJ) von
Rina Dechter. Beim
graphenbasierten Backjumping wird die Ermittlung der den
Backtracking-Schritt verursachenden Variablen dahingehend
vereinfacht, dass bei einem Konflikt durch Analyse des
Constraint-Graphen zu der Variable zurückgesprungen wird, die als
letztes die aktuelle Variable durch ein Constraint beschränkt hat
(vgl. Dechter, 1990a, S. 276 ff.).5.43 Im Gegensatz zu anderen Varianten benötigt GBJ
daher nur relativ wenig zusätzliche Kapazität zur Ermittlung des
Backjumping-Punktes, stellt allerdings nicht sicher, dass wirklich
die konfliktauslösende Variable sofort gefunden wird.
GBJ nutzt das Wissen über Constraints dazu, bei einem
Backtracking-Schritt alle Variablen zu überspringen, die definitiv
nicht am aktuellen Konflikt beteiligt sind. Evtl. ist weiteres
Backjumping notwendig, um die tatsächlich ,,schuldige`` Variable
ausfindig zu machen. Wenn von einer Variable aus ein Rücksprung
zur letzten
beschränkenden Variable
erfolgt ist,
aber keine Lösung des Konflikts ist, erfolgt wiederum ein
Backjumping zur letzten mit einem Wert belegten Variable
,
die entweder
oder
beschränkt usw.
In Abbildung 5.16 ist beispielhaft (graphenbasiertes) Backjumping anhand des Suchbaums für das Constraint-Netz aus Abbildung 5.7 dargestellt:
Eine Zusammenführung der Vorteile von Gaschnigs Backjumping und
GBJ stellt konfliktbasiertes
Backjumping (engl. conflict-directed backjumping, CBJ)
von Patrick Prosser dar
(vgl. Prosser, 1993b, S. 277 ff.). Der Algorithmus von
Prosser baut auf dem Schema von graphenbasiertem Backjumping auf und
ist dadurch in der Lage, mehrere Backjumping-Schritte hintereinander
auszuführen. Allerdings wird bei Konflikten nicht auf Informationen
zurückgegriffen, die sich aus dem Constraint-Graphen ableiten lassen,
sondern es werden, wie bei Gaschnigs Backjumping, zusätzliche
Informationen bereits während der Suche in Form von sog. conflict sets für jede Variable
generiert. Aufgrund dieser conflict
sets kann exakt jeweils die Variable mit der konfliktauslösenden
Belegung ausfindig gemacht werden. Immer dann, wenn eine zu testende
Belegung der aktuellen Variable in Konflikt mit einer
bereits belegten Variable
steht, wird
dem conflict set von
hinzugefügt. Gibt es keine
weiteren alternativen Werte für die Belegung von
, erfolgt
ein Backjumping zu der Variable
im conflict set von
, die sich am tiefsten im
Suchbaum befindet und damit zuletzt vor
mit einem Wert
belegt wurde.5.44
Die genannten Backjumping-Varianten werden auch unter dem allgemeinen Begriff abhängigkeitsgesteuertes Backtracking zusammengefasst (engl. dependency-directed backtracking, DDBT) vgl. Dechter und Frost, 2002, S. 184; Tsang, 1993, S. 137. Der Einsatz dieser Strategie ermöglicht es, konfliktauslösende Entscheidungen im Suchbaum zu identifizieren und diese zu korrigieren. Abhängigkeitsgesteuertes Backtracking kann auf vielerlei Problemstellungen angewendet werden.5.45 Die Frage nach der Effizienz der Strategie wird beeinflusst von der Problemstellung, die entscheidend dafür ist, ob sich der entstehende Overhead lohnt. Die Analyse von Konflikten anhand von Constraints (GBJ) bzw. conflict sets (CBJ) ermöglicht i.A. einen effizienten Einsatz von abhängigkeitsgesteuerten Strategien in CSPs.