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

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

Constraint Propagation in CSPs

- CSP 를 푸는 두 가지 방법

Search

Constraint propagation

- 추론의 특정한 종류

변수가 취할 수 있는 값들이 줄어들게 된다.

-> search space (탐색 공간) 이 줄어들게 된다. -> 효율성이 높아진다.

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

Local Consistency

- Node consistency

CSP 를 구성하는 한 변수가 가질 수 있는 모든 변수, 즉 domain 이 변수의 unary constrain t 를 모두 만족시킨다면 node-consistent 하다.

t 를 모두 만족시킨다면 하다. 예) unary constraint : 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 을 줄일 수 없다.

AC-3 Algorithm

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

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

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

만약 전처리 작업에서 domain 이 empty 가 되었다면, 이는 solution 이 존재하지 않음을 의미한다.

from http://jyeonnyang2.tistory.com/112 by ccl(A) rewrite - 2021-11-23 20:27:08