Algorytm AC-3
W przypadku spełniania ograniczeń algorytm AC-3 (skrót od Arc Consistency Algorithm #3) jest jednym z serii algorytmów używanych do rozwiązywania problemów spełniania ograniczeń (lub CSP). Został opracowany przez Alana Mackwortha w 1977 roku. Wcześniejsze algorytmy AC są często uważane za zbyt nieefektywne, a wiele późniejszych jest trudnych do wdrożenia, dlatego AC-3 jest najczęściej nauczany i używany w bardzo prostych rozwiązaniach z ograniczeniami.
Algorytm
AC-3 działa na ograniczeniach , zmiennych i domenach zmiennych (zakresach). Zmienna może przyjmować dowolną z kilku wartości dyskretnych ; zbiór wartości dla określonej zmiennej jest znany jako jej domena . Ograniczenie to relacja , która ogranicza lub ogranicza wartości , które może mieć zmienna. Ograniczenie może dotyczyć wartości innych zmiennych.
Bieżący stan CSP podczas algorytmu można postrzegać jako skierowany wykres , w którym węzły są zmiennymi problemu, z krawędziami lub łukami między zmiennymi, które są powiązane więzami symetrycznymi, gdzie każdy łuk na liście roboczej reprezentuje ograniczenie, które należy sprawdzić spójność . AC-3 kontynuuje badanie łuków między parami zmiennych ( x , y ). Usuwa te wartości z domeny x , które nie są zgodne z ograniczeniami między x i y . Algorytm przechowuje kolekcję łuków, które nie zostały jeszcze sprawdzone; kiedy z domeny zmiennej usunięto jakiekolwiek wartości, wszystkie łuki ograniczeń wskazujące na tę przyciętą zmienną (z wyjątkiem łuku bieżącego ograniczenia) są dodawane do kolekcji. Ponieważ dziedziny zmiennych są skończone i albo jeden łuk, albo co najmniej jedna wartość są usuwane w każdym kroku, algorytm ten gwarantuje zakończenie .
Dla ilustracji, oto przykład bardzo prostego problemu z ograniczeniami: X (zmienna) ma możliwe wartości {0, 1, 2, 3, 4, 5} — zbiór tych wartości jest dziedziną X , lub D( X ). Zmienna Y ma dziedzinę D( Y ) = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Wraz z ograniczeniami C1 = „ X musi być parzyste” i C2 = „ X + Y musi być równe 4” mamy CSP, który AC-3 może rozwiązać. Zauważ, że rzeczywisty wykres ograniczeń reprezentujący ten problem musi zawierać dwie krawędzie między X i Y , ponieważ C2 jest nieskierowany, ale reprezentacja grafu używana przez AC-3 jest skierowana.
Czyni to najpierw usuwając nieparzyste wartości z domeny X zgodnie z wymaganiami C1 , pozostawiając D( X ) = { 0, 2, 4 }. Następnie bada łuki między X i Y implikowane przez C2 . Tylko pary ( X =0, Y =4), ( X =2, Y =2) i ( X =4, Y =0) pasują do ograniczenia C2 . AC-3 kończy się wtedy z D( X ) = {0, 2, 4} i D ( Y ) = {0, 2, 4}.
AC-3 jest wyrażony w pseudokodzie w następujący sposób:
Dane wejściowe: Zbiór zmiennych X Zbiór dziedzin D(x) dla każdej zmiennej x w X. D(x) zawiera vx0, vx1... vxn, możliwe wartości x Zbiór ograniczeń jednoargumentowych R1(x) na zmienną x, które muszą być spełnione Zestaw ograniczeń binarnych R2(x, y) dla zmiennych x i y, które muszą być spełnione Wyjście: Domeny spójne łukowo dla każdej zmiennej. function ac3(X, D, R1, R2) // Dziedziny początkowe są zgodne z ograniczeniami jednoargumentowymi. dla każdego x w X D(x) := { vx w D(x) | vx spełnia R1(x) } // 'worklist' zawiera wszystkie łuki, które chcemy udowodnić spójność lub nie. lista robocza := { (x, y) | istnieje relacja R2(x, y) lub relacja R2(y, x) } wybierz dowolny łuk (x, y) z listy roboczej lista robocza := lista robocza - (x, y) jeśli zmniejsz łuk (x, y) jeśli D(x) jest puste zwróć błąd else worklist := worklist + { (z, x) | z != y i istnieje relacja R2(x, z) lub relacja R2(z, x) } podczas gdy lista robocza nie jest pusta funkcja arc-reduce(x, y) bool change = false dla każdego vx w D(x) znajdź wartość vy w D(y) taką, że vx i vy spełniają ograniczenie R2(x, y) jeśli nie ma takiego vy { D(x) := D(x) - vx zmiana := prawda } zwróć zmianę
Algorytm ma złożoność czasową w najgorszym przypadku O ( ed 3 ) i złożoność przestrzenną O ( e ), gdzie e to liczba łuków, a d to rozmiar największej domeny.
- AK Mackworth. Spójność w sieciach relacji . Sztuczna inteligencja , 8:99-118, 1977.
- Stuarta Russella i Petera Norviga. Sztuczna inteligencja: nowoczesne podejście , 202-233, 2003.