나의 캐리어 안 공간에 비해 내가 가지고 가야할 것들은 너무나도 많습니다. 이럴 때 우리가 해야 하는 것은 바로 선택이지요. 주어진 조건에 우리가 맞추어 가장 합리적인 선택을 해야 합니다.
주어진 조건 속에서 우리가 선택해야 하는 것들… 이런 문제를 제약 만족 문제(Constraint Satisfaction Problem:CSP)라고 표현할 수 있습니다. 우리는 이와 같은 문제 상황을 일상생활에서 자주 마주하게 됩니다. 여행 기간 동안에도 많이 마주하게 되네요. 일정한 기간 동안 우리가 짜야할 코스, 정해진 시간 안에 갈 수 있는 대중교통 수단의 선택문제, 비행기가 지연되었을 때 어떤 순서로 비행기를 배치하는 스케쥴링 문제 등 즐거운 여행길에도 수많은 선택의 기로에 놓이게 되네요.
제약 만족 문제에 대해 살펴봅시다. 제약만족문제에서 따져보아야 하는 것은 주어진 제약조건, 이 제약조건을 충족시키기 위해 해답이 될 수 있는 변수 그리고 변수를 채울 수 있는 것들의 집합(정의역)이 도메인입니다. 짐 싸기 문제를 살펴보도록 하지요. 주어진 제약조건은 무엇일까요? 바로 캐리어가 하나라는 점입니다. 또 그 캐리어 안의 공간적인 제약도 있을 수 있겠네요. 그렇다면 변수는 무엇일까요? 변수는 바로 캐리어 안의 공간이라고 볼 수 있습니다. 이 공간 안에는 화장품, 옷, 컵라면 따위의 짐이 들어올 수 있겠네요. 이러한 짐들이 바로 도메인입니다. 짐들 중에는 선택되는 것들도 있고, 선택되지 않는 것들도 있겠네요. 제약만족문제는 도메인들을 변수에 넣어서 주어진 조건에 맞는 답을 구하는 것을 목표로 합니다. 위와 같은 상황에서는 캐리어 하나(제약조건)의 공간(변수)에 여러 짐들(도메인)을 넣어서 최적의 여행 짐을 쌓는 것이 목표라고 보면 되겠네요.