백트래킹 (Back Tracking)

I. 모든 경우의 수 도출, 백트래킹

모든 경우의 수를 도출하기 위해 DFS와 Pruning 기법 기반 특정 조건 만족하는 모든 해 탐색 기법

II. 백트래킹 절차도 및 세부 절차

가. 백트래킹 절차도

 
  • DFS 기반 유망성 부재 시 Pruning 수행하여 시간 단축

나. 백트래킹 세부 절차

절차핵심 개념설명
깊이 우선 탐색 수행– 상태 공간 트리– 상태 공간 트리 기반 Pre Order 방식 DFS 수행
Promising 검토– 유망성 검토– 해 존재 가능 시 서브 트리
– 해 부재 예상 시 백트래킹
서브 트리 이동– 재귀 호출– 방문 노드의 하위 노드로 이동
– DFS 기반 해 탐색
백트래킹 수행– Pruning– 방문 노드에 Pruning 수행
– 상위 노드로 백트래킹

다. 백트래킹 구성요소

구분구성요소설명
노드

Non-Promising

– 해답이 나올 가능성이 없는 마디

Promising

– 해가 나올 만한 유망한 마디
모든 해– 해당 문제 해결 위한 모든 해
후보 해– 해가 될 수 있는 집합
기법DFS– 깊이 우선 탐색 모든 기법
Back-Tracking– 가능성 없는 마디 제거(Pruning)

III. 백트래킹 예제기반 원리 설명

 

콘텐츠 사용 시 출처 표기 부탁 드리고, 댓글은 큰 힘이 됩니다^^