[Algorithm] Backtracking

백트래킹은 DFS를 기반으로 한 문제풀이방법이다.

DFS (Depth-First Search, Preorder Tree Traversal) 란?
뿌리가 되는 노드부터, 그 노드의 모든 후손노드를 차례로 방문하는것이다.

// DFS pseudo code
void depth_first_search(node v)
{
    node u;
    visit v;
    for (each child u of v)
        depth_first_search(u);
}

Backtracking 방법은, State Space Tree (상태 공간 트리)를 제작한다.

상태공간 트리의 유망하지 않은 가지를 pruning(가지치기) 하여, 모든 경우를 순회하지 않고 답을 찾을 수 있다.

Promising 이란?
- 이후 전혀 해답이 나올 가능성이 없는 노드를 Non-promising이라 한다.
- 그렇지 않은것을 promising이라 한다.

Backtracking 이란?
- 노드의 유망성을 점검한 후, 유망하지 않다고 판정되면 그 노드의 부모노드로 Backtrack하여 다음 후손노드에 대한 검색을 진행하는 방법이다.

// Backtracking pseudo code
void backtracking(node v)
{
    node u;
    if (promising(v))
        if(there is a solution at v)
            write the solution;
        else
            for (each child u of v)
                cheknode(u);
}

 

모든 조합의 수중에 최적의 경우를 구해야하는 문제에서 자주 쓰이는 해결방법이다.

다만 그 과정에서 pruning으로 최적화 할수 있다. 대표적으로 N-Queen 문제가 있다.