next up previous contents index
Nächste Seite: 5.2.4.4 Backchecking und Backmarking Aufwärts: 5.2.4 Suchverfahren Vorherige Seite: 5.2.4.2 Backtracking   Inhalt   Index

5.2.4.3 Backjumping

Chronologisches Backtracking nimmt u.U. Werte von Variablen zurück, die nicht am aufgetretenen Konflikt beteiligt sind. Wenn z.B. für eine Variable $v_i$ keine konsistente Belegung gefunden werden kann, geht chronologisches Backtracking zurück zu $v_{i-1}$ und versucht für diese Variable eine alternative Wertebelegungen zu finden. Existiert allerdings kein Constraint zwischen $v_i$ und $v_{i-1}$, wird diese Maßnahme nicht zum gewünschten Erfolg führen: Der Algorithmus geht alle alternativen Werte für $v_{i-1}$ durch und trotzdem liegt bei $v_i$ 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 $v_i$ aus ein Rücksprung zur letzten $v_i$ beschränkenden Variable $v_{i-k}$ erfolgt ist, $v_{i-k}$ aber keine Lösung des Konflikts ist, erfolgt wiederum ein Backjumping zur letzten mit einem Wert belegten Variable $v_{i-m}$, die entweder $v_i$ oder $v_{i-k}$ beschränkt usw.

In Abbildung 5.16 ist beispielhaft (graphenbasiertes) Backjumping anhand des Suchbaums für das Constraint-Netz aus Abbildung 5.7 dargestellt:

Abbildung 5.16: Beispiel für graphenbasiertes Backjumping
\begin{figure}\index{GBJ}
\centering
\includegraphics[width=\linewidth]{images/constraints_backjumping}
\ifx\pdfoutput\undefined
\fi
\end{figure}

Beispiel 5.2.5   Angenommen wird, dass die Domänen bereits eingeschränkt wurden, und für die Variable MAINBOARD_SOCKEL_TYP nur noch die Werte Sockel_370 und Sockel_478 mögliche Belegungen darstellen. Angekommen bei der Belegung dieser Variable, wird durch den Algorithmus ein Konflikt festgestellt, für den keine alternative Belegung ermittelt werden kann. Die letzte durch ein Constraint mit MAINBOARD_SOCKEL_TYP verbundenen Variable ist PROZESSOR_SOCKEL_TYP, zu der nun unter Umgehung von KUEHLER_SOCKEL_TYP zurückgesprungen wird. Da auch für diese Variable keine gültige alternative Belegung ermittelt werden kann, ist nochmals Backjumping erforderlich (aufgrund der Struktur des Constraint-Netzes in diesem Fall äquivalent zu chronologischem Backtracking).

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 $v_{cur}$ in Konflikt mit einer bereits belegten Variable $v_i$ steht, wird $v_i$ dem conflict set von $v_{cur}$ hinzugefügt. Gibt es keine weiteren alternativen Werte für die Belegung von $v_{cur}$, erfolgt ein Backjumping zu der Variable $v_i$ im conflict set von $v_{cur}$, die sich am tiefsten im Suchbaum befindet und damit zuletzt vor $v_{cur}$ 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.



Fußnoten

...5.42
Zit. nach Bessière und Régin (1996, S. 63); Dechter (1992, S. 283); Dechter (1999, S. 196); Dechter und Frost (2002, S. 158 u. 184); Frost und Dechter (1994, S. 2); Güsgen, 2000, S. 279; Prosser (1993a, S. 1); Prosser (1993b, S. 268); Prosser (1995a, S. 185); Tsang (1993, S. 156).
...5.43
Die Variable, die als letztes mit einem Wert belegt wurde und über ein Constraint mit der aktuellen Variable im Constraint-Graph verbunden ist.
...5.44
Damit keine Informationen über bestehende Konflikte verloren gehen, werden bei einem Rücksprung die Variablen des conflict sets von $v_{cur}$ zu dem conflict set von $v_i$ hinzugefügt (mit Ausnahme von $v_i$ selbst).
...5.45
Im Zusammenhang mit Prolog wird DDBT auch engl. intelligent backtracking genannt. Des Weiteren begründen sich z.B. TMS auf der Anwendung von DDBT vgl. Dechter und Frost, 2002, S. 184; Kumar, 1992, S. 38 f.; Russel und Norvig, 2002, S. 157.

next up previous contents index
Nächste Seite: 5.2.4.4 Backchecking und Backmarking Aufwärts: 5.2.4 Suchverfahren Vorherige Seite: 5.2.4.2 Backtracking   Inhalt   Index