[AI] Constraint Satisfaction Problems

1. Constraint Satisfaction Problem
 - Variable과 Domain 사이의 제약조건을 통해 미리 Variable에 대한 Domain을 제한하여 수행 속도를 올리는 방법

2. Map-Coloring Problem

 - 위처럼 나눠져 있는 지도에서 3개의 색으로 인접한 구역의 색과 겹치지 않도록 칠하는 방법이 있는지를 구하는 문제
 - Constraint graph를 통해 인접하는 구역을 표현할 수 있고, 해당 그래프를 이용해 색칠 하는 것이 가능

3. Varieties of Constraints
 - Variable의 수에 따라 분류 가능
 - Unary constraints : 하나의 변수를 특정 도메인으로 제약하는 Constraint
 - Binary constraints : 두개의 변수로 제약하는 Constraint
 - higher-order constraints : 3개 이상의 변수로 제약하는 Constraint

4. Cryptarithmetic

       T W O
    + T W O
    -----------
     F O U R
 - 같은 문자의 경우 같은 숫자이며 해당 연산 결과와 맞는 경우가 있는지 찾는 문제
 - Constraint를 정의하여 문제 풀이 가능

5. Real-world CSPs
 - Assignment Problems : 누가 어떤 과목을 강의 할지
 - Timetabling problems : 어떤 class를 언제 어디서 강의 할지
 - Transportation scheduling : 배송을 효율적으로 하는 방법

6. Backtracking search
 - 가능한 경우의 수를 모두 해보는 방식으로 graph에서 dfs방식으로 탐색.
 - 모든 경우의 수를 탐색하므로 정확한 결과를 얻을 수 있지만 필요 없는 계산이 너무 많음.(Cost가 높다)

7. Most constrained variable
 - 가장 단순한 방법으로 가능한 경우의 수 중 가장 빠른 것 부터 적용하는 방법

8. Most constraining variable
 - 가장 많은 연관성(제약)을 가진 곳부터 Domain을 할당하는 방식

9. Least constraining value
 - Domain 중 영향을 가장 적게 주는 value를 선택하는 방식.

10. Forward checking
 - 특정 variable의 value를 정해주고 난 뒤, constraint에 의해 value가 선택되지 않은 variable의 domain이 바뀌게 되는데,
   바뀔 때 마다 Domain을 바꿔 주어서 연산을 줄이는 방식

11. Arc consistency
 - 특정 Variable의 value가 정해졌을 때, constraint에 의해 value가 선택되지 않았을 경우 variable의 domain이 바뀌게 되고,
   해당 Domain의 남은 수가 1개일 경우 해당 value만 가능하므로 이 value를 선택했을 경우를 가정해 다시 Domain을 계속 줄여나가는 방식
 - AC-3 알고리즘이라고 불린다.