Algorithm - Backtracking(백트래킹)

Backtracking :

해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾는 기법. 최적화 문제와 결정 문제를 푸는 방법이 된다. / 가능한 모든 방법을 탐색한다라는 성격을 가짐. / 모든 경우의 수를 전부 고려하는 알고리즘. 상태 공간을 트리로 나타낼 수 있을때 적합한 방식(일종의 트리 탐색 알고리즘). 방식에 따라서 DFS, BFS, 최선 우선 탐색 등이 있다. DFS가 일반적. / 현재 상태에서 가능한 모든 후보군을 따라 들어가며 해결책에 대한 후보를 구축해 나아가다 가능성이 없다고 판단되면, 즉시 후보를 포기하면서 정답을 찾아가는 범용적인 알고리즘. 

 

DFS와 Backtracking :

DFS - DFS의 장점은 무한히 깊은곳을 찾아야 할때 효과적이고 단점은 모든곳을 방문하기 때문에 굳이 목표지점에 있지 않은 경로로 빠져서 비효율적인 결과를 초래할 수 있음. 즉 불필요할 것 같은 경로를 사전에 차단하거나 하는 등의 행동이 없으므로 경우의 수를 줄이지 못함. -> N! 가지의 경우를 갖는 문제는 DFS로 처리가 불가능함.

Backtracking - 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지않고 되돌아감. -> 반복문의 횟수까지 줄일 수 있으므로 효율적임. = 가지치기(Purning) 라고함. 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미. 일반적으로, 불필요한 경로를 조기에 차단할 수 있게 되어 경우의 수가 줄어들지만, 만약 N!의 경우의 수를 가진 문제에서 최악의 경우 여전히 지수함수 시간을 필요로 하므로 처리가 불가능 할 수 있음. 가지치기를 얼마나 잘하느냐에 따라 효율성이 결정되게 됨. / 즉, Backtracking은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것. / 답이 될만한지 판단하고 그렇지 않으면 그 부분까지 탐색하는 것은 하지않고 가지치기 하는 것. / 문제 풀이 시에 DFS등으로 모든 경우의 수를 탐색하는 과정에서, 조건문 등을 걸어 답이 절대로 될 수 없는 상황을 정의하고, 그러한 상황일 경우에는 탐색을 중지시킨 뒤 그 이전으로 돌아가서 다시 다른 경우를 탐색하게끔 구현.

Backtracking시 해가 될 가능성이 있는 노드를 유망하다(promising)라고 한다 함. 해가 유망하지 않다고 결정되면 해당 노드의 이전 노드로 backtracking.

 

Backtracking 절차 :

① DFS 수행 - 재귀함수나 Stack을 이용해서 계속 이동하는 DFS를 수행하여 노드를 찾는다.

② 유망한 Node 검토 - 방문한 노드를 포함해서 유망한 노드이면 subtree로 이동하고 그렇지 않으면 backtracking 수행.

③ Subtree 이동 - 방문한 노드의 하위 노드로 이동하여 다시 Recursion을 통해 DFS수행.

④ Backtracking 수행 - 방문한 노드를 가지치기하고 상위 노드로 backtracking 한 후 DFS를 다시 수행.