1. 모든 경우의 수 도출, 백트래킹 (Back-Tracking)
- 모든 경우의 수를 도출하기 위해 DFS와 Pruning 기법 기반 특정 조건 만족하는 모든 해 탐색 기법
2. 백트래킹 (Back-Tracking) 절차도 및 세부 절차
(1) 백트래킹 절차도
| |
- DFS 기반 유망성 부재 시 Pruning 수행하여 시간 단축
(2) 백트래킹 세부 절차
| 절차 | 핵심 개념 | 설명 |
|---|---|---|
| 깊이 우선 탐색 수행 | – 상태 공간 트리 | – 상태 공간 트리 기반 Pre Order 방식 DFS 수행 |
| Promising 검토 | – 유망성 검토 | – 해 존재 가능 시 서브 트리 – 해 부재 예상 시 백트래킹 |
| 서브 트리 이동 | – 재귀 호출 | – 방문 노드의 하위 노드로 이동 – DFS 기반 해 탐색 |
| 백트래킹 수행 | – Pruning | – 방문 노드에 Pruning 수행 – 상위 노드로 백트래킹 |
(3) 백트래킹 구성요소
| 구분 | 구성요소 | 설명 |
|---|---|---|
| 노드 | Non-Promising | – 해답이 나올 가능성이 없는 마디 |
| Promising | – 해가 나올 만한 유망한 마디 | |
| 해 | 모든 해 | – 해당 문제 해결 위한 모든 해 |
| 후보 해 | – 해가 될 수 있는 집합 | |
| 기법 | DFS | – 깊이 우선 탐색 모든 기법 |
| Back-Tracking | – 가능성 없는 마디 제거(Pruning) |
- 그 외 특정 순간 최적해를 구하기 위해 최적성과 효율성 개선을 통해 최적의 해를 도출하는 그리디 알고리즘 등 여러 해 탐색 기법 존
[참고]
- Wikipedia, Back-Tracking