Kondycjonowanie cięcia

Pierwszy sposób zredukowania wykresu ograniczeń do drzewa polega na przypisaniu wartości niektórym zmiennym, tak aby pozostałe zmienne utworzyły drzewo. Rozważmy wykres ograniczeń dla Australii, ponownie pokazany na rysunku 6.12(a). Bez Australii Południowej wykres stałby się drzewem, jak w (b). Na szczęście możemy usunąć Australię Południową (na wykresie, a nie kraj) poprzez ustalenie wartości dla SA i usunięcie z domen pozostałych zmiennych wszelkich wartości, które są niezgodne z wartością wybraną dla SA. Teraz każde rozwiązanie dla CSP po usunięciu SA i jego ograniczeń będzie zgodne z wartością wybraną dla SA. (Działa to dla binarnych dostawców CSP; sytuacja jest bardziej skomplikowana z ograniczeniami wyższego rzędu.) Dlatego możemy rozwiązać pozostałe drzewo za pomocą algorytmu podanego powyżej, a tym samym rozwiązać cały problem. Oczywiście w ogólnym przypadku (w przeciwieństwie do kolorowania mapy) wartość wybrana dla SA może być niewłaściwa, więc musielibyśmy wypróbować każdą możliwą wartość. Ogólny algorytm wygląda następująco:

1. Wybierz podzbiór S zmiennych CSP tak, aby wykres ograniczeń stał się drzewem po usunięciu S . S to tzw. cutset cyklu.
2. Dla każdego możliwego przypisania do zmiennych w S, które spełnia wszystkie ograniczenia na S,
3. usunąć z dziedzin pozostałych zmiennych wszelkie wartości niezgodne z przypisaniem dla S , oraz
4. jeśli pozostały CSP ma rozwiązanie, zwróć je wraz z przypisaniem dla S.

Jeśli cutset cyklu ma rozmiar c , to całkowity czas działania wynosi O(dc ∙ (nc)d² : musimy wypróbować każdą z kombinacji wartości d² dla zmiennych w , a dla każdej kombinacji musimy rozwiązać problem drzewa size (nc) Jeśli wykres jest „prawie drzewem”, to c będzie małe, a oszczędności w porównaniu z prostym śledzeniem wstecznym będą ogromne – dla naszego przykładu ze 100-zmiennymi boolowskimi, gdybyśmy mogli znaleźć zbiór o rozmiarze c = 20 , to sprowadziłoby nas z czasu życia Wszechświata do kilku minut.W najgorszym przypadku jednak może być tak duży jak (n-2).Znalezienie najmniejszego zestawu cyklicznego jest NP-trudne, ale kilka wydajnych algorytmów aproksymacyjnych Ogólne podejście algorytmiczne nosi nazwę warunkowania zestawu przekrojów.