[Search] 제약조건 만족 문제

개요

제약조건 만족 문제란 주어진 제약 조건을 만족하는 조합 해를 찾는 문제를 말합니다. 대표적으로 체스판에서의 퀸의 배치 상태를 구하는 N-Queen 문제가 있습니다.

이 제약조건 만족 문제에 대한 탐색 기반의 해결방법에는 백트래킹 탐색과 제약조건 전파가 있습니다.

백 트래킹 탐색

백 트래킹 탐색의 특징은 다음과 같습니다.

• 깊이 우선 탐색을 하는 것 처럼 뼌수에 허용되는 값을 하나씩 대입
• 모든 가능한 값을 대입해서 만족하는 것이 없으면 더 이상 그 자식 노드들을 검사하지 않고 부모 노드로 돌아가서 이전 단계의 변수에 다른 값을 대입

백트래킹 탐색 방법을 사용하면 4-Queen 문제를 다음과 같이 풀이할 수 있습니다.

제약조건 전파

제약조건 전파 방법의 특징은 다음과 같습니다.

• 인접 변수 간의 제약 조건에 따라 각 변수에 허용될 수 없는 값들을 제거하는 방식
• 모든 값이 제거되어 선택이 불가한 변수가 생기면 이전 변수에서 다른 값을 선택

제약조건 전파 방법을 사용하면 4-Queen 문제를 다음과 같이 풀이할 수 있습니다.

정리

이번 포스팅에서는 간단하게 인공지능에서 사용되는 제약조건 탐색 문제를 살펴보았습니다.

대표적으로 백트래킹 탐색 방법과 제약조건 전파 방법에 대해 알아보았습니다.