제약 충족 문제

제약 충족 문제(Constraint satisfaction problem, CSP)는 복수의 제약 조건을 충족하는 상태를 찾아내는 수학 문제를 가리킨다. CSP는 특히 인공지능이나 운용 과학 분야에서 심도 있게 연구되고 있다. 보통 CSP는 고도의 복잡성을 보이기 때문에 적정한 시간 내에 문제를 풀기 위해서는 휴리스틱과 조합 최적화 기법을 조합할 필요가 있다.

제약 충족 문제의 구체적인 예:

 8퀸 문제
 4색 문제
 스도쿠
 충족 가능성 문제

제약 충족 문제를 푸는 알고리즘은 AC-3 알고리즘, 백트랙킹, 제약 위반 최소화 등이 있다.

 같이 보기 
 제약 충족
 선언형 프로그래밍
 제약 프로그래밍
 분산 제약 충족 문제(DisCSP)

 참고 문헌 




 외부 링크 
 Tomás Feder, Constraint satisfaction: a personal perspective
 Constraints archive
 Forced Satisfiable CSP Benchmarks of Model RB 
 Benchmarks -- XML representation of CSP instances

분류:제약 프로그래밍
분류:알고리즘
분류:인공지능
분류:운용 과학