알고리즘(Algorithm) – Backtracking (되추적)

되추적(backtracking)? 갈림길에 표시를 해 두었더라면…  간단히 말해서 되추적은 갈림길에 표시를 해 두는 기법이다.

되추적 기술 n-Queens Problem Monte Carlo Technique Graph Coloring 강의 순서 Backtracking 되추적 기술 n-Queens Problem Monte Carlo Technique Graph Coloring Hamiltonian Circuits

깊이우선검색 (Depth-first search) (1/2) Backtracking 루트 노드(root node)를 먼저 방문한 뒤, 그 노드의 모든 후손노드(descendant)들을 차례로(보통 왼쪽에서 오른쪽으로) 방문한다. (= preorder tree traversal). void depth_first_tree_search(node v) { node u; visit v; for (each child u of v) // from left to right depth_first_tree_search(u) }

깊이우선검색 (Depth-first search) (2/2) Backtracking 예제

4개의 Queen을 서로 상대방을 위협하지 않도록 4  4 서양장기(chess)판에 위치시키는 문제이다. 4-Queens Problem (1/2) Backtracking 4개의 Queen을 서로 상대방을 위협하지 않도록 4  4 서양장기(chess)판에 위치시키는 문제이다. 서로 상대방을 위협하지 않기 위해서는 같은 행이나, 같은 열이나, 같은 대각선 상에 위치하지 않아야 한다. 무작정 알고리즘 각 Queen을 각각 다른 행에 할당한 후에, 어떤 열에 위치하면 해답은 얻을 수 있는지를 차례대로 점검해 보면 된다. 이때, 각 Queen은 4개의 열 중에서 한 열에 위치할 수 있기 때문에, 해답을 얻기 위해서 점검해 보아야 하는 모든 경우의 수는 4  4  4  4 = 256가지가 된다.

4-Queens Problem (2/2) 무슨 말인고 하니… 4  4  4  4 = 256가지 Backtracking 무슨 말인고 하니… 첫째 행에 올 수 있는 경우의 수 = 4 둘째 행에 올 수 있는 경우의 수 = 4 셋째 행에 올 수 있는 경우의 수 = 4 넷째 행에 올 수 있는 경우의 수 = 4 4  4  4  4 = 256가지

상태공간트리: State Space Tree 4-Queens 문제의 상태공간트리 Backtracking 상태공간트리: State Space Tree

상태공간트리의 이용 Backtracking 루트 노드에서 리프 노드(leaf node)까지의 경로는 해답후보(candidate solution)가 되는데, 깊이우선검색을 하여 그 해답후보 중에서 해답을 찾을 수 있다. 그러나 이 방법을 사용하면 해답이 될 가능성이 전혀 없는 노드의 후손노드(descendant)들도 모두 검색해야 하므로 비효율적이다.

상태공간트리의 이용 노드의 유망성(promising): 되추적이란? Backtracking 노드의 유망성(promising): 전혀 해답이 나올 가능성이 없는 노드는 유망하지 않다(non-promising)고 하고(해당 노드의 서브트리 검색은 무의미), 그렇지 않으면 유망하다(promising)고 한다. 되추적이란? 어떤 노드의 유망성을 점검한 후, 유망하지 않다고 판정이 되면 그 노드의 부모노드(parent)로 돌아간다(“backtrack”). 그런 다음, 다시 후손노드에 대한 검색을 계속하게 되는 절차이다.

되추적 알고리즘의 개념 되추적 알고리즘은 상태공간트리에서 깊이우선검색을 실시하는데, Backtracking 되추적 알고리즘은 상태공간트리에서 깊이우선검색을 실시하는데, 유망하지 않은 노드들은 가지쳐서(pruning) 검색을 하지 않으며, 유망한 노드에 대해서만 그 노드의 자식노드(children)를 검색한다. 이 알고리즘은 다음과 같은 절차로 진행된다. 1. 상태공간트리의 깊이우선검색을 실시한다. 2. 각 노드가 유망한지를 점검한다. 3. 만일 그 노드가 유망하지 않으면, 그 노드의 부모노드로 돌아가서 검색을 계속한다.

void checknode(node v) { if (promising(v)) 일반적인 되추적 알고리즘 Backtracking void checknode(node v) { if (promising(v)) if (there is a solution at v) write the solution; else for (each child u of v) checknode(u); }

4-Queens 문제의 되추적 상태공간트리 (1/2) Backtracking

4-Queens 문제의 되추적 상태공간트리 (2/2) Backtracking

깊이우선검색 vs. 되추적 검색하는 노드 개수의 비교 순수한 깊이우선검색 = 155 노드 되추적 = 27 노드 Backtracking 검색하는 노드 개수의 비교 순수한 깊이우선검색 = 155 노드 되추적 = 27 노드

4-Queens 문제: 개선된 되추적 알고리즘 Backtracking void expand(node v) { for (each child u of v) if (there is a solution at u) write the solution; else expand(u); } 개선된 알고리즘은 유망성 여부의 점검을 노드를 방문하기 전에 실시하므로, 그만큼 방문할 노드의 수가 적어져서 더 효율적이다. 그러나 일반 알고리즘이 이해하기는 더 쉽고, 일반 알고리즘을 개량된 알고리즘으로 변환하기는 간단하다. 따라서, 앞으로 이 강의에서의 모든 되추적 알고리즘은 일반 알고리즘과 같은 형태로 표시한다.

되추적 기술 n-Queens Problem Monte Carlo Technique Graph Coloring 강의 순서 Backtracking 되추적 기술 n-Queens Problem Monte Carlo Technique Graph Coloring Hamiltonian Circuits

n개의 Queen을 서로 상대방을 위협하지 않도록 n  n 서양장기(chess) 판에 위치시키는 문제이다. n-Queens Problem – 개요 Backtracking n개의 Queen을 서로 상대방을 위협하지 않도록 n  n 서양장기(chess) 판에 위치시키는 문제이다. 서로 상대방을 위협하지 않기 위해서는 같은 행이나, 같은 열이나, 같은 대각선 상에 위치하지 않아야 한다. n-Queens 문제의 되추적 알고리즘:  4-Queens 문제를 n-Queens 문제로 확장 시키면 된다.

n-Queens Problem – 알고리즘 (1/3) Backtracking 유망함수 구현을 위해, col[i]가 i-번째 행에서 Queen이 놓여있는 열이라 하자. 먼저, 같은 열에 있는지 검사하기 위해서는 col[i] = col[k]이 성립하는지 검사하면 된다. 다음으로, 같은 대각선에 있는지 검사하기 위해서는 다음 등식이 성립하는지 검사하면 된다. |col[i] – col[k]| = |i – k|

n-Queens Problem – 알고리즘 (2/3) Backtracking A Backtracking Algorithm for the n-Queens Problem void queens(index i) { index j; if(promising(i)) if(i == n) cout << col[1] through col[n]; else for(j=0;j <= n;j++) { col[i+1] = j; // 다음 위치 선택 queens(i+1); } 최상위 수준 호출: queens(0);

n-Queens Problem – 알고리즘 (3/3) Backtracking A Backtracking Algorithm for the n-Queens Problem (계속) bool promising(index i) { index k = 1; bool switch = true; while(k < i && switch) { if(col[i] == col[k] || |col[i]-col[k]| == i-k) swicth = false; k++; } return switch;

n-Queens Problem – 분석 1 (1/2) Backtracking 상태공간트리 전체에 있는 노드의 수를 구함으로서, 가지 친 상태공간트리의 노드의 개수의 상한을 구한다. 깊이가 i인 노드의 개수는 ni개 이고, 이 트리의 깊이는 n이므로, 노드의 총 개수는 상한(upper bound)은 다음과 같다. Recall

n-Queens Problem – 분석 1 (2/2) Backtracking 따라서 n = 8일 때, 로 계산된다. 그러나 이 분석은 별 가치가 없다. 왜냐하면 되추적함으로서 점검하는 노드 수를 줄이게 되기 때문이다. 즉, 되추적을 통해 점검 노드 수를 얼마나 줄였는지는 상한값을 구해서는 전혀 알 수 없기 때문이다.

n-Queens Problem – 분석 2 유망한 노드만 세어서 상한을 구한다. Backtracking 유망한 노드만 세어서 상한을 구한다. 이 값을 구하기 위해서는 어떤 두 개의 Queen이 동일한 열에 위치할 수 없다는 사실을 이용하면 된다. 예를 들어 n = 8일 경우를 생각해 보자. 첫 번째 Queen은 어떤 열에도 위치시킬 수 있다. 두 번째는 기껏해야 남은 7열 중에서만 위치시킬 수 있다. 세 번째는 남은 6열 중에서 위치시킬 수 있다. 이런 식으로 계속했을 경우 노드의 수는 1 + 8 + 8  7 + 8  7  6 + …+ 8! = 109,601가 된다. 이 결과를 일반화 하면 유망한 노드의 수의 하한은 다음과 같다.

n-Queens Problem – Discussion Backtracking 앞서의 두 가지 분석 방법은 알고리즘의 복잡도를 정확히 얘기 해주지 못하고 있다. 왜냐하면: 대각선을 점검하는 경우를 고려하지 않았다. 따라서 실제 유망한 노드의 수는 훨씬 더 작을 수 있다. 유망하지 않은 노드를 포함하고 있는데, 실제로 해석의 결과에 포함된 노드 중에서 유망하지 않은 노드가 훨씬 더 많을 수 있다. (이는 우리가 expand() 대신에 checknode()를 사용하여 알고리즘을 작성했기 때문이다. 이는 expand()를 사용하여 작성하면 해결할 수 있다.)

n-Queens Problem – 분석 3 Backtracking 유망한 노드의 개수를 정확하게 구하기 위한 유일한 방법은 실제로 알고리즘을 수행하여 구축된 상태공간트리의 노드의 개수를 세어보는 수 밖에 없다. 그러나 이 방법은 진정한 분석 방법이 될 수 없다. 왜냐하면 분석은 알고리즘을 실제로 수행하지 않고 이루어져야 하기 때문이다. (또한, 입력 개수 n은 매번 달라질 수 있기 때문이다.) 그럼, 정확한 분석은 어떻게 하나?  Monte Carlo Technique (확률적 알고리즘)

n-Queens Problem – 알고리즘의 수행 시간 비교 Backtracking 되추적 없이 상태공간트리를 깊이우선검색으로 모든 노드를 검색하는 알고리즘 두 개의 Queen은 같은 행이나 같은 열에 올 수 없다는 제한만을 이용한 알고리즘 제안한 되추적 알고리즘 (같은 행, 열, 대각선에 올 수 없다는 제한을 이용) checknode() 대신 expand()를 사용하여 유망노드 검색을 먼저 하는 알고리즘

되추적 기술 n-Queens Problem Monte Carlo Technique Graph Coloring 강의 순서 Backtracking 되추적 기술 n-Queens Problem Monte Carlo Technique Graph Coloring Hamiltonian Circuits

Monte Carlo Technique? Backtracking Monte Carlo 기법은 어떤 입력이 주어졌을 때 점검하게 되는 상태공간트리의 “전형적인” 경로를 무작위(random)로 생성하여 그 경로 상에 있는 노드의 수를 센다. 상기 과정을 여러 번 반복하여 나오는 결과의 평균치를 추정치로 한다. ( 확률적 복잡도를 구한다.) 이 기법을 적용하기 위해서는 다음 두 조건을 만족하여야 한다. 상태공간트리의 같은 수준(level)에 있는 모든 노드의 유망성 여부를 점검하는 절차는 같아야 한다. 상태공간트리의 같은 수준에 있는 모든 노드는 반드시 같은 수의 자식노드를 가지고 있어야 한다. n-Queens 문제는 위 두 조건을 모두 만족한다.

Monte Carlo Technique – nQueens (1/4) Backtracking 1. 루트 노드의 유망한 자식노드의 개수를 m0라고 한다. 2. 상태공간트리의 수준 1에서 유망한 노드를 하나 랜덤하게 정하고, 이 노드의 유망한 자식노드의 개수를 m1이라고 한다. 3. 위에서 정한 노드의 유망한 노드를 하나 랜덤하게 정하고, 이 노드의 유망한 자식노드의 개수를 m2라고 한다. 4. … 5. 더 이상 유망한 자식노드가 없을 때까지 이 과정을 반복한다. mi = 수준 i에 있는 노드의 유망한 자식노드의 개수의 평균의 추정치 ti = 수준 i에 있는 한 노드의 자식노드의 총 개수(유망하지 않은 노드도 포함) 되추적 알고리즘에 의해서 점검한 노드의 총 개수의 추정치는 다음과 같다.

Monte Carlo Technique – nQueens (2/4) Backtracking 그런데… ti는 정해진 값이라 해도, mi는 어떻게 구하나?  실제 알고리즘을 수행하면서 카운트한다. 과정을 간략히 기술하면 다음과 같다. 루트 수준에서 리프 수준까지 내려가면서 mi의 추정치를 구한다. 이를 위해, 각 수준에서 하나의 노드들 임의로 선택한다. 선택한 노드의 자식 노드들을 대상으로 유망 노드가 되는 비율을 구하여 mi로 삼는다. 상기 과정을 여러 번(경험적으로 20여 번 정도) 반복하여 mi값의 신뢰도를 높인다.

Monte Carlo Technique – nQueens (3/4) Backtracking Generic Backtracking Algorithm의 효율 추정 알고리즘 int estimate() { node v; int m, mprod, t, numnodes; v = 상태공간트리의 루트; numnodes = 1; m = 1; mprod = 1; while(m != 0) { t = v의 자식노드의 개수; mprod = mprod * m; numnodes = numnodes + mprod * t; m = v의 유망한 자식노드의 개수; if(m != 0) v = 무작위로 선택한 v의 자식노드; } return numnodes;

Monte Carlo Technique – nQueens (4/4) Backtracking n-Queens Algorithm의 효율 추정 알고리즘 int estimate_nqueens(int n) { index i, j, col[1..n]; int m, mprod, t, numnodes; set_of_index prom_children; i = 0; numnodes = m = mprod = 1; while(m != 0 && i != n) { mprod = mprod * m; numnodes = numnodes + mprod * t; i++; m = prom_children = 0; for(j=1;j <= n;j++) { col[i] = j; if(promising(i)) { m++; prom_children = prom_children  {j}; } if(m != 0) j = prom_children에서 무작위로 선택한 인덱스; return numnodes;

되추적 기술 n-Queens Problem Monte Carlo Technique Graph Coloring 강의 순서 Backtracking 되추적 기술 n-Queens Problem Monte Carlo Technique Graph Coloring Hamiltonian Circuits

Graph Coloring? 지도에 m가지 색으로 색칠하는 문제 이 그래프에서 두 가지 색으로 문제를 풀기는 불가능하다. Backtracking 지도에 m가지 색으로 색칠하는 문제 m개의 색을 가지고, 인접한 지역이 같은 색이 되지 않도록 지도에 색칠하는 문제 이 그래프에서 두 가지 색으로 문제를 풀기는 불가능하다. 세 가지 색을 사용하면 총 여섯 개의 해답을 얻을 수 있다.

평면 상에서 이음선(edge)들이 서로 엇갈리지 않게 그릴 수 있는 그래프. 평면 그래프 (Planar Graph) Backtracking 평면 상에서 이음선(edge)들이 서로 엇갈리지 않게 그릴 수 있는 그래프. 지도에서 각 지역을 그래프의 정점으로 하고, 한 지역이 어떤 다른 지역과 인접해 있으면 그 지역들을 나타내는 정점들 사이에 이음선을 그으면, 모든 지도는 그에 상응하는 평면그래프로 표시할 수 있다

지도와 평면 그래프 Backtracking

Graph Coloring – Backtracking

Graph Coloring – Algorithm (1/2) Backtracking A Backtracking Algorithm for the Graph Coloring Problem 입력: n – 정점의 수, m – 색깔의 수, W[i][j] – 이음선 있으면 true, 그렇지 않으면 false 출력: vcolor[i] - i번째 정점에 할당된 색(1 ~ m)이다. void m_coloring(index i) { index color; if(promising(i)) if(i == n) cout << vcolor[1] through vcolor[n]; else for(color=0;color <= m;color++) { vcolor[i+1] = color; // 다음 정점에 모든 색을 시도해 본다. m_coloring(i+1); } 최상위 수준 호출: m_coloring(0);

Graph Coloring – Algorithm (2/2) Backtracking A Backtracking Algorithm for the Graph Coloring Problem (계속) bool promising(index i) { index j = 1; bool switch = true; while(j < i && switch) { if(W[i][j] && vcolor[i] == vcolor[j]) swicth = false; j++; } return switch; 모든 vertex에 대해 “인접하고, 색이 같은지”의 여부를 조사한다.

상태공간트리 상의 노드 수에 대한 상한은 다음과 같다. Graph Coloring – 분석 Backtracking 상태공간트리 상의 노드 수에 대한 상한은 다음과 같다. 마찬가지로, Monte Carlo 기법을 사용하여, 실제 수행시간을 추정할 수 있다.

되추적 기술 n-Queens Problem Monte Carlo Technique Graph Coloring 강의 순서 Backtracking 되추적 기술 n-Queens Problem Monte Carlo Technique Graph Coloring Hamiltonian Circuits

Hamiltonian Circuits (1/2) Backtracking 연결된 비방향성 그래프에서, 해밀토니안 회로(Hamiltonian Circuits)/일주여행경로(tour)는 어떤 한 노드에서 출발하여 그래프 상의 각 정점을 한번씩 만 경유하여 다시 출발한 정점으로 돌아오는 경로이다.

Hamiltonian Circuits (2/2) Backtracking 해밀토니안 회로 문제: 연결된 비방향성 그래프에서 해밀토니안 회로를 결정하는 문제 되추적 방법을 적용하기 위해서 다음 사항을 고려해야 한다. 경로 상의 i번째 정점은 그 경로 상의 (i - 1)번째 정점과 반드시 이웃 해야 한다. (n - 1)번째 정점은 반드시 0번째 정점(출발점)과 이웃해야 한다. i번째 정점은 그 앞에 오는 i - 1개의 정점이 될 수 없다.

Hamiltonian Circuits – Algorithm (1/2) Backtracking A Backtracking Algorithm 입력: n – 정점의 수, W[i][j] – 이음선 있으면 true, 그렇지 않으면 false 출력: vindex[i] – 경로상에서 i번째 정점의 인덱스 void hamiltonian(index i) { index j; if(promising(i)) if(i == n-1) cout << vindex[0] through vindex[n-1]; else for(j=2;j <= n;j++) { // 모든 정점의 다음 정점을 vcolor[i+1] = j; // 시도해 본다. hamiltonian(i+1); } 최상위 수준 호출: vindex[0] = 1; hamiltonian(0);

Hamiltonian Circuits – Algorithm (2/2) Backtracking A Backtracking Algorithm (계속) bool promising(index i) { index j=1; bool switch = true; if(i == n-1 && !W[vindex[n-1]][vindex[0]]) switch = false; // 첫번째 정점은 마지막 정점과 else if(i > 0 && !W[vindex[i-1]][vindex[i]]) switch = false; // 인접해야 하고, i번째 정점은 else { // (i-1)번째 정점과 인접해야 한다. while(j < i && switch) { if(vindex[i] == vindex[j]) // 정점이 이미 선택되었는지 swicth = false; // 검사한다. j++; } return switch;

Hamiltonian Circuits – 분석 Backtracking 해밀토니안 회로 문제에서 상태공간트리 상의 노드 수(의 상한)는 다음과 같다. 마찬가지로, Monte Carlo 기법을 사용하여, 실제 수행시간을 추정할 수 있다.