[알고리즘] 되추적 알고리즘, Backtracking

  backtracking은 깊이우선탐색(DFS) 방식으로 상태공간트리를 탐색하는 알고리즘으로, 최적화 문제를 해결하는데에 사용될 수 있다.  backtracking의 진행절차는 다음과 같다.

 

<backtracking 진행절차>

① 상태공간트리의 깊이우선검색(DFS)을 실시

② 각 노드가 유망(promising)한지 점검

③ 유망하지 않은 노드들은 더 이상 검색하지 않고 그 노드의 부모노드로 돌아가서 검색을 계속(pruning), 유망한 노드들은 그 노드의 자식노드를 검색

 

  여기서 promising, 즉 유망하다는 것은 더 내려다볼 가치가 있다는 것이고 반대로 유망하지 않다(non-promising)는 것은 전혀 해답이 나올 가능성이 없다는 것을 의미한다. 유망하지 않으면 그 자식노드에 대한 탐색을 중단하고 부모노드로 돌아가는데, 이를 '가지친다(pruning)'라고 한다.

 

깊이우선탐색(DFS) 방식으로 트리를 탐색하는 알고리즘의 수도코드는 아래와 같다.

 

void depth_first_tree_search (node v) { //node v를 방문
  node u;
  visit v;
  for(each child u of v) //v에게 자식이 있다면
    depth_first_tree_search(u) //재귀
}

 

  이처럼 자식이 있다면 바로 그 자식을 방문하는 방식으로 자식이 없을 때까지 재귀를 반복한다. 이를 상태공간트리에서 보았을 때 자식이 없을 때 까지 계속 아래로 방문하므로 이를 '깊이우선탐색'이라고한다.

 

  이번에는 위의 깊이우선탐색(DFS) 방식을 적용한 backtracking 알고리즘의 수도코드를 보자.

 

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); //재귀
}

 

  이처럼 backtracking 알고리즘은 방문하는 모든 노드마다 유망한지 검사하고 유망하지 않을 경우 자식노드를 방문하지 않는다. 또한 당연한 말이지만, 유망하더라도 자식이 없는 경우에도 더이상 자식을 방문하지않는다.

 

  단순히 깊이우선탐색을 통해 해답을 찾는 것 보다, 상태가 유망한지 그렇지 않은지를 판단하여 가지치기를 해가면서 해답을 찾는 것이 검색횟수를 현저히 줄여준다.  backtracking 문제를 풀기 위해 결정되어야 할 사항들이 있다.

 

<backtracking 문제를 풀기 위해 결정되어야 할 사항>

① 상태공간트리의 구조를 결정

② 유망한지 유망하지 않은지를 따질 조건을 결정. 즉, 유망함의 기준을 설정 (promising function)

 

  상태공간트리의 구조를 결정한다고 하면 그게 뭔지 잘 와닿지 않을 수 있는데, 예를 들면 어떤 값을 기준으로 자식과 부모 노드를 구성할지에 대한 것이 이에 해당한다. 또한 위에서 되추적 알고리즘의 절차 중 각 노드가 유망한지 점검하는 절차가 있었는데, 이를 수행하기 위해서는 무엇이 유망한 것인지에 대한 기준이 있어야 한다. 이런 노드의 유망성을 검사하는 함수를 promising function이라고 한다.

 

  이러한 backtracking을 적용할 수 있는 문제들로는 n-Queens Problem, Monte Carlo Algorithm,  Sum-of-subsets Problem, Graph Coloring, The Hamiltonian Circuits Problem, The 0-1 Knapsack Problem 등이 있다. 이번 카테고리에서 이 문제들을 하나씩 다뤄볼 예정이다.