[인공지능] Path consistency, K-consistency

Path Consistency

3개의 변수가 관련된 consistency 로 arc consistency 의 문제점을 해결하기 위해 등장

Arc-consistency 의 문제점

Map coloring 문제를 2개의 color 만으로 해결하는 문제로 축소시켰을 때 이 문제는 답이 없음

답이 없는 경우 AC-3 알고리즘이 Domain 을 다 없애주어야하지만 그러지 못한다는 문제가 있음 ←  AC3 알고리즘이 아무것도 하지 않음

Path consistency 정의

Xi 와 Xj 에 값을 할당한 상태에서 {Xi, Xm}, {Xm, Xj} 를 만족하며 Xm 에 할당할 수 있는 값이 있다면 {Xi, Xj} 는 Xm 에 path consistent 함

모든 X 가 path consistent 하다면 해당 CSP 는 path consistent 하다고 함 

 

예제 : Map coloring with two colors

WA 에 red, SA 에 greeen 을 할당한 뒤 NT 에 가능한 값이 없으므로 이 문제는 답이 없음

K-Consistency

Consistency 문제를 일반화 시킨것으로

1-Consistency : Node consistency

2-Consistency : Arc consistency

3-Consitency : Path consistency

…

어떤 문제가 1-Consistency, 2-Consistency, …. , K-Consistency 를 모두 만족시킨다면 이 문제를 strongly k-consistent 하다고 함

변수가 N개인 문제에서 strongly N-consistent 하다면 이 문제를 O(n^2d) 로 풀 수 있음