[알고리즘] 백트래킹 알고리즘 ( BackTracking Algorithm )

이전 글 :)

[알고리즘] 계수 정렬 (Counting Sort)

---

https://gfycat.com/ko/babyishtightjanenschia-mazesolving-backtracking

 

 백트래킹 backtracking 

 

백트래킹은 상태 공간이 트리로 나타 낼 수 있을 때 적합한 방식으로 일종의 그래프 탐색 알고리즘입니다.

가능한 모든 방법을 탐색한다는 방법론을 기본으로 하고 있으며 흔한 비교 알고리즘으로는 완전 탐색방법의 DFS (Depth First Search, 깊이 우선 탐색)이 있습니다.

 

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

DFS는 그래프 탐색 알고리즘의 일종으로 가능한 모든 경로를 탐색하는 알고리즘입니다.
이른 이름과 같이 넓게(wide) 탐색하기 전에 깊게(deep) 탐색 하며 모든 노드를 방문하고자 하는 경우에 이 방법을 선택합니다.

 

백트래킹과 DFS의 차이는 분명합니다.

 

백트래킹은 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더 이상 가지 않고 되돌아갑니다. 이는 가능한 모든 경로를 탐색하는 DFS와의 큰 차이점입니다.

이러한 차이점은 반복문의 횟수를 줄이면서 공간, 시간적 자원을 아낄 수 있습니다.

 

이렇게 해가 될 것 같지 않은 경로는 탐색하지 않는 것을 가지치기(pruning)라고 하는데, 불필요한 부분을 쳐내고 올바른 가지로 뻗어 탐색한다는 의미입니다.

 

불필요한 경로를 탐색하지 않아 자원을 절약할 수 있는 장점이 있지만, 만약 N! 의 경우의 수를 가진 문제에서 최악의 경우에는 여전히 지수함수 시간이 필요로 하므로 처리가 불가능할 수도 있습니다. 이처럼 그래프 탐색 알고리즘이 필요한 모든 문제에 대해서 적용하는 것이 아니라, 가지치기를 얼마나 잘하느냐에 따라 효율적으로 적용해야 됩니다.

 

https://medium.com/swlh/recursive-backtracking-for-combinatorial-path-finding-and-sudoku-solver-algorithms-1bf46ba2838c

 

 유망성 판단과 가지치기 

 

유망성 판단과 가지치기는 백트래킹의 핵심입니다.

해가 될 만한지를 판단하는 것을 유망성 판단이라고 합니다.

해가 될 가능성이 있으면 유망하다(promising)고 하며, 노드의 유망성을 판단한 후 유망하지 않다고 판단이 되면 그 노드의 부모 노드로 돌아가 다음 자식 노드로 탐색을 합니다. 유망하지 않은 노드에 가지 않는 것을 가지치기(pruning)한다고 하는 것입니다.

 

 

 예시 

 

백트래킹은 재귀 또는 스택을 이용합니다.

 

보통 재귀와 스택을 혼합해서 사용하며 대체로 재귀 함수의 종료 시점을 처음에 지정한 후 반복문을 배치해 그 안에서 각각의 경우에 대해 값을 바꿔가며 재귀 함수를 호출합니다.

# 백트래킹의 기본 재귀 함수

def backtracking(params,...) :
    if... :
	return
       
    for i in range(param,...) :
    	backtracking(i+1,...)
    return