Backchecking (BC) und
Backmarking (BM), wie von Robert M. Haralick und Gordon L. Elliot vorgestellt, sind Erweiterungen, die
nach dem look-back-Prinzip arbeiten und dazu geeignet
sind, die Anzahl von u.U. rechenintensiven Konsistenztests eines
Backtracking-Suchverfahrens zu verringern
(vgl. Haralick und Elliot, 1980, S. 271 ff.).
Backchecking erreicht dies, indem sich der Algorithmus
Inkompatibilitäten zwischen neu zu belegenden Variablen und bereits
mit Werten belegten Variablen merkt. Wenn z.B. eine Variable
mit
belegt werden soll und eine Inkompatibilität mit der Belegung
einer vorher bereits belegten Variable
festgestellt wird,
merkt sich der Algorithmus dies und wird solange nicht mehr versuchen,
mit
zu belegen, wie
mit
belegt ist. Der Wert
wird dazu (temporär) aus der Domäne von
entfernt
(vgl. Tsang, 1993, S. 147).
Backmarking ist eine Erweiterung von
Backchecking, die sich neben den inkompatiblen zusätzlich
die bereits getesteten kompatiblen Belegungen merkt, und dadurch die
Anzahl der Konsistenztests weiter vermindert. Der Algorithmus merkt
sich während des Suchvorgangs in einer einfachen Datenstruktur für
jeden möglichen Wert einer Variablen
die früheste
vorhergehende Variable
in der Belegungsreihenfolge, ab der die
Teilbelegung
in Konflikt mit der Belegung
für
steht.5.46
Weiterhin merkt sich der Algorithmus für jede Variable
die
früheste Variable in der Belegungsreihenfolge, deren Wert sich
geändert hat, seitdem
das letzte Mal mit einem Wert belegt
worden ist. Aufgrund dieser Informationen ist der Suchalgorithmus in
der Lage zu entscheiden, ob sich die Belegung einer vorhergehenden
Variablen geändert hat, und wenn nicht, ob dessen Belegung weiterhin
inkompatibel oder kompatibel mit
ist.
Backchecking- und Backmarking-Algorithmen
wie hier beschrieben, können ausschließlich auf
Backtracking-Varianten angewendet werden, die eine statische
Reihenfolge bei der Belegung der Variablen
nutzen, da
sich die Konsistenztests und die Datenstrukturen auf eine fixe Ordnung
der Variablen beziehen.