백트래킹(Backtracking, 되추적)

모든 경우의 수를 전부 고려하는 알고리즘. 상태공간을 트리로 나타낼 수 있을 때 적합한 방식이다. 일종의 트리 탐색 알고리즘 방식으로 깊이우선탐색(Depth First Search, DFS)과 너비우선탐색(Breadth First Search, BFS), 최선 우선 탐색(Best First Search/Heuristic Search)이 있다.

모든 경우의 수를 고려해야 하는 문제라면 일반적으로 DFS가 편리하다. 그러나 DFS를 절대 쓰면 안 되는 경우가 있는데, 트리의 깊이가 무한대가 될 때이다. 미로찾기에서 루프(회로)가 발생하는 경우, DFS는 이 가지를 탈출할 수 없게 된다. 물론 중복검사를 막기 위한 장치를 넣을 수도 있지만, 그럴 바에는 BFS가 편하다. 또 분기점 없이 길이만 죽어라 긴 길이 나타나면 스택 오버플로가 발생할 수 있다. 위의 미로찾기도 4방향(또는 8방향)중 마지막으로 진입하는 방향으로만 갔을 때 도착점이 있다거나 하면 DFS는 느리다. 그리고 최단거리 구하기에서는 BFS를 사용하는 게 편리하다.

ㅇ 특징

   - 해를 구할 때까지 모든 가능성을 시도하게 됨
      . 갈 수 있는데까지 가보다가 막히면, (더이상 찾던 해가 없으면)
      . 되돌아와서 다른 길을 찾아봄
   - 되추적을 통해 탐색 대상을 줄여나감
      . 되추적이 발생하면, 해당 서브트리들은 탐색대상에서 제외됨
   - 주로, 그래프(상태 공간 트리)에 대해,
      . DFS(깊이우선탐색)으로 탐색하며, (트리 순회)
      . 재귀적으로 구현됨
   - 문제가 커질 경우 엄청난 시간이 걸리므로, 
      . 분기한정법(Branch-and-Bound) 등 탐색 범위를 줄이는 여러 보완을 취함

 

ㅇ 탐색 방법

   - (과정 1) 루트 노드를 현 위치 노드로 지정
   - (과정 2) 현 위치 노드의 각 자식 노드에 대해 아래의 과정을 진행
      . 해당 자식 노드 방향에 해가 있는지 확인
         .. 해가 없다면, 
             ... (과정 2)로 되돌아가서 진행
         .. 해가 있다면,  
             ... 해를 출력 또는 저장
             ... 하나의 해 만 구하는 문제인 경우에는 탐색 종료
      . 자식 노드를 현 위치 노드로 지정하고, (과정 2)로 감  (깊이우선탐색)
   - (과정 3) 부모 노드를 현 위치 노드로 지정한 후, 다음 자식 노드에 대해 (과정 2) 진행

ㅇ 적용 例) 미로 찾기 문제, 색칠 문제, 최적화 문제, 판정 문제 등등에 사용된다.

1.  DFS (깊이우선탐색, Depth First Search)

재귀함수 또는 스택을 사용하여 DFS를 구현할 수 있다.

 

2. BFS (너비우선탐색, Breadth First Search)

BFS는 큐를 사용하여 구현한다. 

 

3. 최선 우선 탐색 (Best First Search/Heuristic Search)

이 BFS에서 조금 더 발전한 방식이 Best First Search 방식이다. 큐 대신 우선순위 큐 또는 힙을 써서 구현하는데, 발생하는 새로운 경우를 순차적으로 검사하는 Breadth First Search와는 달리 현재 가장 최적인 경우를 우선적으로 검사하므로 상대적으로 효율적이다. 

백트래킹은 모든 경우를 다 고려하기 때문에 이걸 쓰면 어지간해서는 해결할 수도 있다. 다이나믹 프로그래밍으로 할 수 있는 것도 다 구현할 수 있으니 시간과 메모리만 해결하면 매우 유용하다. 해결하지 못했을 때 시간이 많이 걸려서 그렇지. 또한 무의미한 탐색을 막아줄 가지치기(Bounded(Promising) function)를 적용하여 적당한 지능(Heuristic)을 부여한다면 상당히 효과적인 해결방법이 될 수 있다.

 

 

출처]

정보통신기술용어해설 : 백트래킹

나무위키 : 백트래킹

 

 

참고 문제]

 

 

 

 

 

※ 10월 25일은 독도의 날입니다.

대한민국의 아름다운 영토, 독도