백트래킹 (Back Tracking)

목차

---

백트래킹 (Back Tracking)

: 해를 찾는 도중 해가 절대 될 수 없다고 판단되면, 되돌아가서 해를 다시 찾아가는 기법이다.

--> 알고리즘 기법 중 하나로 모든 경우의 수를 전부 고려하는 알고리즘이다. 상태공간을 트리로 나타낼 수 있을 때 적합한 방식으로 일종의 트리 탐색 알고리즘이라고 봐도 된다.

 

>> 방식에 따른 종류

• 깊이우선탐색(Depth First Search, DFS)
• 너비우선탐색(Breadth First Search, BFS)
• 최선우선탐색(Best First Search/Heuristic Search)

 

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

: 그래프 순회 방식의 일종으로, 트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙이 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방식이다. 일반적으로 재귀호출을 사용하여 구현하지만, 단순한 스택 배열로 구현하기도 한다. 구조상 Stack Overflow를 유의해야 한다.

 

>> 장점

• 단지 현 경로상의 노드들만 기억하면 되므로 저장공간의 수요가 비교적 적다.
• 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

>> 단점

• 해가 없는 경로에 깊이 빠질 가능성이 있다.
• 얻은 해가 최단 경로가 된다는 보장이 없다. --> 목표에 이르는 경로가 다수인 문제에 대해 DFS는 해에 다다르면 탐색을 끝내버리므로, 이때 얻은 해가 최적이 아닐 수 있다.

※ 이해를 위한 애니메이션 예시

출처 : https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

 

※ 참고 사이트

링크 : 위키백과 - 깊이우선탐색