제약 충족 문제(CSP - Constraint satisfaction problem)

제약 충족 문제 또는 제약 만족 문제라고 불리는 CSP는 상태가 여러 제약 조건이나 제한 사항을 충족해야 하는 개체 집합으로 정의된 수학적 질문입니다. CSP는 제약 만족 방법으로 해결되는 변수에 대한 유한 제약 조건의 동종 모음으로 문제의 개체(Entity)를 나타냅니다. CSP는 인공지능과 운영 연구(Operations Research)에서 주로 연구되고 있습니다.

이 문제는 규칙성은 겉보기에 관련이 없어 보이는 많은 집합의 문제를 분석하고 해결하기 위한 공통 기반을 제공합니다. CSP는 높은 복잡성을 나타내는데, 합리적인 시간 내에 해결하기 위해 휴리스틱 및 조합 검색 방법이 필요합니다. 그래서 나온 제약 프로그래밍 (CP)은 특히 이러한 종류의 문제를 해결하는 데 중점을 둔 연구 분야입니다.

 

제약 충족 문제로 모델링 할 수 있는 문제의 예는 유형 추론, 여덟 퀸즈 퍼즐, 지도 색칠 문(4색 정리)제, 스도쿠, 십자말 풀이, 후토시키 ,카쿠로, 등이 있습니다.

4색 정리 https://redcarrot.tistory.com/48

8 퀸즈 문제 https://ko.wikipedia.org/wiki/%EC%97%AC%EB%8D%9F_%ED%80%B8_%EB%AC%B8%EC%A0%9C

더 알고 싶으시다면!

: 제약 만족 문제 더 알아보기!