5.2.4.4 Backchecking und Backmarking

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 $v_j$ mit $b$ belegt werden soll und eine Inkompatibilität mit der Belegung $a$ einer vorher bereits belegten Variable $v_i$ festgestellt wird, merkt sich der Algorithmus dies und wird solange nicht mehr versuchen, $v_j$ mit $b$ zu belegen, wie $v_i$ mit $a$ belegt ist. Der Wert $b$ wird dazu (temporär) aus der Domäne von $v_j$ 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 $a$ einer Variablen $v_i$ die früheste vorhergehende Variable $v_p$ in der Belegungsreihenfolge, ab der die Teilbelegung $\vec{a}_p$ in Konflikt mit der Belegung $a$ für $v_i$ steht.^5.46 Weiterhin merkt sich der Algorithmus für jede Variable $v_i$ die früheste Variable in der Belegungsreihenfolge, deren Wert sich geändert hat, seitdem $v_i$ 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 $v_i=a$ 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 $v_1,\ldots,v_n$ nutzen, da sich die Konsistenztests und die Datenstrukturen auf eine fixe Ordnung der Variablen beziehen.

Fußnoten

...^5.46

Constraints mit Variablen, die sich weiter vorne in der Belegungsreihenfolge befinden, müssen zuerst getestet werden.