A-star Algorithm

A* 알고리즘은 트리, 그래프 등의 자료구조에서 최단 경로를 찾기 위한 휴리스틱 알고리즘이다. Dijkstra Algorithm의 비용함수에 휴리스틱 함수 $h(x)$를 추가한 형태이다. $f(x)=g(x)+h(x)$ $f(x)$: 비용함수 $g(x)$: 현재 노드까지의 최단 거리 $h(x)$: 현재 노드로 부터 남은 거리 (예측값)

1. 각 노드까지의 거리를 inf로 설정한다.
2. 현재 도달 가능한 노드의 $f(x)$를 바탕으로 우선순위 큐(또는 힙 트리)를 구성한다.
3. $f(x)$가 최소가 되는 노드를 현재 노드로 설정한다.
4. 해당 노드에서 방문 가능한 노드들을 우선순위 큐에 추가한다.
5. 위 과정을 반복하여 목표 노드에 도착하는 경우 중지한다.