백 트래킹 기법

1. Back Tracking 

 

백트래킹 혹은 퇴각 검색으로 불려진다.

제약 조건 만족 문제에서 해를 찾기 위한 전략 중 하나로 후보군에 제약 조건을 점진적으로 체크하다가, 해당 후보군이 제약조건을 만족할 수 없다고 판단되는 즉시 다시는 이 후보군을 체킹 하지 않을 것을 표기한 다음 다른 후보군으로 넘어가는 방법이다.

 

실제 구현시 모든 경우의 수를 상태 공간 트리를 통해 표현한다.

 - 각 후보군을 DFS 방식으로 확인

  1) Promising : 해당 루트가 조건에 맞는지를 검사하는 기법

  2) Pruning : 조건에 맞지않으면 포기하여 탐색 시간 절약하는 기법

 

 

즉 백트래킹은 트리 구조를 기반으로 DFS로 깊이 탐색을 진행하면서 각 루트에 대해 조건에 부합하는 지제크 하고 조건이 다르다면 더 이상 자식 노드를 검사하지 않고 가지를 처버 린다.

 

 

상태 공간 트리

 

문제 해결 과정의 중간 상태를 각각의 노드로 나타낸 트리이다.