[Algorithm] 백트래킹 알고리즘

I. 백트래킹(Back Tracking) 알고리즘의 개요

가. 백트래킹 알고리즘의 정의

깊이우선탐색(DFS)기법에 Pruning 기법을 적용하여 Promising 검토와 Back Tracking 을 활용하여 탐색 성능을 개선한 알고리즘

 

나. 백트래킹의 특징

특징	설명
깊이우선탐색 기법	탐색 트리의 최초의 하위노드 (child node) 를 확장하여 목표상태 (goal state) 가 발견될 때까지 더 깊이 (deeper and deeper) 확장하는 무정보 탐색(Uninformed or Blind Search) 방법
Pruning 기법	유망하지 않은 노드를 포함한 경로를 더 이상 고려하지 않도록 가지치기 표시를 하는 기법

 

Ⅱ. 백트래킹의 순서도 절차

가. 백트래킹의 순서도

백트래킹의 순서도

나. 백트래킹의 절차

절 차	핵심 개념	설명
1. 깊이우선탐색수행	상태공간 트리	상태공간트리를 활용하여 Pre Order 방식으로 깊이우선 탐색 수행, 해를 찾음
2. Promising 검토	유망성 검토	방문한 Node 를 포함하여 해가 있을 가능성이 있으면 3번, 없으면 4번 이동
3. 서브 트리 이동	재귀 호출	방문한 Node 의 하위 Node 로 이동 후 1번으로 이동하여 해를 탐색
4. 백트래킹 수행	Pruning 수행	방문한 Node 에 Pruning 후 상위 Node 로 백트래킹 후 1번으로 이동함

 

 

III. 백트래킹 알고리즘 구현 및 적용 사례

가. 백트래킹의 알고리즘

백트래킹 알고리즘 구현 및 적용 사례

 

나. 백트래킹의 적용 사례 (4*4 Queen 문제)

백트래킹의 적용 사례 (4*4 Queen 문제)

 

• Queen 이 서로 Checkmate 되지 않도록 배치하는 문제
• Step 1 과 2를 통해 해가 없다는 것을 확인 후 1,1 을 pruning 수행
• Step 3 에서 1,2 에 Queen 을 배치 후 promising 검증을 통해 하위 탐색
• Step 4 에서 마지막 4,3 에 Queen 을 할당하여 최적해 탐색 후 종료

 

다. 미로 탈출로 찾기 예제

구 분	그 림
미로 표현
검색 경로	Start 부터 시작에서 1,2,3 순으로 깊이 우선 탐색을 하게 됨 탐색한 노드가 마지막 노드일 시에 “백트레킹” 을 하여 이전 노드로 돌아가감 이런 ①~② 까지 의 과정을 반복적으로 진행 하면서 Goal 까지 찾아 감