최단 경로를 탐색하는 알고리즘 중 Dijkstra와 A* 알고리즘에 대해 간단하게 알아보자.
두 알고리즘의 차이는 다음과 같다.
- Dijkstra : 시작점으로부터 나머지 정점들까지의 최단 거리를 구한다.
- A* : 시작점이 정해지고, 목표점이 정해지면 2개의 최단 거리를 구한다.
| Dijkstra
시작 정점에서 모든 정점까지의 최단 경로를 구하는 알고리즘이다.
- 탐욕적 탐색(Greedy)을 사용하며, 방문하지 않은 정점 중 최단 거리를 가진 정점을 선택한다.
- 각 경로의 비용만 고려하며, 목표 노드에 도달하는 방향성을 가지지 않는다.
동작 방식
- 시작 정점의 거리를 0으로 초기화하고, 나머지 정점의 거리는 무한대로 설정
- 현재 정점에서 갈 수 있는 모든 인접 정점의 거리 값을 업데이트
- 업데이트 후, 방문하지 않은 정점 중 최단 거리를 가진 정점을 선택
- 목표 노드에 도달하거나 모든 정점을 방문할 때까지 반복
모든 최단 경로를 알 수 있지만, 음의 가중치가 없는 경우에만 적용 가능하다.
또한, 목적지 노드에 도달하기 위한 방향성이 없어, 탐색 범위가 넓다.
| A*
특정 시작 정점에서 목표 정점까지의 최단 경로를 구하는 알고리즘이다.
- 탐색 방식: 탐욕적 탐색 + 휴리스틱(Heuristic)을 사용한다.
- 휴리스틱 사용: 예상 거리(휴리스틱)와 현재까지의 경로 비용을 합산하여 탐색 우선순위를 결정한다.
동작 방식
- f(n)=g(n)+h(n)
- g(n): 시작 정점에서 현재 정점 n까지의 실제 비용
- h(n): 현재 정점 n에서 목표 정점까지의 예상 비용(휴리스틱)
- 우선순위 큐에 시작 정점을 삽입하고, 큐에서 가장 작은 f(n) 값을 가진 정점을 선택한다.
- 현재 정점에서 인접한 정점으로의 이동 비용을 계산하고 f(n)값을 업데이트한다.
- 목표 정점에 도달하면 종료한다.
Dijkstra보다 효율적으로 특정 목표에 도달 가능하며, 탐색 범위를 줄여 빠르게 동작할 가능성이 높다.
하지만, 적절한 휴리스틱 함수가 필요하고, 휴리스틱이 정확하지 않으면 비효율적일 수 있다.