Backtracking

백트래킹(=퇴각검색) , 일종의 트리 탐색 알고리즘.

해를 찾아가는 중에 막히면 다시 이전으로 돌아가서 해를 찾아가는 기법으로, 최적화 문제와 결정 문제를 풀 때 사용.

 

- 깊이우선탐색 (Depth First Search, DFS)

- 너비우선탐색 (Breadth First Search, BFS)

 

- 최선우선탐색 (Best First Search/Heuristic Search)

 

모든 경우의 수를 검색 > DFS.

트리의 깊이가 무한대이면 BFS

 

 

 

 

DFS는 가능한 모든 경로를 탐색함. 일일이 하나씩 체크해보면서 노가다하는 탐색임.

백트래킹은 DFS 방식과 비슷한데, DFS처럼 해를 찾아가는 중에, 다음에 갈 경로로 하면 해가 절대 안나올것 같으면 그 경로는 가지않고 되돌아감.

이렇게 조건을 설정해서 안가는 경로를 체크하여 경우의 수를 확연하게 줄임.

이런 것을 가지치기라 하는데, 불필요한 부분은 쳐내고 필요한 부분으로만 가게 만들어 주는 것임.

가지치기를 잘해야지 효율성이 좋음.

 

한줄정리하면, 백트래킹은 모든 가능한 경우의 수에서 특정 조건을 만족하는 경우의 수만 확인하는 것.

답이 될지 안될지 판단해서 가지치기 하는 것이 백트래킹임.

  

유망한지 유망하지않은지 판단해서 않다고 판단하면 그 노드의 부모노드로 돌아간다음 다음 자식노드로 이동함.(Backtracking)

유망하다고 하면 유망하지 않는 노드에 안가게 가지치기함.(Pruning)

재귀함수는 깊이우선탐색으로 구현가능.

 

---