[Information]/[Algorithm]

[Algorithm] 백트래킹 알고리즘

starterr 2024. 7. 25. 16:42

백트래킹 알고리즘 - 개 념

깊이우선탐색(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 문제)
백트래킹의 적용 사례 (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] 최소신장트리 알고리즘

개 념최소신장트리 (Minimum Spanning Tree) 알고리즘 (프림 알고리즘, 크루스칼 알고리즘) 모든 정점을 포함하고 정점 간 서로 연결하면서 사이클이 존재하지 않는 그래프 I. 신장트리 (Spanning Tree)의

infoofit.tistory.com

 

[Algorithm] 순차 탐색 (Sequential Search)

 

[Algorithm] 순차 탐색 (Sequential Search)

개념정렬되지 않은 배열의 항목들을 처음부터 마지막까지 하나씩 검사하여 원하는 항목을 찾아가는 방법 I. 순차 탐색 (Sequential Search)의 개요 가. 순차 탐색의 정의- 정렬되지 않은 배열의

infoofit.tistory.com

 

 

반응형