A* 알고리즘

A* 알고리즘

다익스트라 알고리즘을 확장하여 만들어진 최단 경로 탐색 알고리즘

 

g(x) : 출발 위치에서부터 현재 위치까지 오는 비용

h(x) : 휴리스틱 알고리즘을 통해 계산한 현재 위치부터 도착지점까지 예상 비용

f(x) = g(x) + h(x)일때 f(x)가 최소가 되는 노드부터 탐색하는 BFS 방식의 알고리즘

참고로 다익스트라 알고리즘은 f(x) = g(x)인 경우

 

A* 알고리즘의 성능은 h(x)에 따라 좌우된다

h(x)가 과소평가를 한다면 최단 거리는 보장되지만 더 넓은 노드를 탐색하게되서 성능이 저하될 수 있다

반면 과대평가한다면 빠르게 답을 구할 수 있지만 최단 거리가 보장되지 않는다

결국 h(x)가 얼마나 실제 비용과 가깝게 비용을 예상할 수 있는지가 A* 알고리즘 성능에 있어서 중요하다