[Algorithm] 백트래킹 알고리즘

백트래킹 알고리즘 - 개 념

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

 

 

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 까지 찾아 감

 

 

[Algorithm] 최소신장트리 알고리즘

[Algorithm] 최소신장트리 알고리즘

 

[Algorithm] 순차 탐색 (Sequential Search)

[Algorithm] 순차 탐색 (Sequential Search)