백트래킹(Backtracking)

• 어떠한 집합에서  정해진 기준에 따라 원소의 순서를 선택하는 문제를 푸는 문제에 적합 ex) 순열
• 깊이우선탐색 (DFS)
• 모든 문제에 대해서 효율적인 알고리즘이라고 보장할 순 없으나 대부분의 문제 사례에 대해 효율적이다.
• ex) n-Queens, 부분집합의 합, 0-1 배낭문제 등

미로찾기의 경우 길을 찾다가 갈림길에서 먼저 특정한 방향으로 탐색을 시작한다. 그러다가 막힌 길이 나오는 경우 왔던 길을 다시 돌아와서 갈림길에서 다른 경로를 선택하여 탐색한다. 

 

# 상태공간트리

- 상태 공간: 해답을 탐색하기 위한 탐색 공간

- 상태공간트리: 탐색 공간을 트리 형태의 구조로 암묵적으로 해석

 

# 백트래킹 기법

상태공간트리를 깊이우선탐색으로 탐색하고, 방문 중인 노드에서 조건에 의해 더 하위 노드를 탐색하여도 해답이 없다고 판단이 된다면 하위트리를 방문하지 않고 부모 노드로 되돌아 간다. - 가지치기(pruning)

- 가지치기한 상태: 해당 노드의 방문하지 않는 하위트리 (pruned state)

 

# 유망함(promising) : 해답이 있다고 생각하는 것

 

# n-Queens 문제

n X n 체스판에 n개의 퀸을 배치하는 문제, 어떤 퀸도 다른 퀸에 의해서 잡히지 않도록 배치해야 함

즉, 같은 행, 열, 대각선에는 다른 퀸을 놓을 수 없음

- 백트래킹 적용:

• n^2개의 위치에 퀸을 놓을 수 있음
• 기준: 새로 놓을 퀸이 다른 다른 퀸을 잡을 수 있음(같은 가로,세로,대각선)
• 원소의 순서: 퀸을 놓을 수 있는 n개의 위치

4-Quenns 문제를 생각해보면 1번째 조건은 걑은 가로줄에 놓을 수 없으므로 4개의 퀸을 모두 다른 행을 선택해야하고 그 중에 4개의 열중에서 자리를 선택해야 하므로 4X4X4X4 =256 가지이다. 그리고 가지치기를 하는 경우는 퀸 2개를 놓았을 때 같은 열에 위치한다면 더 이상 다른 퀸을 놓지 않아도 유망하지 않다고 판단하고 더 이상 탐색하지 않는다.