그래프 탐색 알고리즘(DFS,BFS,UCS,Hill-Climbing,A*)

 

1. 깊이우선탐색(DFS, Depth First Search)

- 해가 존재할 가능성 있으면 계속 전진 탐색

- 스택 구조, 재귀 호출 이용

- 재귀 호출이 이루어질 때마다 위치가 점점 깊게 들어감

- 너무 깊게 들어가면 overflow 발생하므로, 막히면 나아갈 곳이 있는 곳으로 돌아가서 과정 반복, 모든 곳을 방문했을 때 탐색 종료

- 유용 : 사이클 탐지(Cycle Detection), 위상 정렬(Topological Sorting)

- 장점 : 무한히 넓은 트리에 효과적

- 단점 : 목표 노드가 없는 경로에 깊이 빠질 수 있음 <- 깊이 제한

2. 너비우선탐색(BFS, Breadth First Search)

- 생성된 순서에 따라 노드 확장

- 큐 구조, 큐의 첫 정점을 보고 그 정점에 인접한 정점들 탐색

- 새롭게 발견되는 정점 enqueue, 모든 인접 정점 탐색 끝나면 첫 정점 dequeue

- 많은 기억 공간 필요

- 유용 : 최소신장트리(Minimum Spanning Trees), 최단경로(Shortest Paths)

- 장점 : 무한히 깊거나 무한에 가까운 트리인 경우 효과적

- 단점 : 목표 노드로 가는 경로들 모두가 같은 거리일 때 헛된 탐색

3. 균일비용방법(UCS, Uniform Cost Search)

- 출발 노드로부터의 경로비용이 최소인 노드 선택 확장

- g(n_i) = g(n) +c(n, n_i)

- 음수가 있는 Graph -> 음수 값을 0으로 하기 위해 모두 +
 

4. 언덕오르기방법(Hill-Climbing)

- 임의 경로 신속 탐색

- 현재 상태까지 도달하는데 소비한 경로 비용 무시

- 남은 경로까지의 비용만 고려

문제점

- 지역최대치 문제 : ┳   ┯  인 경우 후자에 도달시 더 이상 진행 X

  -> Back Tracking으로 해결

- 평원 문제 : 사방이 동일한 경우 진행 X

  -> 연산자 반복으로 해결

- 능선 문제 : Branching factor : 너무 많아지면 비효율적

                                              너무 제한하면 실제지형 판단 힘듦

  -> Branching Factor 적절히 늘림으로서 해결

5. 최적우선탐색(Best First Search)

- 지역적으로 확장된 모든 노드 중 가장 좋은 노드부터 탐색

- 많은 메모리 소요, 구현 방법 복잡

- 언덕오르기 탐색과 같이 정렬을 필요로 함

6. A* 알고리즘

- 시작으로부터 목표에 이르는 하나의 경로를 찾음

- 휴리스틱을 가장 효율적으로 사용

- A₁ :  f₁(n) = g₁(n) + h₁(n)       모든 노드에 대해 h₁(n) <= h(n)

  A₂  :  f₂(n) = g₂(n) + h₂(n)       모든 노드에 대해 h₂(n) <= h(n)

- h₁(n), h₂(n)는 예측 경로 비용

- h₁(n) = h(n) -> 곧바로 목표노드(최소비용)

  h₁(n) = 0     -> g에만 의존 : 균일비용탐색