A* 알고리즘, 다익스트라(Dijkstra) 알고리즘

[ A* 알고리즘 ]

다익스트라, A* 모두 그리디 기반의 길 찾기 알고리즘인데

다익스트라는 모든 경로를 구하고 A*는 목적지까지의 경로만을 구하려 하는 이유가 무엇일까?

기본적으로 다익스트라 알고리즘은 시작 노드로부터 가장 최소의 비용으로 도달한 노드를 다음 탐색 노드로 선정한다. 

 

반면 A* 알고리즘은 다음 탐색 노드를 선정하는 방식이 다익스트라와 사뭇 다른데, 시작 노드부터 현재 노드까지의 비용을 g(n), 현재 노드에서 목표 노드까지의 예상 비용을 h(n)이라 할 때, 이 두 값을 더한 f(n) = g(n) + h(n)이 가장 최소가 되는 노드를 다음 탐색 노드로 선정한다. 일반적으로 가장 작은 f(n)을 찾기 위해 우선순위 큐가 사용된다.

현재 노드에서 목표 노드까지의 예상 비용을 구하는 함수 h(n)을 휴리스틱 함수라 하며 휴리스틱 함수를 설계하는 방법에 따라서 알고리즘의 성능이 결정된다. 가장 단순하며 대표적인 휴리스틱 함수로 맨해튼 거리 함수와 유클리디안 거리 함수가 있으며 본 포스팅에선 맨해튼 거리를 이용해서 길 찾기 코드를 작성할 예정이다.

 

간단하게 예제를 살펴보면 시작 노드(A)와 목표 노드(B)가 있을 때, A 주변 노드의 f(n)을 구하면 다음과 같다.

8개의 노드 중 f(n)이 가장 작은 ↖방향 노드를 다음 탐색 노드로 선정하고 ↖방향 주변 노드의 f(n)을 다시 구한다.

( h(n) = 유클리디안 거리 함수 )

 

이처럼 가장 작은 f(n)을 가진 노드를 찾아가고 다시 주변 노드의 f(n)을 계산하고 찾아가고 계산하는 과정을 반복하면 목표 노드인 B에 도착할 수 있다.

---

 

[ 다익스트라(Dijkstra) 알고리즘 ]

다익스트라 알고리즘은 그래프 상에서 시작 정점부터 나머지 각 정점까지의 최단거리를 계산하는 알고리즘이다. 

다익스트라 알고리즘은 그래프의 어느 간선의 가중치라도 음수가 있으면 안된다. (벨만-포드 알고리즘은 음수도 가능)

 

다익스트라 알고리즘을 구현하기 위해서는 다음과 같은 과정을 반복하면 된다.

1. 방문하지 않은 정점 중 가장 가중치 값이 작은 정점을 방문한다. (처음엔 시작 정점 방문)
2. 해당 정점을 거쳐서 갈 수 있는 정점의 거리가 이전에 기록한 값보다 작다면 그 거리를 갱신한다.  

이해가 잘 가지 않는다면 아래 예시를 보면 이해가 빠를 것이다.

위와 같은 그래프가 있다고 하자. 시작정점은 0번 정점이라고 가정하고 나머지 정점까지의 최단거리를 계산해보자.

1차원 배열 dist[]에 각 정점까지의 최단거리를 갱신해 나갈 것이다. 초기에는 모두 INF(무한대)로 설정한다.

• 가장 먼저 시작정점을 방문한다.
• 시작 정점에서 방문 할 수 있는 정점들에 대한 거리를 갱신한다. 

• 방문하지 않은 정점 중 가장 가중치가 작은 2번 정점을 방문한다.
• 0번 정점에서 2번 정점을 거쳐서 4번 정점을 가면 기존 거리 보다 최단 거리이므로 갱신한다 ( INF > 11)
• 0번 정점에서 2번 정점을 거쳐서 3번 정점을 가면 기존 거리 보다 최단 거리이므로 갱신한다 ( 7 > 6 )

• 방문하지 않은 정점 중 가장 가중치가 작은 3번 정점을 방문한다. 
• 0번 정점-2번 정점-3번정점을 거쳐서 4번 정점을 가면 기존 거리보다 최단 거리이므로 갱신한다( 11> 10 )

  

• 방문하지 않은 정점 중 가장 가중치가 작은 4번 정점을 방문한다.
• 갱신할 거리가 없다.

• 방문하지 않은 정점 중 가장 가중치가 작은 1번 정점을 방문한다.
• 갱신할 거리가 없다.
• 모든 정점을 방문했으므로 종료한다.

위와 같은 과정을 거치면 dist 배열에 0번정점부터 각 정점까지의 최단거리가 기록되게 된다.

---

대표적인 그래프 탐색 알고리즘들과 A*의 차이점은

BFS는 가중치가 없는 그래프에서 최단 경로를 찾는 완전 탐색 알고리즘이며

다익스트라는 가중치 그래프에서 시작 노드를 기준으로 모든 노드까지의 최단거리를 구하는 그리디 알고리즘이다.

반면 A* 알고리즘은 가중치 그래프에서 시작 노드에서 목표 노드까지의 최단 경로만 구하려 하는 그리디 알고리즘이다.

 

[ 정리 ]

BFS : 가중치 없는 그래프, 시작 노드 기준으로 모든 노드의 최단 경로 구함, 완전 탐색 

다익스트라 : 가중치 그래프, 시작 노드 기준으로 모든 노드의 최단 경로 구함, 그리디 알고리즘

A* : 가중치 그래프, 시작 노드에서 목표 노드까지의 최단 경로만을 구하려 함, 그리디 알고리즘

 

 

 

출처:

https://code-lab1.tistory.com/29

https://kangworld.tistory.com/61

---