백트랙킹(Backtracking) 기법: 해를 찾는 도중에 막히면(해가 아니면) 되돌아가서 다시 해를 찾아가는 기법
최적화(optimization) 문제와 결정 (decision) 문제를 해결할 수 있다.
결정문제: 문제의 조건을 만족하는 해가 존재하는지의 여부를 'yes' 또는 'no'가 답하는 문제
(ex. 미로찾기, 해밀토니안 사이클 문제, 부분 집합의 합 문제 등)
최적의 답을 찾고 싶은 것이 아니라, 여러 솔루션이 있고 모든 솔루션을 원할 때 사용
Backtrack 알고리즘의 기본 형태
Assume:
1. Solution: X(1...n)
2. X(k)∈S={a1,a2,...,am} for 1<=k<=n, where: finit set
3. Initially, X(k)=a0 for all k, where a0∉S
--백트랙킹 코드--
Procedure BackTrack(n)
k:=1;
for i=1 to n do
X(i) := a0;
while 1 <= k <= do
{
GETNEXT(k);
if X(k) = a0 //조건에 부합하지 않으면
then k:= k-1; **//backtrack**
else if k=n; //끝나면 출력
then OUTPUT(X);
else k:= k+1;
}Procedure GETNEXT(k)
Let ai be the current value of X(k) //ai를 X(k)의 현재 값으로 둔다
while i<m do
{
X(k):= a(i+1); //X(k)값을 a(i+1) 값으로 두자
i:= i+1;
if BOUND(k) = true //조건에 부합하면
then return;
}
if i=m then X(k) := a0; //조건에 부합하지 않으면 X(k)=a0문제 1) n-Queens 문제
n개의 Queen을 서로 상대방을 attack 하지 않도록 n X n chess판에 위치시키는 문제
-> 서로 상대방을 attack 하지 않기 위해서는 같은 행이나, 같은 열이나, 같은 대각선 상에 위치하지 않아야 한다.
8-Queens 문제: 후보해의 개수 : 약 44억개, 실제 해의 개수 : 92개
-> 효율적으로 찾아내는 것이 관건
방법 1) 무작정 알고리즘
후보해의 수: 16C4 = 1820개
Queen들에 임의로 번호를 붙이고, Queen-i는 i행에 할당한다고 가정하자.
그러면 점검해야하는 모든 경우의 수는 4^4 = 256 개이다.
<복습> Depth-First Search
root가 되는 노드를 먼저 방문 -> 그 노드의 모든 desendant(후손)들을 차례로 (보통은 왼->오 순으로) 방문한다.
트리에서는 preorder tree traversal과 같다.
void DFS(node v) {
node u;
visit[v] := 1; //visit[v] = 1
for (each node u which is adjacent to v) //v와 인접한 각 u노드에 대해
DFS(u)
}상태공간트리 (State Space Tree)
문제해결 과정의 중간 상태를 각 노드로 나타낸 트리
- 각 노드들을 problem state (혹은 state)라 함
- Candidate Solution(해답후보): 루트에서 리프까지의 모든 경로
- Answer States: 루트에서 solution states 로의 경로가 solutions의 값이 되는 tuple
DFS로 형성되는 state space tree:
Root 노드에서 leaf 노드까지의 경로는 해답후보가 되는데, 깊이 우선 검색을 하여 그 해답후보 중에서 해답을 찾을 수 있다.
=> 그러나, 이 방법을 사용하면 해달이 될 가능성이 전혀 없는 노드의 후손노드들도 모두 검색해야 하므로 비효율적 (이미 답이 아닌걸 아는데도 리프 노드까지 가서 검색해야함)
4-Queens 문제: 방법 2) Backtrack 기술
- 노드의 유망성:
- 전혀 해답이 나올 가능성이 없는 노드는 non-promising(유망하지 않다)이라 하고,
- 그렇지 않으면 promising(유망하다)이라 한다.
=> 어떤 노드의 유망성을 점검한 후(답이 될까?), 유망하지 않다고 판정되면 그 노드의 부모 노드(parent)로 돌아가서(backtracking) 다음 후손 노드에 대한 검색을 계속한다.
깊이 우선 탐색을 실시(단, 유망한 노드만)
- 순서
1) State Space Tree의 깊이 우선 검색을 실시
2) 각 노드가 promising한 지를 점검
3) 만일 그 노드가 non-promising이면, 그 노드의 부모노드로 돌아가서 계속 검색
state space tree
- 같은 diagonal()에 있는 element들은 (row-column)의 값이 같다.
- 같은 diagonal(/)에 있는 element들은 같은 (row+column) 값을 갖는다.
만약 어떤 두 queen의 위치가 각각 A(a,b), B(c,d)라 두자.
두 Queen이 같은 대각선 상에 있다면, |b-d| = |a-c|이 된다.
DFS vs Backtracking
4-Queen 문제에서 검색하는 노드 개수의 비교
- 순수한 깊이 우선 검색 = 155노드
- backtracking = 27노드
Monte Carlo 기법을 사용한 Backtracking 알고리즘의 수행시간 측정
- Monte Carlo 기법은 어떤 입력이 주어졌을 때 점검하게 되는 state space tree의 전형적인 경로를 무작위로 생성하여 그 경로 상에 있는 노드의 수를 센다. 이 과정을 여러 번 반복하여 나오는 결과의 평균을 추정치로 한다.
- 기법을 적용하기 위해서는 두 조건을 만족해야한다.
- state space tree의 같은 level에 있는 모든 노드의 promising 여부를 점검하는 절차는 같아야한다.
- state space tree의 같은 level에 있는 모든 노드는 반드시 같은 수의 자식노드를 가지고 있어야한다.
=> 이 두 조건을 n-Queens 문제는 만족한다.
문제 2) Graph Coloring (그래프 색칠하기)
problem:
m개의 색을 가지고, 인접한 지역이 같은 색이 되지 않도록 지도에 색칠하는 문제
Backtracking 해법
분석
색깔 개수: m, 노드 개수: n
State space tree 상의 노드의 총수: 1 + m + m^2 + ... + m^n := m^n
문제 3) 외판원 문제(TSP)
그림과 같이 첫번째 해를 찾은 후에도 계속해서 수행하며, 이때 더 짧은 해(bestSolution)를 찾는다.
아래 그림은 tour=[A,C]에 대해서 모든 수행을 마친 결과, bestSolution보다 더 우수한 해는 탐색되지 않았고, x표시된 4개의 상태는 bestSolution의 거리인 16보다 짧지 않아서 가지치기했다.
아래 그림은 [A,D]에 대해서 모든 수행을 마친 결과 bestSolution보다 더 우수한 해는 탐색되지 않았으나, 같은 거리의 해를 찾는데 이 해는 bestSolution의 역순, 즉 [A,B,E,C,D,A]
x로 표시된 1개 상태는 bestSolution과 같으므로 가지치기했다.
//5장 END.
