Backtracking(백트래킹)

Basic Concept

---

If you were trying to find your way through the well-known maze of hedges by Hampton Court Palace in England, you would have no choice but to follow a hopeless path until you reached a dead end. When that happened, you’d go back to a fork and pursue another path. Think how much easier it would be if there were a sign, positioned a short way down a path, that told you that the path led to nothing but dead ends. If the sign were positioned near the beginning of the path, the time savings could be enormous, because all forks after that sign would be eliminated from consideration. This means that not one but many dead ends would be avoided. There are no such signs in the famous maze of hedges or in most maze puzzles. However, as we shall see, they do exist in backtracking algorithms.

 

👉 백트래킹의 개념을 의미하는 미로그림이 챕터 앞부분에 실려있다. 미로 속에서 길을 찾다가 막다른 곳에 조우했다면 가장 최근의 갈림길로 돌아가 다른 길을 갈 것이다.

갈림길의 시작지점에 막힌 곳으로 가는 경로가 표시되어 있다면, 표지판 뒤에 있는 모든 분기점들을 고려대상에서 제외시키기 때문에 탐색시간을 엄청나게 절약할 수 있을 것이다. 백트래킹 알고리즘에는 그런 표시가 존재한다.

 

 

The Backtracking Technique

---

Backtracking is used to solve problems in which a sequence of objects is chosen from a specified set so that the sequence satisfies some criterion. Backtracking is a modified depth-first search of a tree. Although the depth-first search is defined for graphs in general, we will discuss only searching of trees, because backtracking involves only a tree search.

 

 

A preorder tree traversal is a depth-first search of the tree. This means that the root is visited first, and a visit to a node is followed immediately by visits to all descendants of the node. Although a depth-first search does not require that the children be visited in any particular order, we will visit the children of a node from left to right in the applications in this chapter. The nodes are numbered in the order in which they are visited.

Notice that in a depth-first search, a path is followed as deeply as possible until a dead end is reached. At a dead end we back up until we reach a node with an unvisited child, and then we again proceed to go as deep as possible.

 

👉 백트랙킹 기법은 지정된 집합(a specified set)에서 어떤 기준(creiterion)을 만족하면서 그 집합에 속한 대상의 순서(sequence)를 선택하는 문제를 푸는데 사용된다. 이 기법은 수정 된 깊이우선탐색(depth-first search)이다.

깊이우선탐색은 트리 방문방법 중 하나인 전위순회(preorder)와 같다. 루트가 되는 노드를 먼저 방문한 뒤, 그 노드의 모든 후손 노드들을 차례로(일반적으로 왼쪽에서 오른쪽) 방문한다.

깊이우선탐색에서의 방문경로는 더 이상 갈 수 없는 노드까지 내려간다. 그렇게 내려간 마지막 노드에서 다시 방문하지 않은 자식노드가 있는 노드로 되돌아가고, 거기서부터 다시 가능한 깊이까지 내려간다.

 

Pseudocode 

There is a simple recursive algorithm for doing a depth-first search. Because we are presently interested only in preorder traversals of trees, we give a version that specifically accomplishes this. The procedure is called by passing the root at the top level.

• Depth-first search

void depth_first_tree_search (node v)
{   
    node u;
    visit v;    
    for (each child u of v)     
        depth_first_tree_search(u)
}