Constraint Satisfaction Problem (CSP; 제약 만족 문제)

- 제약 만족 문제(Constraint Satisfaction Problem; CSP)

- 주어진 제약 조건을 만족시키는 해를 찾는 탐색 방법으로, 이 제약 조건을 만족시킨 상태가 CSP의 목적 상태이다.

- 제약 조건을 만족시키지 않으면 탐색 범위에서 제외되기 때문에 탐색 공간을 줄일 수 있고, 모든 상태가 제약 조건을 만족시키지 않을 경우, 해가 없음을 미리 알 수 있는 예측적 성격을 갖는다.

- 어느 도메인에서든 제약 조건만 변경하면 적용할 수 있으므로, 도메인 독립적이다.

- 해를 찾는 과정을 추적(trace)할 수 있다.

- 각각의 변수가 가지는 도메인 내에서 문제에 주어진 모든 제약 조건을 만족하는 해를 찾는 문제로 정의

- 구성 요소

domain variable : 상태값이 저장되어 있는 변수, 각 변수 사이에는 제약조건(constraint)이 존재함.

domain value : domain variable에 할당(assign)될 수 있는 값들의 집합.

constraint : variable 간에 존재하는 제약조건, 문제 해결을 위한 제약조건.

- 어떤 문제가 CSP로 정형화 되면 제약 네트워크로 구성가능, 변수(노드로 표현), 도메인(노드내의 요소), 제약 조건(노드 간의 아크)

- 변수의 개수와 도메인의 크기가 증가할수록 탐색공간과 탐색 시간이 지수적으로 증가, 효과적인 탐색 기법과 도메인 제거 기법 요구됨

- 일관성 검사 기법 : NC, AC, PC.

NC(Node consistency), AC(Arc consistency), PC(Path consistency)

- 예를 들어 Map-Coloring 문제의 경우

- domain valiable : WA, NT, Q, NSW, V, SA, T

- domani value : {red, green, blue}

- contraint : WA ≠ NT, or (WA, NT) ∈ {(red, green), (red, blue), (green, red), (green, blue), ...}

WA ≠ NT, WA ≠ SA, NT ≠ Q, SA ≠ Q, Q ≠ NSW, SA ≠ NSW, SA ≠ V, V ≠ T

- 특정 domain valiable에 domain value가 할당된 경우에 제약 조건에 따라 다른 domain valiable에 할당 가능한 domain value가 제한된다. (Node consistency)

- 위 두 그림은 Arc consistency가 적용되어 domain valiable에 할당가능한 domain value를 제한한다.

- Solution : { WA = red, NT = green, Q = red, NSW = green, V = red, SA = blue, T = green }