알고리즘 (Algorithm) g( 되추적 ) 2011년봄학기 강원대학교컴퓨터과학전공문양세
되추적 (backtracking)? 갈림길에표시를해두었더라면 간단히말해서되추적은갈림길에표시를해두는기법이다. Page 2
강의순서 되추적기술 n-queens Problem Monte Carlo Technique Graph Coloring Hamiltonian Circuits Page 3
깊이우선검색 (Depth-first search) (1/2) 루트노드 (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) tree search(u) Page 4
깊이우선검색 (Depth-first search) (2/2) 예제 Page 5
4-Queens Problem (1/2) 4 개의 Queen 을서로상대방을위협하지않도록 4 4 서양장 기 (chess) 판에위치시키는문제이다. 서로상대방을위협하지않기위해서는같은행이나, 같은열 이나, 같은대각선상에위치하지않아야한다. ( 다음페이지 ) 무작정알고리즘 각 Queen 을각각다른행에할당한후에, 어떤열에위치하면해답은 얻을수있는지를차례대로점검해보면된다. 이때, 각 Queen 은 4 개의열중에서한열에위치할수있기때문에, 해답을얻기위해서점검해보아야하는모든경우의수는 4 4 4 4 = 256 가지가된다. Page 6
4-Queens Problem (2/2) 무슨말인고하니 첫째행에올수있는경우의수 = 4 둘째행에올수있는경우의수 = 4 셋째행에올수있는경우의수 = 4 넷째행에올수있는경우의수 = 4 Page 7 4 4 4 4 = 256 가지
4-Queens 문제의상태공간트리 상태공간트리 : State Space Tree i 번째말이 j 번째열에 Page 8
상태공간트리의이용 루트노드에서리프노드 (leaf node) 까지의경로는해답후보 (candidate solution) 가되는데, 깊이우선검색을하여그해답 후보중에서해답을찾을수있다. 그러나이방법을사용하면해답이될가능성이전혀없는노 드의후손노드 (descendant) 들도모두검색해야하므로비효 율적이다. Page 9
상태공간트리의이용 노드의유망성 (promising): 전혀해답이나올가능성이없는노드는유망하지않다 (non-promising) 고하고 ( 해당노드의서브트리검색은무의미 ), 그렇지않으면유망하다 (promising) 고한다. 되추적이란? 어떤노드의유망성을점검한후, 유망하지않다고판정이되면 ( 그노드의후손노드 ( 서브트리 ) 들에대한검색을중지하고, 그노드의부모노드 (parent) 로돌아간다 ( backtrack ) ). 그런다음, 다시후손노드에대한검색을계속하게되는절차이다. Page 10
되추적알고리즘의개념 되추적알고리즘은상태공간트리에서깊이우선검색을실시하는데, 유망하지않은노드들은가지쳐서 (pruning) 검색을하지않으며, 유망한노드에대해서만그노드의자식노드 (children) 를검색한다. 이알고리즘은다음과같은절차로진행된다. 1. 상태공간트리의깊이우선검색을실시한다. 2. 각노드가유망한지를점검한다. 3. 만일그노드가유망하지않으면, 가지치기를수행하고, 그노드의부모노드로돌아가서검색을계속한다. Page 11
일반적인되추적알고리즘 void checknode(node d v) { if (promising(v)) if (there is a solution at v) write the solution; else for (each child u of v) checknode(u); Page 12
4-Queens 문제의되추적상태공간트리 (1/2) Page 13
4-Queens 문제의되추적상태공간트리 (2/2) Page 14
깊이우선검색 vs. 되추적 검색하는노드개수의비교 순수한깊이우선검색 = 155 노드 ( 전체는 (1+4+16+64+256) 개이나, 그이전에솔루션 (2-4-1-3) 이찾아지므로 ) 되추적 = 27 노드 Page 15
4-Queens 문제 : 개선된되추적알고리즘 void expand(node v) { for (each child u of v) if (promising(u)) if (there is a solution at u) write the solution; else expand(u); 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); 개선된알고리즘은유망성여부의점검을노드를방문하기전에실시하므로, 그만큼방문할노드의수가적어져서더효율적이다. 그러나일반알고리즘이이해하기는더쉽고, 일반알고리즘을개량된알 고리즘으로변환하기는간단하다. 따라서, 앞으로이강의에서의모든되추적알고리즘은일반알고리즘과같은형태로표시한다. Page 16
강의순서 되추적기술 n-queens Problem Monte Carlo Technique Graph Coloring Hamiltonian Circuits Page 17
n-queens Problem 개요 n 개의 Queen 을서로상대방을위협하지않도록 n n 서양장 기 (chess) 판에위치시키는문제이다. 서로상대방을위협하지않기위해서는같은행이나, 같은열 이나, 같은대각선상에위치하지않아야한다. n-queens Q 문제의되추적알고리즘 : 4-Queens 문제를 n-queens 문제로확장시키면된다. Page 18
n-queens Problem 알고리즘 (1/3) 유망함수구현을위해, col[i] 가 i- 번째행에서 ( 즉, i- 번째 ) Queen 이 놓여있는열이라하자. 먼저, 같은열에있는지검사하기위해서는 col[i] = col[k] 이성립하 는지검사하면된다. 다음으로, 같은대각선에있는지검사하기위해서는다음등식이 성립하는지검사하면된다. col[i] col[k] = i k 열의차이 = 행의차이 Page 19
n-queens Problem 알고리즘 (2/3) A 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=1;j <= n;j++) { col[i+1] = j; // 다음위치선택 queens(i+1); 최상위수준호출 : queens(0); 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); Page 20
n-queens Problem 알고리즘 (3/3) A Algorithm for the n-queens Problem ( 계속 ) bool promising(index i) { index k = 1; bool switch = true; while(k < i && switch) { // k <= n if(col[i] == col[k] col[i]-col[k] == i-k ) swicth = false; k++; return switch; Page 21
n-queens Problem 분석 1 (1/2) 상태공간트리전체에있는노드의수를구함으로서, 가지친상태 공간트리의노드의개수의상한을구한다. 깊이가 i 인노드의개수는 n i 개이고, 이트리의깊이는 n 이므로, 노드의총개수는상한 (upper bound) 은다음과같다. 1 n 1 2 3 n n 1 n n n n n 1 Recall n i 0 i 2 3 n r 1 r r r r r n 1 1 r 1 Page 22
n-queens Problem 분석 1 (2/2) 9 8 1 19,173,961 따라서 n = 8일때, 로계산된다. 8 1 그러나이분석은별가치가없다. 왜냐하면되추적함으로서점검 하는노드수를줄이게되기때문이다. 즉, 되추적을통해점검노드수를얼마나줄였는지는상한값을구 해서는전혀알수없기때문이다. Page 23
n-queens Problem 분석 2 유망한노드만세어서상한을구한다. 이값을구하기위해서는어떤두개의 Queen 이동일한열에위치 할수없다는사실을이용하면된다. 예를들어 n = 8 일경우를생각해보자. 첫번째 Queen 은어떤열에도위치시킬수있다. 두번째는기껏해야남은 7 열중에서만위치시킬수있다. 세번째는남은 6 열중에서위치시킬수있다. 이런식으로계속했을경우노드의수는 1 + 8 + 8 7 + 8 7 6 + + 8! = 109,601가된다. ( 여기서 1 = root) 이결과를일반화하면유망한노드의수의하한은다음과같다. 1 n n( n 1) n( n 1)( n 2) n! Page 24
n-queens Problem Discussion 앞서의두가지분석방법은알고리즘의복잡도를정확히얘기해 주지못하고있다. 왜냐하면 : 대각선을점검하는경우를고려하지않았다. 따라서실제유망한노드의수는훨씬더작을수있다. 유망하지않은노드를포함하고있는데, 실제로해석의결과에포함된노드 중에서유망하지않은노드가훨씬더많을수있다. ( 이는우리가 checknode() 대신에 expand() 를사용하여알고리즘을작성했 기때문이다. 이는 expand() 를사용하여작성하면해결할수있다.) Page 25
n-queens Problem 분석 3 유망한노드의개수를정확하게구하기위한유일한방법은실제 로알고리즘을수행하여구축된상태공간트리의노드의개수를 세어보는수밖에없다. 그러나이방법은진정한분석방법이될수없다. 왜냐하면분석 은알고리즘을실제로수행하지않고이루어져야하기때문이다. ( 또한, 입력개수 n 은매번달라질수있기때문이다.) 그럼, 정확한분석은어떻게하나? Monte Carlo Technique ( 확률적알고리즘 ) Page 26
n-queens Problem 알고리즘의수행시간비교 되추적없이상태공간트리를깊이우선검색으로모든노드를검색하는알고리즘 두개의 Queen 은같은행이나같은열에올수없다는제한만을이용한알고리즘 제안한되추적알고리즘 ( 같은행, 열, 대각선에올수없다는제한을이용 ) checknode() 대신 expand() 를사용하여유망노드검색을먼저하는알고리즘 Page 27
강의순서 되추적기술 n-queens Problem Monte Carlo Technique Graph Coloring Hamiltonian Circuits Page 28
Monte Carlo Technique? Monte Carlo 기법은어떤입력이주어졌을때점검하게되는상태 공간트리의 전형적인 경로를무작위 (random) 로생성하여그 경로상에있는노드의수를센다. 상기과정을여러번반복하여나오는결과의평균치를추정치로 사용한다. ( 확률적복잡도를구한다.) 이기법을적용하기위해서는다음두조건을만족하여야한다. 상태공간트리의같은수준 (level) 에있는모든노드의유망성여부를 점검하는절차는같아야한다. 상태공간트리의같은수준에있는모든노드는반드시같은수의자 식노드를가지고있어야한다. n-queens 문제는위두조건을모두만족한다. Page 29
Monte Carlo Technique nqueens (1/4) 1. 루트노드의유망한자식노드의개수를 m 0 라고한다. 2. 상태공간트리의수준 1 에서유망한노드를하나랜덤하게정하고, 이노드의유망한자식노드개수를 m 1 이라고한다. 3. 위에서정한노드의유망한노드를하나랜덤하게정하고, 이노드의유망한자식노드의개수를 m 2 라고한다. 4. 5. 더이상유망한자식노드가없을때까지이과정을반복한다. m i = 수준 i 에있는노드의유망한자식노드개수의평균의추정치 t i = 수준 i 에있는한노드의자식노드의총개수 ( 유망하지않은노드도포함 ) 되추적알고리즘에의해서점검한노드의총개수의추정치는다음과같다. 1 t0 m0t1 m0m1t2 m0m1 mi 1ti Page 30
Monte Carlo Technique nqueens (2/4) 그런데 t i 는정해진값이라해도, m i 는어떻게구하나? 실제알고리즘을수행하면서카운트한다. 과정을간략히기술하면다음과같다. 루트수준에서리프수준까지내려가면서 m i 의추정치를구한다. 이를위해, 각수준에서하나의노드들임의로선택한다. 선택한노드의자식노드들을대상으로유망노드가되는비율을구 하여 m i 로삼는다. i 상기과정을여러번 ( 경험적으로 20 여번정도 ) 반복하여 m i 값의신 뢰도를높인다. Page 31
Monte Carlo Technique nqueens (3/4) - skip Generic Algorithm 의효율추정알고리즘 int estimate() { node v; int m, mprod, t, numnodes; // mprod = 각수준의 m 0 m 1...mm i-11 // m = 각수준의유망자식노드개수 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; // visit 할노드의추정치 Page 32
Monte Carlo Technique nqueens (4/4) - skip 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에서무작위로선택한인덱스 ; col[i] = j; return numnodes; Page 33
강의순서 되추적기술 n-queens Problem Monte Carlo Technique Graph Coloring Hamiltonian Circuits Page 34
Graph Coloring? 지도에 m 가지색으로색칠하는문제 m 개의색을가지고, 인접한지역이같은색이되지않도록지도에 색칠하는문제 이그래프에서두가지색으로문제를풀기는불가능하다. 세가지색을사용하면총여섯개의해답을얻을수있다. Page 35
평면그래프 (Planar Graph) 평면상에서이음선 (edge) 들이서로엇갈리지않게그릴수 있는그래프. 지도에서각지역을그래프의노드로하고, 한지역이어떤 다른지역과인접해있으면그지역들을나타내는노드들사 이에이음선을그으면, 모든지도는그에상응하는평면그래 프로표시할수있다. ( 다음페이지참조 ) Page 36
지도와평면그래프 Page 37
Graph Coloring 3-Coloring Page 38
Graph Coloring Algorithm (1/2) A 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=1;color <= m;color++) { vcolor[i+1] = color; // 다음노드에모든색을시도해본다. m_coloring(i+1); 최상위수준호출 : m_coloring(0); Page 39
Graph Coloring Algorithm (2/2) A 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 에대해 인접하고, 색이같은지 의여부를조사한다. Page 40
Graph Coloring 분석 상태공간트리상의노드수에대한상한은다음과같다. 1 m 1 2 m m 1 m m m m 1 마찬가지로, Monte Carlo 기법을사용하여, 실제수행시간을 추정할수있다. Page 41
강의순서 되추적기술 n-queens Problem Monte Carlo Technique Graph Coloring Hamiltonian Circuits Page 42
Hamiltonian Circuits (1/2) 연결된비방향성그래프에서, 해밀토니안회로 (Hamiltonian Circuits)/ 일주여행경로 (tour) 는어떤한노드에서출발하여 그래프상의각노드를한번씩만경유하여다시출발한노 드로돌아오는경로이다. Page 43
Hamiltonian Circuits (2/2) 해밀토니안회로문제 : 연결된비방향성그래프에서해밀토 니안회로를결정하는문제 되추적방법을적용하기위해서다음사항을고려해야한다. 경로상의 i번째노드는그경로상의 (i -1) 번째노드와반드시이웃해야한다. (n - 1) 번째노드는반드시 0 번째노드 ( 출발점 ) 와이웃해야한다. i 번째노드는그앞에오는 i - 1 개의노드가될수없다. Page 44
Hamiltonian Circuits Algorithm (1/2) A 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++) { // 모든노드의다음노드를 vindex[i+1] = j; // 시도해본다. hamiltonian(i+1); // j=2인이유 : 출발점은제외 최상위수준호출 : vindex[0] = 1; hamiltonian(0); Page 45
Hamiltonian Circuits Algorithm (2/2) A 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; Page 46
Hamiltonian Circuits 분석 해밀토니안회로문제에서상태공간트리상의노드수 ( 의상 한 ) 는다음과같다. n 2 ( n 1) ( n 1) 1 1 ( n 1) ( n 1) ( n 1) n 2 마찬가지로, Monte Carlo 기법을사용하여, 실제수행시간을 추정할수있다. Page 47