Constraint Propagation in CSPs, Local Consistency, Node consistency, Arc consistency

Constraint Propagation in CSPs

- CSP 를 푸는 두 가지 방법 

• Search
• Constraint propagation

- 추론의 특정한 종류

• 변수가 취할 수 있는 값들이 줄어들게 된다.
• -> search space (탐색 공간) 이 줄어들게 된다. -> 효율성이 높아진다.

- 전처리 단계에 constraint propagation 이 일어나거나, search 중간에 일어날 수도 있음

 

 

 

Local Consistency

- Node consistency 

• CSP 를 구성하는 한 변수가 가질 수 있는 모든 변수, 즉 domain 이 변수의 unary constraint 를 모두 만족시킨다면  node-consistent 하다.
• 예) unary constraint : SA 노드는 green 을 싫어해서 칠할 수 없다. 
• <SA, SA ≠ green>
• 이때 SA 의 domain 이 {red, green, blue} 라면 , SA는 node-consistent 하지 않다.
• 따라서 SA의 domain 을 줄일 수 있다.  {red, green, blue} -> {red, blue}
• 이때는 SA 가 node-consistent 하게 된다.

- Arc consistency

• 변수의 모든 domain 이 변수의 binary constraint 를 모두 만족시킨다면 arc-consistent 하다.
• Xi 가 다른 변수 Xj 에 대해서 arc-consistent 하다는 것은, Xi 의 도메인 Di 에 모든 값들이  Dj 에 있는 적어도 하나의 값을 binary constraint 와 함께 만족시켜야 한다. 

 

- Arc consisteny 예제

  

ㅡ> map coloring 문제의 경우 모든 노드가 arc consistent 하기 때문에, domain 을 줄일 수 없다.

ex) WA 의 도메인도 {r,g,b} 이고 SA 의 도메인도 {r,g,b} 이기 때문에 (모든 노드의 도메인은 전체 색상을 가짐) , 

두 노드에 대해 arc-consistency 한 값들이 도메인에 적어도 하나 존재하기 때문에 이 경우 도메인을 줄일 수 없게 된다.

 

 

 

AC-3 Algorithm

입력으로는 csp 를 받고,  binary constraint 들을 arc로 표현하고 이를 모두 queue 에 넣는다.

먼저 queue 에서 하나를 꺼내고, 꺼낸 arc 를 가지고 arc-consistent 하게 만들기 위해서 domain 의 value 를 필요한 경우에 줄여주게 된다.

또한, domain 이 줄어들게 된다면 Xk 가 Xi 에 대해서 arc-consistent 했는데 이가 변경될 수 있기 때문에 Xk, Xi 를 큐에 넣어주는 작업이 필요하게 된다.

만약 search 이전에 AC-3 알고리즘을 적용한 전처리 작업에서 domain 이 empty 가 되었다면, 이는 solution 이 존재하지 않음을 의미한다.