백트래킹

 목표를 찾아가는 도중에 어떤 노드에서 출발하는 경로가 해가 될 것 같지 않으면 그 경로를 따라가지 않고

 

되돌아감으로써 시도 횟수를 줄인다. 이를 가지치기(Pruning)이라고 하는데, 불필요한 부분의 연산을 줄이는 것이다.

 

깊이 우선 탐색과 비교했을 때, 깊이 우선 탐색은 모든 경로를 추적하는데 반해,

 

백트래킹은 불필요한 경로를 조기에 차단하기 때문에 경우의 수가 상대적으로 많이 줄어든다.

 

하지만 N!의 경우의 수를 가진 문제에서는 여전히 최악의 경우 지수함수 시간을 필요로 하기 때문에 

 

처리가 불가능하다. 따라서 가지치기를 잘하는 것에 따라 효율이 결정된다.

 

쉽게 말하자면 특정한 조건을 만족하는 경우만 고려하고, 그렇지 않은 경우 과감하게 쳐낸다는 뜻이다.

 

 

이는 다양한 탐색에서 조건을 걸어 답이 도출되기 힘든 상황에서는 과감하게 돌아가는 등의 연산을 실행해서

 

탐색시간을 줄이는 데에 많이 쓴다.

 

 

 

백트래킹 기법의 기본은 다음과 같다.

 

어떤 노드의 유망성을 확인한 후에 유망(Promising)하지 않다고 확인이 되면 그 노드의 부모로 

 

되돌아가서(Backtracking) 다음 자식 노드로 간다.

 

즉, 특정 노드를 방문했을 때 해다 노드가 해답으로 갈 수 있다면 유망한 것이고, 그렇지 않다면 

 

유망하지 않은 것이다. 이 유망하지 않은 노드 쪽의 경로를 고려하지 않는 것이 바로 가지치기(Pruning)이다.

 

 

 

대표적인 문제는 N-Queen 문제인데,

 

다음과 같은 백트래킹 알고리즘 절차를 적용해서 풀어보자.

 

- 상태 공간 트리(State Space Tree)의 깊이 우선 탐색을 실시

 

- 각 노드가 유망한지 확인

 

- 유망하지 않다면 다시 돌아가서 탐색

 

 

라고 이해했다.