[CPA340] Algorithms and Practice Youn-Hee Han http://link.kut.ac.kr Ch.05 Backtracking (되추적) [CPA340] Algorithms and Practice Youn-Hee Han http://link.kut.ac.kr

Tree Tree consists of A finite set of nodes (vertices) A finite set of branches (edges, arcs) that connects the nodes Degree of a node: # of branches In-degree: # of branch toward the node (# of upward branch) Out-degree: # of branch away from the node (# of downward branch) Every non-empty tree has a root node whose in-degree is zero. In-degree of all other nodes except the root node is one.

Tree Terminology A node is a structure which may contain a value or condition A node is child of its predecessor E and F are child nodes of B A node is parent of its successor nodes B is the parent node of E and F A is the parent node of B, C, and D A descendant node of any node A is any node below A in a tree, where "below" means "away from the root." B, E, F, C, and D are descendant nodes of A An ancestor node of any node A is any node above A in a tree, where "above" means "toward the root." B and A are ancestor nodes of F Path a sequence of nodes in which each node is adjacent to the next one

Tree Terminology A sibling node of A is a node with the same parent as A B, C, and D are sibling nodes each other E and F are sibling nodes each other A leaf (or terminal) node is a node who hos no child nodes C, D, E, E are leaf nodes Node with out-degree zero

Subtree B can be divided into two subtrees, C and D Terminology A subtree of a tree T is a tree consisting of a node in T and all of its descendants in T each node corresponds to the subtree of itself and all its descendants each node is the root node of the subtree it determines the subtree corresponding to the root node is the entire tree Subtree B can be divided into two subtrees, C and D

Tree Recursive Definitions of Tree A tree is a set of nodes that either: 1. is Empty, or 2. has a designated node, called the root, from which hierarchically descend zero or more subtrees, which are also trees. Binary tree is a tree in which no node can have more than two subtrees the child nodes are called left and right Left/right subtrees are also binary trees

Tree Traversal Tree Traversal process each node once and only once in a predetermined sequence Two general approach Depth-first traversal (depth-first search: DFS) Breadth-first traversal (breadth-first search: BFS, level-order) 1 4 6 2 5 7 3 1 5 6 2 3 7 4 depth-first traversal breadth-first traversal

Tree Traversal Depth-first traversal proceeds along a path from the root to the most distant descendent of that first child before processing a second child. Page 8

Tree Traversal 3 types of depth-first traversal in Binary Tree Preorder traversal A node  left subtree  right subtree Inorder traversal Left subtree  a node  right subtree Postorder traversal Left subtree  right subtree  a node

Tree Traversal Preordered depth-first traversal Root  all subtrees of the node When the function is returned, “backtracking” start void depth_first_tree_search(node v){ node u; visit v; // or process v for (each child u of v) // from left to right depth_first_tree_search(u) } Page 10

Tree Traversal Breadth-first traversal (=level-order traversal) Begins at the root node and explores all the neighboring nodes Then for each of those nearest nodes, it explores their unexplored neighbor nodes, and so on, until it finds the goal  Attempts to visit the node, not already visited, closest to the root

되추적(backtracking)? 갈림길에 표시를 해 두었더라면…  간단히 말해서 되추적은 갈림길에 표시를 해 두고 막다른 골목에 다다르면 갈림길까지 되돌아가서 다른 골목으로 가보는 방법이다.

되추적의 개요 Backtracking 은 제약조건 만족 문제 (Constraint Satisfaction Problem) 에서 해를 찾기 위한 전략 중 하나이다. Backtracking 은 올바른 답을 구할 때까지 각각의 가능성을 시도한다. 해를 찾기 위한 깊이우선 탐색 (Depth First Search) 과 관련성이 깊다. 탐색도중에, 새로운 탐색이 무의미하다고 판단되면, 다른 새로운 탐색이 가능한 선택 포인트 (choice point) 로 backtrack 하여 새로운 탐색을 시도하게 된다. 더 이상의 선택 포인트가 존재하지 않게되면, 탐색은 실패로 끝난다

n-Queens 문제 n-Queens 문제: 4-Queens 문제: n×n 서양장기판(chess) 에 배치되는 n개의 Queen들이 서로 위협하지 않도록 배치하는 문제 기준: 어떤 두 Queen도 서로를 위협하지 않아야 한다. 같은 행이나, 같은 열이나, 같은 대각선 상에 위치하지 않아야 한다. 4-Queens 문제: 4개의 Queen을 서로 상대방을 위협하지 않도록 4  4 서양장기(chess)판에 위치시키는 문제

무작정 알고리즘으로 구현할 때 고려해야 할 Candidate Solution 개수 n-Queens 문제 4-Queens 문제: 첫째 행에 올 수 있는 경우의 수 = 4 둘째 행에 올 수 있는 경우의 수 = 4 셋째 행에 올 수 있는 경우의 수 = 4 넷째 행에 올 수 있는 경우의 수 = 4 4  4  4  4 = 256가지 무작정 알고리즘으로 구현할 때 고려해야 할 Candidate Solution 개수

4-Queens 문제의 상태공간트리 상태공간트리: State Space Tree (i,j)  i번째 queen 이 j번째 열에… 첫 번째 queen이 놓일 수 있는 곳 두 번째 queen이 놓일 수 있는 곳 세 번째 queen이 놓일 수 있는 곳 네 번째 queen이 놓일 수 있는 곳 후보답: Candidate Solution

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

상태공간트리의 이용 노드의 유망성(promising): 전혀 해답이 나올 가능성이 없는 노드는 유망하지 않다 (non-promising)고 하고 (해당 노드의 서브트리 검색은 무의미), 그렇지 않으면 유망하다(promising)고 한다.

상태공간트리의 이용 되추적이란? 되추적 알고리즘은 상태공간트리에서 깊이우선검색을 실시하는데, 어떤 노드의 유망성을 점검한 후, 유망하지 않다고 판정이 되면 (그 노드의 후손 노드(서브 트리)들에 대한 검색을 중지하고, 그 노드의 부모노드(parent)로 돌아간다(“backtrack”). 그런 다음, 다시 후손 노드에 대한 검색을 계속하게 되는 절차이다. 되추적 알고리즘은 상태공간트리에서 깊이우선검색을 실시하는데, 유망하지 않은 노드들은 가지쳐서(pruning) 검색을 하지 않으며, 유망한 노드에 대해서만 그 노드의 자식노드를 검색한다.

되추적 알고리즘의 개념 [Summary] 되추적 알고리즘의 절차 1. 상태공간트리의 깊이우선검색을 실시한다. 1. 상태공간트리의 깊이우선검색을 실시한다. 2. 각 노드가 유망한지를 점검한다. 3. 만일 그 노드가 유망하지 않으면, 가지치기를 수행하고, 그 노드의 부모노드로 돌아가서 검색을 계속한다. void checknode(node v){ node u; if (promising(v)) // 각 응용마다 promising 함수는 다르다. if (there is a solution at v) write the solution; else for (each child u of v) checknode(u); } [Note] 실제 트리를 만들어 알고리즘을 수행할 필요는 없다. 즉, 상태공간트리는 묵시적으로(implicitly) 존재한다.

4-Queens 문제의 되추적 상태공간트리 (1/2) 순수한 깊이우선검색의 검색 노드 수 = 155 노드 (전체는 (1+4+16+64+256)개이나, 그 이전에 솔루션(2-4-1-3)이 찾아지므로…) 되추적방법에 의한 검색 노드 수 = 27 노드

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

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

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

n-Queens Problem – 알고리즘 (2/3) A Backtracking Algorithm for the n-Queens Problem 최상위 수준 호출: queens(0); void checknode(node v){ node u; if (promising(v)) if (there is a solution at v) write the solution; else for (each child u of v) checknode(u); } void queens(index i){ index j; if(promising(i)) if(i == n) System.out.print(col[1] through col[n]); else for(j=1 ; j <= n ; j++) { col[i+1] = j; // 다음 위치 선택 queens(i+1); }

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

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

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

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

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

n-Queens Problem – 분석 3 유망한 노드의 개수를 정확하게 구하기 위한 유일한 방법은 실제로 알고리즘을 수행하여 구축된 상태공간트리의 노드의 개수를 세어보는 수 밖에 없다.

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

n-Queens Problem – 분석 4 그러나 이 방법은 진정한 분석 방법이 될 수 없다. 왜냐하면 분석은 알고리즘을 실제로 수행하지 않고 이루어져야 하기 때문이다. (모든 입력 개수 n에 대해 앞에 있는 표를 만들 수는 없다.) 그럼, 정확한 분석은 어떻게 하나?  Monte Carlo Technique (확률적 알고리즘)

Monte Carlo Technique? Monte Carlo 기법은 어떤 입력이 주어졌을 때 점검하게 되는 상태공간트리의 “전형적인” 경로를 무작위(random)로 생성하여 그 경로 상에서 검사하게 되는 시뮬레이션 기법 상기 과정을 여러 번 반복하여 나오는 결과의 평균치를 추정치로 사용한다. ( 확률적 복잡도를 구한다.) 대학원 과정에서 심도있게 배울 수 있음 [Note]Monte Carlo: 모나코의 유명한 도박의 도시