Backtracking

백트래킹

어떠한 문제가 모든 가능성을 조사하지 않고는 해를 구할 수 없는 경우, 모든 가능성을 조직적이고 효율적으로 조사하는 방법
'조사하지 않아도 되는 부분은 조사 대상에서 제외, 해를 빨리 찾는다.'
이러한 백트래킹의 해는 어떠한 제한조건을 만족하는 n개의 원소로 구성된 벡터인 (x1, x2, x3, ..., xn)의 형태로 나타낼 수 있다.
이러한 이유는, 해의 표현을 어떻게 정하느냐 하는 것은 알고리즘의 설계 방향 및 시간복잡도를 결정하기 때문에 위와 같이 단순한 형태로 나타낸다.
따라서, 해를 결정하는 과정에서 아니다 싶은 것은 사전에 제거하는데, 이때 DFS의 변형을 통해 가지치기하여 결정한다.

분기한정
백트래킹과 유사하나, 해를 찾기 위해 백트래킹과 같이 어느 특정한 운행 방법뿐만 아니라 깊이 우선 탐색을 비롯한 너비 우선 탐색, 최고 우선 탐색 등 다양한 방법을 모두 이요할 수 있는 포괄적인 방법이다.