Oznaczanie wsteczne

W przypadku spełniania ograniczeń znakowanie wsteczne jest wariantem algorytmu śledzenia wstecznego .

Oznaczanie wsteczne działa jak śledzenie wsteczne poprzez iteracyjne ocenianie zmiennych w określonej kolejności, na przykład ${\ displaystyle x_ {1}, \ ldots, x_ {n}}$ . Poprawia to śledzenie wsteczne, zachowując informacje o ostatnim przypadku $utworzenia instancji$ do wartości oraz informacje o tym, co zmieniło się od tego czasu W szczególności:

Przykład, w którym wyszukiwanie osiągnęło xi=d za pierwszym razem.

1. dla każdej zmiennej $rejestruje$ wartości $za$ informacje o ostatnim ustawieniu na ${\ displaystyle x_ {i}}$ \ $a}$ ; w ${\ Displaystyle x_ {1}, \ ldots, x_ {j}, x_ {i}}$ przechowuje minimalny indeks $że$ przypisanie do był wtedy niespójny ;
2. dla każdej zmiennej $czasu$ pewne informacje dotyczące tego, co zmieniło się $;$ ostatniej w szczególności przechowuje minimalny indeks $która$ została zmieniona od tego czasu

Pierwsza informacja jest zbierana i przechowywana za każdym razem, gdy algorytm ocenia zmienną do $} i$ { $displaystyle a$ się to po prostu poprzez sprawdzenie spójności bieżących przypisań dla $}} \ Displaystyle x_ {1}, x_ {i}}$ , dla ${\ Displaystyle x_ {1}, x_ {2}, x_ {i}}$ , dla ${\ Displaystyle x_ {1}, x_ {2}, x_ {3}, x_ {i}}$ itd.

Kiedy wyszukiwanie osiąga xi=d po raz drugi, część ścieżki jest taka sama jak za pierwszym razem.

Druga informacja jest zmieniana za każdym razem, gdy oceniana jest inna zmienna. W szczególności indeks „maksymalnej niezmienionej zmiennej od ostatniej oceny $za każdym razem, gdy$$jest$ zmienna zmienia wartość. Za każdym razem $}$$się$${ \ displaystyle i>$ zmienna , wszystkie zmienne są rozpatrywane po kolei. Jeśli $powiązany$ indeks był ich poprzednim powiązanym indeksem, ta wartość jest zmieniana na ${\ Displaystyle min (k, j)$ .

Zebrane w ten sposób dane służą do uniknięcia pewnych kontroli spójności. W szczególności, ilekroć śledzenie $za {$ ustawiłoby , oznaczenie wsteczne porównuje $x_$ indeksy względem pary $i} = a$ Dwa warunki pozwalają określić częściową zgodność lub niezgodność bez sprawdzania z ograniczeniami. jeśli ${\ displaystyle k}$ jest minimalnym indeksem zmiennej, która zmieniła się od czasu ostatniej $oceny$ i minimalnym indeksem takim $,$${\ displaystyle x_ {1}, \ ldots, x_ {j}, x_ {i}}$ był spójny ostatnim razem, gdy został oceniony na ${\ displaystyle a}$ , a następnie: x ja $\ displaystyle x_ {$

1. jeśli ${\ Displaystyle j <k}$ , ocena ${\ Displaystyle x_ {1}, \ ldots, x_ {j}, x_ {i}}$ jest nadal niespójna, ponieważ tak było wcześniej, bo jak dotąd żadna z tych zmiennych nie uległa zmianie; w rezultacie dalsze sprawdzanie spójności nie jest konieczne;
2. jeśli $k}$$geq$ ocena nadal $ale$ przypisanie może nadal niespójne

W przeciwieństwie do innych wariantów backtrackingu, backmarking nie zmniejsza przestrzeni poszukiwań, a jedynie ewentualnie zmniejsza liczbę ograniczeń, które spełnia częściowe rozwiązanie.

•   Dechter, Rina (2003). Przetwarzanie ograniczeń . Morgana Kaufmanna. ISBN 1-55860-890-7 .