What is a CSP?
- Finite set of variables V1 , V2, · · · , Vn
- Nonempty domain of possible values for each variable DV1, DV2, · · · , DVn
- Finite set of constraints C1, C2, · · · , Cm
Varieties of CSPs
- Discrete variables
- Finite domains
- Infinite domains (integers, strings, etc.)
- Continuous variables
E.g. start/end times for Hubble Telescope observations Linear programming
우리는 이 중에서 finite 도메인을 고려함
CSP benefits
- 표준화된 표현
- 상태는 변수의 값에 대한 할당
- 점진적 vs. 전체 상태
- 전역 검색 vs. 지역 검색
- 일반적인 휴리스틱
- CSP는 문제-specific 전문 지식 없이도 사용할 수 있는 일반적인 휴리스틱을 제공
- 제약 그래프의 구조 활용
- 제약을 위배하는 콤비를 다 날릴 수 있음
Inference in CSPs
제약조건을 위배하지 않았는지 살펴보는 것
- Constraint propagation
- Intertwined with search, or done as a preprocessing step
서치와 엮여 있거나, 전처리 과정으로 수행된다
CSP도 서치다
- Incremental formulation : CSP는 점진적으로 변수를 할당해 나가는 방식으로 문제를 해결
- A state is an assignment of values to some or all variables Initial state:
the empty assignment {}
- Actions: assign value to an unassigned variable provided that there is no conflict
- Goal test: the current assignment is complete
- Path cost: irrelevant (고려x)
- Solution is found at depth n (if there are n variables) → DFS가 사용될 수 있다