제약 충족 문제 (constraint satisfaction problem)

한 줄 정의: 변수, 각 변수가 가질 수 있는 값(도메인), 지켜야 할 제약으로 정의되어 모든 제약을 만족하는 값 배정을 찾는 문제 유형이에요.

쉽게 풀면

시간표를 짤 때는 과목마다 시간과 교실을 정해야 하고, 같은 선생님이 두 수업을 동시에 할 수 없다는 조건을 지켜야 해요. 이렇게 여러 변수에 값을 정하되 조건을 모두 지키는 답을 찾는 문제를 제약 충족 문제라고 해요. 스도쿠도 대표적인 예예요.

왜 중요한가

일정 계획, 자원 배분, 설정 문제 등 실제 문제를 표현하는 일반 틀이라 인공지능과 운영연구에서 폭넓게 쓰여요. 풀이 알고리즘의 효율 비교가 주요 연구 주제예요.

논문에서는 이렇게 쓰입니다

"강의실 배정 문제를 제약 충족 문제로 정식화하고 제약 전파를 적용해 탐색 노드 수를 90% 줄였다."

현실 문제를 CSP로 바꿔 풀이 효율을 높인 문장이에요.

조금 더 깊게 보면

기본 풀이는 변수에 값을 하나씩 정하다 제약을 어기면 되돌아가는 백트래킹이에요. 여기에 남은 값이 가장 적은 변수부터 고르는 휴리스틱, 값을 정할 때마다 다른 변수의 가능한 값을 줄이는 순방향 검사와 아크 일관성 같은 제약 전파를 더해 효율을 높여요. 그래프 색칠, 스케줄링, 논리식 만족 문제(SAT)가 모두 CSP로 표현될 수 있어요. 일반적인 CSP는 NP-완전이라 최악의 경우 어려운 문제예요.

주의할 점

기호주의 인공지능은 기호와 규칙으로 지능을 구현하려는 접근법 전체이고, 제약 충족 문제는 그 안에서 쓰이는 특정한 문제 표현 틀이에요. 최적의 답을 찾는 최적화 문제와 달리 기본 CSP는 조건을 만족하는 답을 찾는 것이 목표예요.