인공지능 제약조건 만족 문제

제약조건 만족 문제

제약조건 만족을 하기 위한 방법은 총 두 가지가 있는데 백 트랙킹 방식과 제약 조거 건 전파 방식이 있다.

우선 이 두 가지를 설명하기 위해서 4-퀸(queen) 문제로 예시를 들어보겠다.

 

1. 백 트랙킹 탐색

백 트랙킹 탐색은 깊이 우선 탐색을 하는 것처럼 변수에 허용되는 값을 하나씩 대입하며 만족하는 값이 없으면 이전 단계에 돌아가 그 이전 단계의 변수에 다른 값을 대입하는 탐색 방식이다.

우선  이런 4x4의 게임판이 있다고 했을 때 A, B, C, D순서로 퀸을 놓을 수 있다 하였을 때 우선 A-0자리에 퀸을 놓았을 때 발생하는 이벤트는 총 네 가지이다.

하지만 여기서 2가지는 서로 퀸의 범위가 겹치기에 허용이 안되며 3번째 경우는 만족하기에 계속 탐색을 하다 보면

 

이 처럼 모든 탐색이 만족하지 않으므로 다시 맨 처음 노드로 돌아가 새로운 노드를 만든다.

하지만 새로운 노드마저도 결과적으론 게임의 승리를 하지 못하는 경우밖에 없기에 처음 루트 노드의 퀸의 위치를 바꿔 다시 탐색을 해보면

이런 식으로 탐색을 하는 것이 백 트랙킹 탐색 방식이다.

 

2. 제약조건 전파

제약조건 전파 방식은 특정 제약조건에 따라 각 변수에 허용될 수 없는 값들을 제거하는 방식이다.

위의 그림처럼 각자 놓을 수 있는 숫자를 나타내 주고 만약에 A가 1번에 위치에 퀸을 놓는다면

허용될 수 없는 위치들을 제거를 하면 이를 순차적으로 계속 진행하다 보면

결국 C에 놓을 수 없기에 다시 이전 단계로 돌아가 다시 탐색하게 된다.