Back-Tracking 알고리즘

Back-Tracking 알고리즘이란?

기본적으로 탐색을 기반으로 한 알고리즘입니다. 

DFS 던 BFS 던 모두 다 쓰이는 방법으로, 탐색의 횟수가 많을 때, 

답으로 가지 않는 트리는 과감히 버리고, 답으로 갈 만한 트리만 가지치기 하여서 체크하는 방법입니다.

소개에서도 말씀드렸듯, 답으로 갈 수 있는 상태 공간 트리를 만들어서 탐색 횟수를 기가막히게 줄입니다.

아래 그림을 참조해봅시다.

백트래킹은 위에 그림으로 설명이 끝난다.

한 노드에 있어서 이어지는 경로 중 해결책으로 이어지지 않을 경우 더이상 따라가지 않아서

시도 횟수를 줄게 만든다. (가지치기 방식) --> 불필요한 경로는 조기에 차단

이는 깊이 우선 탐색의 문제를 해결해줍니다.

깊이 우선 탐색은 경우의 수가 많으면 처리하기 힘듭니다.

가령, 8-Queens 문제를 풀게 된다면, 경우의 수로 나올 수 있는 것이 64C8 개입니다. (깊이 우선 탐색)

그러나 백트래킹 방식을 사용한다면, 해에 관련된 트리만 가지고 탐색하기 때문에

92가지만 나오게 됩니다. (탐색 횟수 : 92)

---

private static int queen_located(int row) {

if (row == row_num)

return 1;

int count = 0;

for (int col = 0; col < row_num; col++) {

if (check(row, col)) {

check_col[col] = true;

check_dv1[row + col] = true;

check_dv2[row - col + row_num] = true;

a[row][col] = true; // 퀸이 있움

count += queen_located(row + 1); // 다음 행으로 이동

// Back Tracking ... 다시 처음으로 돌린 다음에 행열 정리

//System.out.println("루프 체크" + " " + count);

check_col[col] = false;

check_dv1[row + col] = false;

check_dv2[row - col + row_num] = false;

a[row][col] = false;

}

}

return count;

}

---

앞서 N-Queens 문제를 포스팅 했지만 다시 체크해보면, 행과 열 그리고 대각선 모두 갈 수 있는지 체크를 한 뒤에, 퀸을 미로에 둡니다. 

그리고 나서 다시 재귀로 함수를 호출하는데, 행을 한 칸 이동하면서 호출하고

거기서의 횟수를 계속해서 더해줍니다.

그리고 중요한 것은 재귀 함수로 호출한 다음에, 백트래킹으로 이 전에 왔던 곳은 지나지 않았다고 체크한다

즉, 해가 없는 브랜치는 가지 않는다는 것과 같다고 생각하시면 됩니다.

다음 포스팅에서는 조금 더 구체적으로 정리해서 소개하겠습니다.

감사합니다 =)