- 제약 만족 문제(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 }
'Study > Artificial Intelligence' 카테고리의 다른 글
Backward Chaining vs Forward Chaining (0) | 2010.09.30 |
---|---|
CSP vs BFS vs GA for N-Queen (0) | 2010.09.30 |
Genetic Algorithm (GA; 유전 알고리즘) (0) | 2010.09.30 |
Local beam search (0) | 2010.09.30 |
Best first search, A* algorithm (0) | 2010.09.30 |