Advanced05 백트래킹 (5) 핵심요약

1. 백트래킹

 : 해를 찾는 도중에 막히면 즉, 해가 아니면 되돌아가서 다시 해를 찾아 가는 기법.

- 최적화 문제와 결정 문제 해결 가능.

- 탐색 과정에서 해가 될 수 없는 경우들은 탐색 범위에서 제외되기 때문에 완전 검색에 비해 효율적.

- 상태 공간 트리에 기반하여 탐색 수행.

- 상태공간 트리

- 해를 찾기 위한 과정을 트리로 표현

- 내부 노드는 최종상태로 가는 중간 상태 표현

- 단말 노드는 하나의 후보해에 대한 최종 상태

- 트리를 깊이 우선 탐색하는 방법이 백트래킹 알고리즘의 기본 형태

- 깊이 우선 탐색은 모든 경로를 추적하는 데 비해 백트래킹은 가지치기로 불필요한 경로 조기 차단 가능.

- 경우의 수가 너무 많은 경우, 즉 N! 의 경우의 수를 가진 문제에 대해 DFS를 가하면 경우의 수가 너무 많아져서 처리 불가능.

- 백트래킹 알고리즘을 적용하면 일반적으로 경우의 수가 줄어들게 되어 처리 가능.

- but, 최악의 경우에는, 지수함수 시간을 요하므로 처리 불가능.

2. 부분 집합

- 원소의 수가 n개라면 n번의 선택을 통해 하나의 부분집합을 표현.

- 부분 집합 상태 공간 트리

- 선택지가 항상 2개이므로 자식 노드가 2개인 이진 트리 형태.

- 단말 노드 개수 = 2^n

- 왼쪽 자식을 방문하는 경우는 원소를 포함하지 않는 선택(0으로 표현).

- 오른쪽 자식을 방문하는 경우는 원소를 포함하는 선택(1로 표현).

3. 순열

- 순열 상태 공간 트리

- 부분집합과 마찬가지로 나열해야 할 요소의 수가 n개라면 n번의 선택.

- n개의 원소에 대한 부분집합과 순열의 상태 공간 트리의 높이는 동일.

- 순열의 경우에는, 선택을 할 때 마다 가능한 선택지의 감소.

- 루트에서는 n개마늠 선택지가 있지만, 한 번씩 선택을 하여 자식노드를 방문 할 때마다 선택지가 줄어듦.

- 단말노드 개수 = N x (N-1) x (N-2) x .... x 2 x 1 = N!