제약 충족 문제

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

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

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

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

같이 보기

• 제약 충족
• 선언형 프로그래밍
• 제약 프로그래밍
• 분산 제약 충족 문제(DisCSP)

참고 문헌

• Tsang, Edward (1993年). 《Foundations of Constraint Satisfaction》. Academic Press. ISBN 0-12-701610-4. 
• Dechter, Rina (2003年). 《Constraint processing》. Morgan Kaufmann. ISBN 1-55860-890-7. 
• Apt, Krzysztof (2003年). 《Principles of constraint programming》. Cambridge University Press. ISBN 0-521-82583-0. 

외부 링크

• Tomás Feder, Constraint satisfaction: a personal perspective
• Constraints archive
• Forced Satisfiable CSP Benchmarks of Model RB Archived 2021년 1월 25일 - 웨이백 머신
• Benchmarks -- XML representation of CSP instances