next up previous contents index
Nächste Seite: 5.2.4.6 Backtracking mit Look-Ahead Aufwärts: 5.2.4 Suchverfahren Vorherige Seite: 5.2.4.4 Backchecking und Backmarking   Inhalt   Index

5.2.4.5 Backtracking mit Forward Checking

Das von Haralick und Elliot (1980, S. 270 f.) vorgestellte Forward Checking (FC) verwendet eine einfache look-ahead-Strategie zur Reduktion des Suchraums und zum Aufspüren von Inkonsistenzen. Forward Checking ergänzt das Backtracking um eine vorausschauende Komponente, die eine eingeschränkte Form von Kantenkonsistenz herstellt.5.47 Immer dann, wenn der Backtracking-Suchalgorithmus eine Variable mit einem Wert belegt, werden die Wertebereiche der noch unbelegten, mit der aktuellen Variable über ein Constraint in direkter Abhängigkeit stehenden Variablen, auf inkonsistente Werte überprüft, die mit dem aktuell gewähltem Wert inkompatibel sind. Werte, die nicht zu der gewählten Belegung konsistent sind, werden aus den Wertebereichen der noch nicht belegten Variablen (temporär) entfernt. Es wird dadurch sichergestellt, dass sich in den Wertebereichen von zukünftig zu belegenden Variablen ausschließlich Werte befinden, die mit sämtlichen bisher belegten Variablen kompatibel sind. Durch das Schrumpfen der Wertebereiche wird der Suchraum ggf. drastisch eingeschränkt. Wenn die Domäne einer noch unbelegten Variable keine Werte mehr enthält, kann dadurch u.U. bereits sehr früh festgestellt werden, dass die aktuell gewählte Belegung keine mögliche Lösung darstellt. Stattdessen wird an dieser Stelle ein Backtracking initiiert.

Beispiel 5.2.6   Ein Beispiel für Forward Checking bezogen auf das Constraint-Beispiel aus Abschnitt 3.6.3 f. ist in Tabelle 5.3 dargestellt. In Zeile 2 können durch die Belegung der Variable P_FSB_Rate mit dem Wert 100 aus den Domänen der restlichen Variablen bereits einige Werte entfernt werden, die nicht mehr durch den Suchalgorithmus getestet werden müssen. In Zeile 3 kann direkt der kompatible (und einzig verbliebene) Wert für MB_FSB_Rate ausgewählt werden. Der erste Wert für die Variable S_FSB_Rate, der in Zeile 4 ausgewählt wird, führt sofort zu einer Lösung des Problems. Backtracking ist nicht erforderlich.


Tabelle 5.3: Beispiel für Forward Checking
  P_FSB_Rate MB_FSB_Rate S_FSB_Rate
1. initiale Domänen 66 100 133 66 100 133 66 100 133
2. P_FSB_Rate = 100 66 100 133 66 100 133 66 100 133
3. MB_FSB_Rate = 100   100     100     100 133
4. S_FSB_Rate = 100   100     100     100 133
5. Lösung   100     100     100  


Forward Checking ist ähnlich dem Backchecking bzgl. dem Entfernen inkonsistenter Werte, die inkompatibel zu einem aktuell gewählten Wert sind, bezieht sich allerdings im Gegensatz zum Backchecking-Algorithmus nicht auf eine Optimierung der rückwärtsgerichteten Backtracking-Phase, sondern versucht im Vorfeld Konflikte zu vermeiden. Wenn $v_i$ mit der Belegung $a$ und $v_j$ mit $b$ inkompatibel zueinander sind, und $v_i$ vor $v_j$ belegt wird, dann wird Forward Checking $b$ in dem Augenblick aus der Domäne von $v_j$ entfernen, wenn $v_i$ mit $a$ belegt wird. Backchecking würde $b$ aus der Domäne von $v_j$ entfernen, in dem Augenblick wenn $v_j$ belegt werden soll. Obwohl Backchecking eine Reihe von Konsistenztests vermeidet und solche aufschiebt, die u.U. später unnötig sind (die Belegung $v_i$ mit $a$ kann sich bereits wieder geändert haben, wenn $v_j$ an der Reihe ist) ist Forward Checking dem Backchecking überlegen, sowohl was die Anzahl der Backtracking-Schritte (und damit die Größe des Suchbaums) als auch die Anzahl der getesteten Wertebelegungen betrifft vgl. Haralick und Elliot, 1980, S. 271; Tsang, 1993, S. 147. Forward Checking erkennt Konflikte aufgrund der look-ahead-Strategie früher und ist dadurch in der Lage, ggf. früher Backtracking-Schritte durchzuführen. Obwohl Forward Checking mehr Rechenaufwand als einfaches Backtracking benötigt, sobald eine neue Variable mit einem Wert belegt wird, führt dieser Mehraufwand i.d.R. dazu, dass insgesamt das Problem effizienter gelöst werden kann. Ein grundsätzliches Ablaufschema von look-ahead-Algorithmen ist dem Flussdiagramm in Abbildung 5.17 zu entnehmen.

Eine Variante ist das von Dent und Mercer (1994b,a) vorgestellte Minimal Forward Checking (MFC)5.48, welches ggf. nicht jeden Wert von noch unbelegten Variablen auf Konsistenz mit der aktuellen Variable testet. Um festzustellen, dass die aktuelle Variablenbelegung zu einem domain wipe out führt, ist es ausreichend, für alle noch unbelegten Variablen lediglich einen einzigen konsistenten Wert pro Variable zu ermitteln.5.49 Zusätzliche Konsistenzüberprüfungen werden zu einem späteren Zeitpunkt durchgeführt, sobald diese notwendig werden. Die Anwendung von MFC führt im Vergleich zu normalem FC zu einer signifikanten Verbesserung durch eingesparte Konsistenztests, wenn es auf umfangreiche CSPs angewendet wird, d.h. CSPs mit vielen Variablen und großen Wertebereichen. Weitere aktuelle Erweiterungen des ursprünglichen Forward Checking, ein generelles Schema sowie eine Reihe darauf basierender Algorithmen werden von Bacchus (2000) vorgestellt.



Fußnoten

...5.47
Forward Checking entspricht der Kombination des Backtracking-Algorithmus mit der REVISE-Routine aus Abbildung 5.4.
...5.48
Auch: Lazy Forward Checking (LFC) (vgl. Kwan und Tsang, 1996a).
...5.49
Das Konzept ähnelt der dem Algorithmus AC-6 von Bessière (1994a) zugrunde liegenden Idee, für die Werte der Variablen vorerst lediglich eine konsistente Wertebelegung pro Constraint zu berechnen (vgl. Abschnitt 5.2.3.3). Weitere konsistente Belegungen werden bei Bedarf erzeugt (vgl. Dent und Mercer, 1994a, S. 432).

next up previous contents index
Nächste Seite: 5.2.4.6 Backtracking mit Look-Ahead Aufwärts: 5.2.4 Suchverfahren Vorherige Seite: 5.2.4.4 Backchecking und Backmarking   Inhalt   Index