그래프 탐색 알고리즘

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에만 의존 : 균일비용탐색

 

출처 : http://wwweb.tistory.com/entry/%EA%B7%B8%EB%9E%98%ED%94%84-%ED%83%90%EC%83%89-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98DFSBFSUCSHill-ClimbingA