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

  • Node consistency

  • Arc consistency

    • X → Y is consistent iff for every value x of X there is some allowed y
    • X가 값을 잃으면 X의 이웃들도 다시 체크해야 함

    

    • time complexity : O(cd^3) (호 개수 c, 한 호는 최대 d번만 삽입됨, 호 일관성 강제 d^2)

  • Path consistency

  • k-consistency e.g. k가 2이면 arc, 3이면 path

• 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가 사용될 수 있다