백트래킹(Backtracking)
비선형으로 구성된 자료 구조를 깊이 우선으로 탐색할 때,
더 이상 나아갈 수 없는 상황에서 그 이전 단계로 복귀하는 과정을 말한다.
-일반적으로 최적화 문제를 해결할 때 사용하는 방법이다.
-문제를 비선형으로 구조화한 다음, 가능한 모든 상태를 깊이 우선으로 탐색해가며 해를 구성해 나간다.
-이 과정에서 더 이상 탐색을 진행할 수 없으면 백트래킹하여 다시 다른 상태를 조사해 나간다.
-모든 가능한 상태를 다 조사하며 이를 백트래킹 기법이라 한다.
문제해결 방법
① 주어진 문제를 비선형 구조로 구조화한다.
② 구조화된 문제공간을 적절한 방법으로 해를 구성할 때까지 탐색한다.
③ 구성된 해를 정리한다.
예제 및 알고리즘
주어진 3 x 3 행렬에서 개의 원소를 서로 행과 열이 중복되지 않도록 선택하는 게임이 있다.
여기서 얻을 수 있는 최소 점수는 얼마인가?
행과 열이 중복되지 않아야 하므로 일단 각 행에서 1개 이상의 값은 얻을 수 없다.
그리고 서로 열도 중복하지 않아야 하므로 위 문제는 다음과 같이 구조화할 수 있다.
위 그림의 탐색 구조는 1행 1열의 1을 선택했을 때의 탐색 구조의 일부이다.
행과 열이 중복되지 않아야 하므로 {2}를 선택할 수 없다.
따라서 깊이 우선으로 구할 수 있는 첫 번째 해는 아래 그림과 같다.
처음으로 구한 해 1-4-5를 탐색하여 구한 수는 10이다.
문제의 조건에 따랏 1행 1열, 2행 2열을 선택했기 때문에 3행에서는 1열과 2열을 선택할 수 없다.
10이 최종적인 해인지 아닌지 현태 상태로는 확정할 수 없다.
따라서 백트리킹으로 가능한 모든 해를 구해야만 최종적으로 해를 구할 수 있다.
1로 백트래킹을 한 다음 7값을 가지는 노드로 진행해 새로운 해를 구할 수 있다.
백트래킹을 계속 진행해 구할 수 있는 모든 해를 나열하면 다음과 같다.
{1, 7, 3} = 11, {5, 2, 5} = 12, {5, 4, 5} = 14, {3, 2, 3} = 8, {3, 4, 5} = 12
구할 수 있는 최소 점수는 3, 2, 3을 선택해 나올 수 있는 8점이 정답이 된다.
위 문제를 알고리즘으로 표현해보자.
|
int m[3][3] = {
min_sol = INT_MAX;
void backtracking(int row, int score) { if(row == 4) if(score < min_sol) min_sol = score; return; for(i = 1; i <= 3; i = i + 1) if(col_check[i] == false) col_check[i] = true; backtracking(row + 1, score + m[row][i]); col_check[i] = false; return; }
main() { backtracking(1, 0); print min_sol on the screen; } |
깊이 우선 탐색(DFS, Depth-first search)
-완전탐색 방법 중 하나
-탐색 트리의 수직방향으로 점차 깊은 곳까지 목표노드를 찾아 탐색해 나가는 기법
(backtracking 과정이 존재)
장점
-단지 현 경로상의 노드들만 기억하면 되므로 저장공간의 수요가 비교적 적다.
-목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.
단점
-해가 없는 경로에 깊이 빠질 가능성이 있다.
(미리 지정한 임의의 깊이까지만 탐색하고 목표노드를 발견하지 못하면 다음의 경로를 탐색하는 방법도 있다.)
-얻어진 해가 최단 경로가 된다는 보장이 없다.
(목표에 이른 경로가 다수인 문제에 대해 깊이우선 탐색은 해에 다다르면 탐색을 끝내므로, 이때 얻은 해가
최적이 아닐 수 있다.)
참고사이트
-위키백과
'공부 > 자료 구조 및 알고리즘' 카테고리의 다른 글
| 알고리즘 기법[부분 탐색] - 분기 한정(Branch & Bound) (0) | 2019.07.22 |
|---|---|
| 알고리즘 기법[부분 탐색] - 탐욕적 방법(Greedy method) (0) | 2019.07.21 |
| 알고리즘 기법[전체 탐색] - 브루트 포스(brute force) (5) | 2019.07.16 |
| 자료의 탐색 - 해싱(Hashing) (0) | 2019.07.15 |
| 자료의 탐색 - 이진 탐색(Binary search) (0) | 2019.07.13 |
