[알고리즘] 백트래킹 - n-Queens, 해밀턴회로

되추적 (Back Tracking)

 

틀린 답에 접근했을 때, 틀리기 전의 상태로 돌아가서 다른 선택을 하는 알고리즘

 

만약 답이 나올 때까지가 시간 복잡도가 엄청 복잡하게 나올 수도 있지만, 이 답이 유망했는지 아닌지를 판별하면서 불필요한 노력을 절감할 수 있다.

 

되추적은 트리의 변형된 깊이우선탐색(DFS)이다.

 

깊이 우선 탐색 (depth - first search)

 

부모 마디 우선(preorder) 트리 검색은 트리의 깊이 우선 검색이다. 

 

이는 뿌리마디(root)를 먼저 방문한 후, 그 뿌리마디(node)의 후손들을 모두 방문한다.

 

예시로는 왼쪽에서 오른쪽의 순서로 마디의 자식을 방문한다.

깊이우선검색 순서에 따라 마디에 번호가 매겨진 트리

 

다음은 깊이우선검색을 하는 간단한 재귀 알고리즘을 쓰는 프로시저이다.

 

void depth_first_tree_search (node v)
{
	node u;
    visit v;
    for(each child u of v)
    	depth_first_tree_search(u);
}

 

위의 프로시저는 자연스럽게 왼쪽 노드에서 오른쪽 노드로 방문하게 된다.

 

$n$-여왕말 문제 ($n$-Queens problem)

 

$n=4$ 일 때 $n$-여왕말 문제 (4 - Queens problem)

 

4X4 체스판에 두 퀸이 서로 잡아먹지 않아야하는 문제이다.

(각각의 말들이 같은 열, 행, 대각선에 있으면 안된다.)

 

백트래킹을 활용해 트리로부터 알고리즘을 구성해야한다.

 

4 여왕말 문제를 백트래킹하는 과정을 트리로 나타낸 예시

위의 트리에서 유망하지 않은 마디는 x로 표시되어 있다.

4-여왕말 문제의 트리 사이즈의 크기

 

$$ 1+4+4^2+4^3+4^4=341 $$

 

341개의 마디를 가지고 있다. 실제로 dfs로 4여왕말 문제를 풀어보면 155번째에 정답이 발견된다.

유망함수(promising function)를 적절히 사용하면 27만에 찾을 수 있다.

 

유망함수(promising function) 설계

 

아래는 두 퀸이 같은 대각선에 있는지 확인하는 유망함수이다.

 

$$ \vert \mathrm{col}(i) - \mathrm{col}(k) \vert = \vert i-k \vert $$

 

이러한 유망함수가 점점 개발되면 백트래킹의 성능은 더 높아진다.

 

n-여왕말 문제의 트리 사이즈의 크기

 

$$1+n+n^2+ \cdots +n^n = \frac{n^{n+1} -1}{n-1} $$

 

예를 들어 $n=8$인 경우, 상태공간트리의 마디 개수는 $19,173,961$개이다.

 

여기서 유망한 마디의 개수의 상한을 구해보자 그 상한을 계산하기 위해 어떤 두 여왕말도 같은 열에 놓지 않는다는 사실을 이용하자. 예시로 $n=8$일 때를 보자

 

$$1 + 8 + 8\times 7 + 8\times 7 \times 6 + 8 \times 7 \times 6 \times 5 + \cdots + 8! = 109,601 $$

 

이 결과를 일반화하면,

 

$$1 + n + n \times (n-1) + n\times (n-1) \times (n-2) + n \times (n-1) \times (n-2) \times (n-3) + \cdots + n! $$

 

이다.

 

이러한 분석으로는 이 알고리즘의 효율성을 제대로 파악할 수 없다. 대각선 검사를 고려하지 않았고, 검사한 마디의 총 개수는 유망한 마디와 유망하지 않은 마디를 모두 포함한다.

 

 

 

아래는 백트래킹 알고리즘으로 푼 문제이다.

 

https://kimmessi.tistory.com/192?category=833468 

[백트래킹] BOJ 9663 N-Queen

 

 

반응형

 

몬테카를로 방법 (Monte Carlo method)

 

몬테카를로 방법(Monte Carlo method)은 반복된 무작위 추출(repeated random sampling)을 이용하여 함수의 값을 확률적으로 계산하는 알고리즘을 부르는 용어이다. 

 

$t_i \; \rightarrow $ 수준 $i$에서 어떤 마디의 자식 마디의 총 개수

 

$$ 1+ t_0 + t_0t_1 + \cdots + t_0t_1 \cdots t_i + \cdots $$

 

$m_i$만큼의 유망한 자식만 검사한다면, $(m_i \leq t_i)$ 검사한 마디의 총 개수 추정치는 다음과 같다.

 

$$ 1+ t_0 + m_0t_1 + m_0m_1t_2 +\cdots + m_0m_1 \cdots m_{i-1}t_i + \cdots $$

 

특정 사례를 얼마나 효율적으로 처리하는지에 대한 추정치가 있다면 그 사례에 대해 그 알고리즘을 사용하는 게 타당한지 결정 가능하다.

 

여기서 $m_i$는 수준 $i$에서 마디들의 유망한 자식마디의 평균 개수의 추정치이다.

표본공간의 무작위 표본의 평균치를 가지고 표본공간에서 정의된 무작위 변수의 기대치를 추정한다. (알고리즘이 오래 실행할수록 실제 기대치에 근접한다)

 

그래프 색칠하기 문제 (Graph Coloring Problem)

 

m-색칠하기 문제는 비방향그래프에서 서로 인접한 정점이 같은 색을 갖지 않도록 최대 m개의 다른 색으로 칠하는 방법을 모두 찾는 문제이다. (planer graph를 찾는 문제)

planer graph $\rightarrow \;$  그래프 중 간선이 꼬이지 않은 그래프

 

Analysis (상태공간트리의 노드 수)

 

$$ 1+m+m^2 + \cdots + m^n = \frac{m^{n+1}-1}{m-1} $$

 

해밀턴 회로 문제 (Hamiltonian Path Problem)

 

해밀턴 경로

 

각 노드를 한 번씩만 방문하고 시작한 노드에서 끝내야한다.

 

Analysis (상태공간트리의 노드 수)

 

$$ 1+ (n-1) + (n-1)^2 + \cdots + (n-1)^{n-1} = \frac{(n-1)^{n-1}}{n-2} $$