Algorytm AC-3 - AC-3 algorithm

Algorytm AC-3 (skrót od Arc Consistency Algorithm #3) jest jednym z szeregu algorytmów wykorzystywanych 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 z późniejszych jest trudnych do zaimplementowania, dlatego AC-3 jest najczęściej nauczanym i używanym w bardzo prostych programach do rozwiązywania ograniczeń.

Algorytm

AC-3 operuje na ograniczeniach , zmiennych i domenach zmiennych (zakresach). Zmienny może mieć dowolną z wielu dyskretnych wartości; zbiór wartości dla konkretnej zmiennej jest znany jako jej domena . Ograniczeniem jest to związek , który ogranicza lub ogranicza wartości zmienna może mieć. Ograniczenie może obejmować wartości innych zmiennych.

Aktualny stan CSP podczas działania algorytmu może być postrzegany jako graf ukierunkowany , w którym węzły są zmiennymi problemu, z krawędziami lub łukami między zmiennymi, które są powiązane ograniczeniami 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 dziedziny 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; gdy domena zmiennej ma usunięte jakiekolwiek wartości, wszystkie łuki ograniczeń wskazujące na tę przycinaną zmienną (z wyjątkiem łuku bieżącego ograniczenia) są dodawane do kolekcji. Ponieważ domeny zmiennych są skończone i albo jeden łuk, albo co najmniej jedna wartość jest usuwana na każdym kroku, algorytm ten gwarantuje zakończenie .

Na przykład, 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 domeną 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 pomiędzy X i Y, ponieważ C2 jest nieskierowane, ale reprezentacja grafu używana przez AC-3 jest skierowana.

Robi 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 wynikające z C2 . Tylko pary ( X =0, Y =4), ( X =2, Y =2) i ( X =4, Y =0) pasują do ograniczenia C2 . AC-3 następnie kończy się, 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:

 Input:
   A set of variables X
   A set of domains D(x) for each variable x in X. D(x) contains vx0, vx1... vxn, the possible values of x
   A set of unary constraints R1(x) on variable x that must be satisfied
   A set of binary constraints R2(x, y) on variables x and y that must be satisfied
   
 Output:
   Arc consistent domains for each variable.
 
 function ac3 (X, D, R1, R2)
     // Initial domains are made consistent with unary constraints.
     for each x in X
         D(x) := { vx in D(x) | vx satisfies R1(x) }   
     // 'worklist' contains all arcs we wish to prove consistent or not.
     worklist := { (x, y) | there exists a relation R2(x, y) or a relation R2(y, x) }
 
     do
         select any arc (x, y) from worklist
         worklist := worklist - (x, y)
         if arc-reduce (x, y) 
             if D(x) is empty
                 return failure
             else
                 worklist := worklist + { (z, x) | z != y and there exists a relation R2(x, z) or a relation R2(z, x) }
     while worklist not empty
 
 function arc-reduce (x, y)
     bool change = false
     for each vx in D(x)
         find a value vy in D(y) such that vx and vy satisfy the constraint R2(x, y)
         if there is no such vy {
             D(x) := D(x) - vx
             change := true
         }
     return change

Algorytm ma najgorszy przypadek złożoności czasowej O ( ed ³ ) i złożoność przestrzenną O ( e ), gdzie e to liczba łuków, a d to rozmiar największej dziedziny.

Bibliografia

• AK Mackwortha. Spójność w sieciach relacji . Sztuczna inteligencja , 8:99-118, 1977.
• Stuarta Russella i Petera Norviga. Sztuczna inteligencja: nowoczesne podejście , 202-233, 2003.