[개념] Backtracking

Backtracking

- 문제의 해결 방법을 탐색하다 가능성이 없다고 판단되는 후보를 즉시 가지치기(Pruning)하는 방식

- bfs 와 같은 방식으로 탐색하는 모든 방법으로, bfs는 backtracking의 골격을 이루는 알고리즘

- bfs 와 같은 재귀 방식으로 구현

- 운이 좋으면 시행착오를 거치지 않고 해답을 얻을 수 있지만, 최악의 경우 모든 경로를 거쳐야 함

- backtracking 에서 사용되는 가지치기(Pruning) 는 트리의 탐색 최적화 문제(제약 충족 문제(constraint satifaction problems))와도 연관

 

* 제약 충족 문제 : 수많은 제약 조건(constraint)을 충족하는 상태(States)를 찾아내는 수학 문제

                           : ex) 스토쿠, 8퀸 문제, 4색 문제, 배낭 문제, 문자열 파싱, 조합 최적화

 

 

[그림 1]

[그림 1] 은 개략적인 포함 관계를 나타낸다.

 

 

예시 문제 추가 예정