-
[인공지능] Local consistency인공지능 2020. 12. 5. 19:29728x90
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)
'인공지능' 카테고리의 다른 글
[인공지능] CSP Backtracking 탐색 (0) 2020.12.05 [인공지능] Path consistency, K-consistency (0) 2020.12.05 [인공지능] CSP 문제 (0) 2020.12.05 [인공지능] Game AI 이론 (0) 2020.12.05 [인공지능] Partial observable search (0) 2020.12.03