2018년 11월 23일
백트래킹 (Back Tracking)
I. 모든 경우의 수 도출, 백트래킹
모든 경우의 수를 도출하기 위해 DFS와 Pruning 기법 기반 특정 조건 만족하는 모든 해 탐색 기법
II. 백트래킹 절차도 및 세부 절차
가. 백트래킹 절차도
 |
- DFS 기반 유망성 부재 시 Pruning 수행하여 시간 단축
나. 백트래킹 세부 절차
| 절차 | 핵심 개념 | 설명 |
|---|---|---|
| 깊이 우선 탐색 수행 | – 상태 공간 트리 | – 상태 공간 트리 기반 Pre Order 방식 DFS 수행 |
| Promising 검토 | – 유망성 검토 | – 해 존재 가능 시 서브 트리 – 해 부재 예상 시 백트래킹 |
| 서브 트리 이동 | – 재귀 호출 | – 방문 노드의 하위 노드로 이동 – DFS 기반 해 탐색 |
| 백트래킹 수행 | – Pruning | – 방문 노드에 Pruning 수행 – 상위 노드로 백트래킹 |
다. 백트래킹 구성요소
| 구분 | 구성요소 | 설명 |
|---|---|---|
| 노드 | Non-Promising | – 해답이 나올 가능성이 없는 마디 |
Promising | – 해가 나올 만한 유망한 마디 | |
| 해 | 모든 해 | – 해당 문제 해결 위한 모든 해 |
| 후보 해 | – 해가 될 수 있는 집합 | |
| 기법 | DFS | – 깊이 우선 탐색 모든 기법 |
| Back-Tracking | – 가능성 없는 마디 제거(Pruning) |
III. 백트래킹 예제기반 원리 설명
 |
About The Author
