백트래킹 알고리즘

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

. 백트래킹(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 문제)

- Queen 이 서로 Checkmate 되지 않도록 배치하는 문제

- Step 1 과 2를 통해 해가 없다는 것을 확인 후 1,1 을 pruning 수행

- Step 3 에서 1,2 에 Queen 을 배치 후 promising 검증을 통해 하위 탐색

   - Step 4 에서 마지막 4,3 에 Queen 을 할당하여 최적해 탐색 후 종료

 

다. 미로 탈출로 찾기 예제

구분

그림

미로 표현

미로길

검색

경로

미로길_트리

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

 

댓글
닉네임

qqqq