백트래킹

백트래킹이란?

해를 찾는 도중 해가 아니어서 막히면 되돌아가서 다시 해를 찾아가는 기법

DFS, BFS 와 명확하게 다르다고 할 수는 없을 것 같다.
해를 찾아가는 탐색 도중에 지금 경로가 해가 될 것 같지 않으면 더 이상 깊이 탐색하지 않고 이전 단계로 다시 돌아간다. 이를 가지치기 라고 한다.
이러한 가지치기 등으로 탐색을 더 효과적으로 수행하는 한가지 방법 정도라고 보면 될 것 같다.

백트래킹의 유망성 판단

어떤 노드의 유망성, 즉 해가 될 만한지 판단한 후 유망하지 않다고 결정되면 그 노드의 이전(부모)로 돌아가(Backtracking) 다음 자식 노드로 간다.

해가 될 가능성이 있으면 유망하다(promising)고 하며, 유망하지 않은 노드에 가지 않는 것을 가지치기(pruning) 한다고 하는 것이다