해탐색 알고리즘

1. 백트래킹 기법

해를 찾는 도중에 막히면 되돌아가서 다시 해를 찾는 기법으로, 최적화 문제와 결정 문제를 해결한다. 깊이 우선 탐색을 진행한다. 

모든 경우의 수를 확인하는 상태 공간 트리에서는 이파리 노드 수만 계산해도 (n-1) ! 이다. 이진트리로 계산해도 최악의 경우 2^n 개의 노드를 탐색해야 한다. 이는 시간이 오래 걸리기 때문에, 백트래킹 기법의 가지치기를 하면 효율적이다. 

1-1. TSP

best solution 이 16인 상태

1-2. n-Queens

Queen 은 같은 행, 열, 대각선에 위치할 수 없다. 

 

이 문제도 상태 공간 트리로 탐색하면 4^4=256 의 해가 있다. 하지만 백트래킹 기법을 사용하면 최초 해를 발견하기 까지 27번의 탐색만 하면 된다. 

 

1-3. 부분집합의 해

1-4. 그래프 색칠하기

2. 분기 한정 기법

백트래킹 기법은 깊이 우선 탐색이기 때문에 사실상 대부분의 노드를 탐색하여야 한다는 한계가 있다. 이때 bound 값을 기준으로 너비 우선 탐색을 하는 분기 한정 기법을 사용하면 단점을 보완할 수 있다. bound란, 해당 노드 이후로 확장했을 때 얻을 수 있는 해의 예상값이다. 노드에서 bound 값을 계산해서, 그 노드가 탐색할 가치(promising)가 있는지 판단한다.

분기 한정 기법은 상태 공간 트리의 각 노드에 특정한 값 (한정값) 을 부여한다. 너비 우선 탐색 중에서도 둘 중 더 유망한 것을 먼저 탐색하는 최선 우선 탐색 (Best First Search) 을 사용한다. 즉, 최적해가 있을 만한 영역을 먼저 탐색한다. 

2-1. TSP 

 

activeNodes 에서 최솟값을 제거하고, 제거하는 값의 자식들을 추가한다. 

TSP 문제를 풀기 위해 백트래킹 알고리즘은 54개의 노드 방문해야 했지만, 분기 한정 알고리즘은 22개에 그쳤다. 분기 한정 알고리즘이 더 우수한 성능을 보인다. 

 

2-2. 0/1 배낭 문제

a) breadth-first 분기 한정

b) best-first 분기한정