[인공지능] CSP 문제

Factored state representation

기존에는 state 가 atomic 하게 표현되었다면 지금부터는 state 를 변수로 표현하는 문제에 대해 다룰 것입니다.

이러한 문제를 CSP(Constraint Satisfaction Problem) 이라고 합니다.

state 가 제약조건(Constraint)을 만족하는지 검색하는 것

CSP 는 General-purpose heuristic 이 존재함 : 일반화된 heuristic

CSP 문제 정의법

• X : 변수 집합

• D : 도메인 집합

• C : 제약조건 집합

• Ci = <scope, rel>

• scope : 제약 조건에 관련된 변수들

• rel : 변수들 간의 relation(관계)

• 예시 : <(X1, X2), {(A, B), (B, A)}>
  X1 이 A이면, X2 는 B이고, X1이 B이면, X2는 A 이다.

• State : 할당된 변수가 존재한다면 해당 상태를 state 라 함

• Consistent, Legal assignment : 제약 조건을 모두 만족하는 state

• Complete assignment : 모든 변수에 값이 할당된 state

• Solution : Complete assignment 이면서 consistent 한 상태

Map coloring 문제

지도에서 서로 인접한 지역은 다른색으로 칠하는 문제

Constraint Graph

Constraint 로 서로 관련된 Variable 끼리 묶은 그래프

CSP 장점

• 많은 문제들이 CSP 로 표현될 수 있음

• state-space search 보다 더 빠르게 해결할 수 있음

• General heuristic 이 존재하기 때문

특징

• 일반적으로 descrete(이산) variable 과 finite(유한) domains 를 가짐

• Infinite discrete, Continuous domain 또한 가능

• Constraint types

• Unary

• Binary

• Ternary

• BETWEEN(X, Y, Z) : Y는 X, Z 사이에 있다.

• Global contraint : 문제 전역적으로 적용되는 constraint : 예) 스도쿠

Cryptarithmetci Puzzle (Constraint Hypergraph)

T, W, O와 F, O, U, R 에 모두 다른 수를 대입하여 올바른 수식을 만들어내는 문제

Hypergraph 라는 것은 ternary constraint 가 포함된 그래프를 말함

C1, C2, C3 의 domain 은 0 또는 1로도 수정 가능

Alldiff 는 각 변수들이 모두 다른 값을 가져야함을 의미 (Global constraint)

Hyper edge