[알고리즘] 백트래킹 (Backtracking)

퇴각검색(영어: backtracking, 한국어: 백트래킹)은 한정 조건을 가진 문제를 풀려는 전략이다. "퇴각검색(backtrack)"이란 용어는 1950년대의 미국 수학자 D. H. 레머가 지었다.  문제가 한정 조건을 가진 경우 원소의 순서는 해결 방법과 무관하다. 이런 문제는 변수 집합으로 이뤄지는데, 한정 조건을 구성하려면 각각의 변수들은 값이 있어야 한다. 퇴각검색은 모든 조합을 시도해서 문제의 해를 찾는다. 이것이 장점이 될 수 있는 이유는 퇴각검색 구현 방법들이 많은 부분 조합들을 배제하기 때문이다. 결국 풀이 시간이 단축된다.

1. 한정 조건을 가진 문제를 풀려는 전략

 - 해를 찾기 위해, 해의 후보를 전짐적으로 확인하여, 해당 후보가 제약 조건을 만족할 수 없다고 판단한 경우 backtrack하여, 다음 후보로 넘어가 최적의 해를 찾는 전략

 

2. backtrack

- 제약 조건을 만족할 수 없다고 판단한 후보에 대하여 다음 단계에서 다시 확인하지 않도록 표기하는 방법

 

3. 모든 경우의 수

- 각 후보의 모든 경우의 수를 상태공간트리를 통해 표현하고 각 후보를 DFS 방식으로 확인한다.

 

4. Promising

- 확인 단계에서 해당 루트가 조건에 맞는지를 검사하는 기법

 

5. Pruning

- 조건에 맞지 않는 루트를 포기하고 다른 루트로 방향을 옮겨 탐색 시간을 절약하는 기법

 

 

백트래킹의 과정

 

1. 문제 상황을 상태 공간 트리로 표현한다.

2. 루트 부터 DFS를 하여 불필요한 탐색을 하지 않고 한정 함수를 만족하는 (x[1], x[2], ..., x[n])를 찾는다.

3. 각 노드 s 에 도착할 때마다 루트에서 s까지의 경로 예를 들어 k번째 선택에선 (x[1], x[2], ..., x[k])의 튜플이 한정함수를 만족하는지 판단한다.
4-1.  (x[1], x[2], ..., x[k])의 튜플이 한정 함수를 만족한다면 x[k] 노드를 live node이자 e-node로 변경한다.
4-2. 한정함수를 만족하지 않는 다면 T(x[1], ... x[k])의 노드들을 더이상 확장하지 않으며 dead node로 만든다.
5.  k < n일때 x[k]의 자식 노드들인 x[k+1] 들 즉, T(x[1], ... x[k])을 탐색한다.
6. 모든 자식 노드를 탐색했다면 현재 노드를 dead node로 변경한다.
7. 진행 도중 한정함수를 만족하는 (x[1], x[2], ..., x[n])에 도달하면 정답을 출력한다.
8. 정답이 도출되었거나 모든 노드가 dead 노드가 되었다면 탐색을 종료한다. 이때 정답이 여러개 인 경우에 모든 정답을 찾고 싶다면 모든 노드가 dead 노드가 될때까지 탐색해야 한다.