개요

A* 알고리즘에 대해 기본 개념 이해하고 구현한다. 또한 최적화 방안을 살펴보자.

기본 개념

A*알고리즘은 경로 찾기와 그래프 탐색 문제에 사용되는 알고리즘으로, 최적성과 완전성을 동시에 보장한다.

즉, 항상 최적의 해를 찾아낼 수 있으며, 해가 존재한다면 반드시 해를 찾을 수 있다.

이전에 최적의 경로를 탐색하는 알고리즘으로

Dijkstra 알고리즘이 있다.

Dijkstra 알고리즘은 가중 그래프에서 한 노드에서 다른 모든 노드까지의 최단 경로를 찾는 알고리즘으로 그리디 알고리즘을 기반으로 동작한다.

• 그리디 알고리즘

A*와 Dijlkstra 모두 최단 경로를 찾는 알고리즘이고

• 가중 그래프에서 동작한다.

다만 Dijkstra에서 모든 노드에 대해 최단 경로를 찾는 것과 달리 A*는 목표 지점을 고려하여 탐색 범위를 좁힌다.

A* 알고리즘은 각 노드에 대해 두 가지 값을 계산한다.

<aside> 💡 f(n) = g(n) + h(n)

</aside>

여기서

• g(n)은 시작 노드에서 n 노드까지의 실제 비용(다익스트라 알고리즘과 동일)
• h(n)은 n 노드에서 목표 노드까지의 추정 비용 (휴리스틱 함수)