되추적 알고리즘(BackTracking Algorithm)

BackTracking

되추적 알고리즘은 결과를 찾는 도중 막히면 다시 되돌아가 결과를 찾는다.

모든 노드를 탐색해서 만드는 DFS와 비슷하다.

 

구현 방법

 

DFS는 모든 노드를 탐색하며,

BackTracking은 모든 노드를 탐색하지만, 특정 조건을 설정해서 이 경로가 아니라고 판단되면 경로를 이탈하고 다시 되돌아 가며, 가지치기를 통해 불필요한 경로를 차단해 효율을 높일 수 있다.

 

실제 구현시, 고려할 수 있는 모든 경우의 수를 상태공간트리(State Space Tree)를 통해 표현한다.

 

각 후보군을 DFS(깊이 우선 탐색) 방식으로 확인

상태 공간 트리를 탐색하면서, 제약이 맞지 않으면 해의 후보가 될만한 다른 곳으로 바로 넘어가서 탐색한다.

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

Prusing : 조건에 맞지 않으면 포기하고 다른 루트로 바로 돌아가, 탐색의 시간을 절약하는 가지치기 기법

 

즉 , 백트래킹은 트리 구조를 기반으로 DFS로 깊이 탐색을 진행하면서 각 루트에 대해 조건에 부합하는지

Promising을 통해 체크하고, 만약 해당 트리에서 조건에 맞지 않는 노드는 더이상 DFS 탐색을 진행하지 않고, Prusing 가지를 쳐서 아래의 노드를 탐색하지 않는다.

 

예시 문제

 

N Queen 문제

 

NxN 크기의 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치하는 문제

State Space Tree 예시

4x4의 체스판을 가정해 4개의 퀸자리를 선택한다고 하면 굉장히 많은 가지의 경우의 수가 존재한다.

이 모든 경우의 수를 다 참조하여 판단하는 것은 매우 비효율적이다. 

 

이제 해당 가지의 경우에서 Promising과 Nonpromising을 적용하고 Prusing하면

유망한(Promising)노드의 밑으로 계속해서 깊이 우선 탐색을 진행하고, 유망하지 않은(Non-Promising)노드는 탐색하지 않고 Prusing(가지치기)를 하고 BackTrack하여 다른 Promising한 노드를 찾아 조사를 한다.

 

코드 구현 예제 N-Queen 구하기