백 트래킹
-
개념: 해를 찾기 위해, 후보군에 제약 조건을 점진적으로 체크하다가, 해당 후보군이 제약 조건을 만족할 수 없다고 판단되는 즉시 backtrack (다시는 이 후보군을 체크하지 않을 것을 표기)하고, 바로 다른 후보군으로 넘어가며, 결국 최적의 해를 찾는 방법
-
특징
- 제약 조건 만족 문제 (Constraint Satisfaction Problem) 에서 해를 찾기 위한 전략
- 만족할 수 없다고 판단되면 바로 밑의 답들 버리고 다시 위로 올라가 진행
- 고려할 수 있는 모든 경우의 수를 상태공간트리(State Space Tree)에 저장
- 상태공간트리에서는 DFS로 경우 탐색
- 각 루트에 대해 조건에 부합하는지 체크(Promising)
- Pruning (가지치기): 조건에 맞지 않으면 포기하고 다른 루트로 바로 돌아서서, 탐색의 시간을 절약하는 기법