1. BackTracking 이란?
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은 modified depth-first-search(DFS)입니다.
일반적인 DFS와는 다르게 조금 변형된 구조를 가지고 있습니다.
지금은 Backtracking은 변형된 DFS라고 생각하고 preorder tree traversal을 한다고만 알고 있으면 될 것 같습니다.
Backtracking은 n-Queens 문제를 푸는 데 사용됩니다.
n-Queens 문제는 nxn 크기의 체스판에 n개의 퀸을 나누는데, 모든 퀸이 서로 다른 퀸을 잡아먹을 수 없게 하는 문제입니다.
이 문제에서 순서는 여왕을 두는 n개의 위치이고, 특정 집합은 여왕을 놓을 수 있는 n^2의 칸, 기준은 서로가 서로를 잡아먹을 수 없어야 한다는 것입니다.
2. State Space Tree(상태 공간 트리)
n = 4 일 때, Backtracking으로 문제를 풀어봅시다. 4x4 체스판에 4개의 여왕을 나눠야 합니다.
우선 우리는 아주 간단하게 같은 행에 두 여왕을 놓을 수 없다 라는 사실을 알 수 있습니다.
따라서 모든 여왕은 각각 다른 행에 넣는다는 가정하에, 한 행마다 4개의 열을 선택할 수 있으므로, 4 x 4 x 4 x 4 = 256의 candidate solution(해답 후보)가 나옵니다.
이때 우리는 문제를 조금 더 간단히 풀기 위해서 state space tree라는 가상의 트리를 만듭니다.
이 state space tree는 해결을 위한 탐색 공간이고, 탐색 공간을 트리 구조로 Implicitly(암묵적)으로 해석합니다.
root는 level-0이고, 1행에 놓는 여왕은 트리의 level-1에 해당한다고 가정한다면, tree는 level-4까지 존재하게 됩니다.
하나의 level에는 열에 해당하는 노드가 4개가 존재합니다. 따라서 preorder tree traversal을 통해서 모든 노드를 탐색할 수 있습니다. 이후 문제가 없는 노드들을 선택하면 됩니다.
하지만 위 방식은 너무 비효율적입니다.
따라서 좀 더 효율적인 방식을 사용해야 합니다.
우리는 기준의 정보를 알고 있습니다.
바로 같은 열도 안 되고, 같은 대각선도 안 됩니다.
이 기준을 가지고 state space tree의 노드들을 방문하다가, 기준에 맞지 않는 (같은 열 혹은 같은 대각선) 노드를 발견하면, 하위 노드는 다 버리는 방식을 사용합니다. 어차피 내려가 봤자 해답이 없습니다.
이때 해답이 없는 마디를 만나는 순간, 그 마디의 검색을 중단하고, 부모마디로 돌아가서 다른 자식 마디를 검사를 계속하는 과정이 바로 Backtrack(되추적)입니다.
3. Promising and Pruning
해답이 될 가능성이 없는 마디를 nonPromising(유망하지 않음)이라고 하고, 그렇지 않으면 Promising(유망함)이라고 합니다.
이때 nonpromising하다면 부모 마디로 Backtrack 합니다. 이 절차를 State Space Tree를 Pruning(가지 친다)라고 하고, Promising한 마디로만 구성된 부분 트리를 Pruned State Space Tree(가지친 상태 공간 트리)라고 합니다.
4. A general Algorithm for the Backtracking approach
def checknode(node v) -> None:
node u
if promising(v):
if there is a solution at v:
write the solution
else:
for each child u of v:
checknode(u)대부분 위와 같은 형태를 띄고 있습니다.
5. 효율성 추정
BackTracking은 어쩌면 극 소수의 노드만 방문할 수도 있고, 어쩌면 모든 노드를 방문할 수가 있습니다.
따라서 시간 복잡도를 정확히 판단할 수가 없고, 일반적으로 Monte-Carlo 방식을 사용하여 분석합니다.
몬테 카를로는 확률 알고리즘으로, 결정 알고리즘인 Deterministic과는 다릅니다
몬테 카를로 알고리즘을 이용한다면, 기대치를 추정할 수 있습니다.
간단히 말해서 난수를 생성한 후, 프로그램을 실제로 돌리면서 몇 개의 노드를 방문했는지 개수를 세는 겁니다.
이번 글에서는 알고리즘의 기법 중 Backtracking에 대해 알아봤습니다.
감사합니다.
지적 환영합니다.