[인공지능] Local consistency

Constraint propagation

변수에 들어갈 수 있는 domain 의 수를 줄임으로서 탐색공간의 축소로 이어짐

constraint propagation 은 search 전에 전처리로 사용되거나 search 중간 중간에 이루어지는 경우가 많음

Local Consistency

Node consistency

한 변수의 Domain 전체가 Unary constraint 를 만족한 경우

예를 들어 “A 는 짝수이다.” 라는 constraint 가 있었는데 여기에 “A 는 2가 아니다.” 라는 unary constraint 가 추가된 상황

이 때 “A 는 짝수이다.” 라는 constraint 가 변하지 않고 있으면 node consistency 하지 않은 것이고, “A는 2가 아닌 짝수이다.” 라고 변한다면 이는 node consistency 한 것임

Arc consistency

변수의 모든 Domain 이 변수와 관련된 Binary constraints 를 모두 만족하는 경우

Xi 가 Xj 에 대해서 arc-consistency 하다고 말하려면 Xi 의 Domain Di 의 모든 원소는 Xj 의 Domain Dj 의 적어도 한 원소와의 binary constraint 를 만족시켜야함

 

예시

Constraint : Y = X2

Domain : 0-9

4의 경우에는 constraint 를 만족하는 Y 가 없으므로 위 예제는 Arc-consistent 하지 않음

X 의 Domain 을 0-3 으로 바꾼다면 arc-consistent 함

 

Map Coloring 문제의 경우에는 Arc-consistency 가 아무런 의미를 가지지 못함

항상 arc-consistent 하기 때문임

AC-3 알고리즘

 

모든 arc 가 arc-consistent 하거나 domain 이 남아있지 않은 변수가 있을 경우에는 답이 없음(no solution)