백트래킹

• 백트래킹이란 현재 상태에서 가능한 모든 경로를 따라 들어가 탐색하는 방법이다.
• 원하는 값이 아닐 경우 더 이상 탐색을 진행하지 않고 전 단계로 back해서 돌아가는 방법으로 이름 그대로 backtracking 알고리즘

관련용어

• 유망함(promising): 진행중인 경로가 해답을 찾을 가능성이 있음
• 유망하지 않음(nopromising): 진행중인 경로가 해답을 찾을 가능성이 없음
• 가지치기(pruning): 유망하지 않은 하위 트리를 잘라냄

특징

• 어떤 노드의 유망성을 점검한 후에 유망하지 않다고 결정되면 그 노드의 부모로 되돌아가 다음 자식 노드로 탐색
• 어떤 노드를 방문했을 때 그 노드를 포함한 경로가 해답이 될 수 없으면 그 노드는 유망하지 않음
• 해답의 가능성이 있으면 유망함
• 가지치기 사용가능 (유망하지 않은 노드가 포함되는 경로는 고려하지 않는 기법)
• 기본적으로 재귀의 성격을 띄는 형태

백트래킹과 DFS의 차이점

백트레킹

• 어떤 노드에서 출발하는 경로가 그 해결책으로 이어질 것 같지 않으면 더 이상 경로를 탐색하지 않음으로써 시도 횟수 감소
• 불필요한 경로의 조기 차단
• N! 가지의 경우의 수를 가진 문제에 대해 백트레킹에 가하면 일반적으로 경우의 수가 줄어들지만 최악의 경우는 처리 불가능
• 모든 후보를 검사하지 않음

DFS

• 모든 경로를 추적
• N! 가지의 경우의 수를 가진 문제에 대해 깊이 우선 탐색을 이용하면 처리 불가능
  모든 후보를 검사

활용 예시

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

최적화 문제, 결정 문제에서 많이 사용
미로 찾기 / n-Queen 문제 / Map coloring / 부분 집합의 합 등