2021.6.13 TIL : [알고리즘] 백트래킹 (BackTracking)

마지막 알고리즘 수업에서는 백트래킹과 NP-완전을 배웠다. 둘 다 조금은 이해하기 어렵다고 느껴져서 오늘은 이 내용을 정리해보고자 한다.

 

문제에서 어떤 해를 구할 때, 해의 형태가 n개의 원소로 이루어진 튜플인 경우가 있다. (이 때, 이 튜플 내의 각 원소를 x1, x2, x3, ... xn이라고 한다.) 해의 원소들(xi)은 유한 집합(Si)에서 선택된다. 백트래킹은 기준함수인 P를 최대화/최소화/만족하는 해를 구하는 문제를 해결하는데 적용하는 방법으로 효율적인 알고리즘이 존재하지 않을 경우에 사용한다. 모든 문제의 사례에 대해서 효율적이진 않지만 많은 문제 사례에서 효율적이다. 

 

mi를 Si의 크기, 즉 원소의 개수라고 하면, xi가 선택할 수 있는 해는 각각 m1, m2, m3, ..., mi, ..., mn개 있다. 백트래킹 알고리즘은 문제에서 가능한 해의 공간을 체계적으로 DFS를 이용하여 탐색함으로서 m보다 매우 작은 횟수의 시도로 해를 찾게 한다. 

 

백트래킹을 이용한 대표적인 문제가 N-Queens 문제이다. 

N-Queens 문제 설명 :

n x n 격자에 다음 조건을 만족하도록 n개의 Queen을 놓는다.

조건 1) 같은 행에 두 개의 퀸이 놓여서는 안 된다.

조건 2) 같은 열에 두 개의 퀸이 놓여서는 안 된다.

조건 3) 같은 대각선에 두 개의 퀸이 놓여서는 안 된다.

 

여기서 구하는 해의 구조는 튜플로 (x1, x2, x3, ..., xn) 으로 이루어질 것이며, 각 xi는 i번째 행에 놓여지는 퀸의 열의 위치이다. 예를 들면 다음과 같다.  

백트래킹 알고리즘을 위해서는 상태공간트리라는 개념을 알아야 한다. 상태공간은 해답을 탐색하기 위한 탐색 공간을 의미한다. 상태공간트리는 모든 가능한 해의 공간을 tree로 구성한 것이다. 시각적으로 표현해보면 다음과 같다. 

이 트리에서 DFS로 노드를 생성해 가면서 더 아래로 탐색할지 말지를 결정하면 된다. 즉 방문 중인 노드에서 하위 노드가 해답을 발견할 가능성이 있다면 해당 노드를 (promising)하다고 보는데, 다음 노드가 유망한지를 계속 판단하면서 내려가야 한다. 이 때 유망하지 않다고 판단되면 하위 트리를 가지치기(prune)를 통해 더 이상 탐색하지 않는다. 답이 될 가능성이 없는 경우에는 다시 위로 백트래킹하고, 답이 된 경우는 출력하고 return 하면 된다. 일반적인 백트래킹 알고리즘을 의사코드로 적어보면 다음과 같다.

void checknode(node v){
node u;
if (promising(v))
	if (v에 해답이 있으면)
    	해답을 출력;
    else
    	for (v의 모든 자식 노드 u에 대해서)
        	checknode(u);
}

백트래킹 알고리즘은 상태 공간 트리를 말 그대로 트리 형태로 구현할 필요는 없다. 현재 조사 중인 가지의 값에 대해 추적만 해 주면 된다. (상태공간 트리는 암묵적으로 존재한다고 이해하고 넘어가면 된다)

 

N-Queens 문제의 의사코드를 적어보면서 백트래킹 알고리즘에 대한 내용을 정리하려고 한다.

Algorithm nQueens(x, k, n)
//xk가 가질 수 있는 값들의 집합 T = {1, 2, ..., n}
for i = 1 to n
	if (place(x, k, i)) //place(x, k, i)는 bounding 함수임
    	x[k] = i; //답이 될 가능성이 있으면
    if(k == n) //해를 찾은 경우
    	x[1], x[2], ..., x[n]을 출력
    else
    	nQueens(x, k+1, n)