백트래킹 알고리즘
백트래킹 정의
•
모든 가능한 경우의 수를 탐색하는 알고리즘
백트래킹은 트리 자료구조에서 그래프 탐색의 변형된 모습이다.
대부분의 백트래킹 알고리즘은 깊이우선탐색(DFS)의 형태를 가지고 있다. 모든 경우의 수를 탐색하는 DFS와는 다르게 백트래킹은 유망하지 않다고(non-promising) 판단된 노드는 배제(purning)한다.
즉, 해당 노드가 유망한지(promising) 검사하여, 해가 될 수 있는 경우에만 자식 노드를 탐색한다
•
특정한 집합(set)에서 어떤 기준(criterion)을 만족하는 원소들의 순서(sequence)를 선택하는 알고리즘
또한 백트래킹은 각 원소들을 순서대로 방문(DFS)하면서 기준을 만족하는지(promising) 검사한다
따라서 수열이나 순열, 조합을 구하는 문제를 푸는 방법이 될 수 있다
백트래킹 기법
상태 공간 트리 (State Space Tree)
•
백트래킹은 상태 공간 트리를 갖는다
•
상태 공간이란 해답을 탐색하기 위한 탐색 공간이며, 상태 공간 트리는 탐색 공간을 트리 형태의 구조로 암묵적으로 해석한 것이다
•
암묵적으로 해석한 것이기 때문에 일반적인 배열을 트리라고 생각하고 접근하면 된다
깊이 우선 탐색 (DFS)
•
깊이 우선 탐색은 이름 그대로 그래프의 최대 깊이까지 탐색 한 후, 이전 분기점으로 돌아가 탐색을 이어가는 탐색 방법
•
BFS는 이와 반대로 시작 정점과 인접한 모든 정점을 우선 방문하는 탐색 방법
DFS
BFS
백트래킹 기본 구조
1.
탈출 조건
2.
상태 변화
3.
재귀 호출
4.
상태 복구
5.
유망 함수
void backtracking(int index) {
if (index == n) { // 탈출 조건
return;
}
if (isPromising()) {
visited[index] = true; // 상태 변화
backtracking(index + 1); // 재귀 호출
visited[index] = false; // 상태 복구
}
}
bool isPromising(int index) { // 유망 함수
if (non-promising) return false;
if (promising) return true;
}
C++
복사
•
백트래킹은 보통 재귀(recursion)로 구현된다
•
따라서 재귀함수의 종료 조건이 있어야 한다
•
유망 함수 (promising function)는 문제에 따라 필요하지 않는 경우도 있다
•
한 노드의 탐색이 종료되면 상태 배열을 복구하여 다음 탐색에 영향이 없어야 한다
추가 내용
•
자료구조 그래프와 트리 이론
•
재귀로 구현하는 다른 알고리즘과의 비교
