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.
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 mit der Belegung
und
mit
inkompatibel zueinander sind, und
vor
belegt wird,
dann wird Forward Checking
in dem Augenblick aus der
Domäne von
entfernen, wenn
mit
belegt wird.
Backchecking würde
aus der Domäne von
entfernen,
in dem Augenblick wenn
belegt werden soll. Obwohl
Backchecking eine Reihe von Konsistenztests vermeidet und
solche aufschiebt, die u.U. später unnötig sind (die Belegung
mit
kann sich bereits wieder geändert haben, wenn
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.