트리, 그래프 등의 자료구조에서 최단 경로를 찾기 위한 휴리스틱 알고리즘이다. A-star Algorithm의 단점 중 하나인 priority queue에서 얻은 모든 노드를 방문하는 것을 보완하기 위해, 방향을 바꿀 수 있는 코너 지점 만을 큐에 넣어 탐색한다. : 비용함수 : 현재 노드까지의 최단 거리 : 현재 노드로 부터 남은 거리 (예측값)
- priority queue에서 최우선 노드를 현재 노드 지정한다.
- 현재 노드로부터 상하좌우, 대각선 방향으로 이동하면서 “코너”를 찾는다.
- “코너”에서는 직진을 멈추고, 주변 노드를 priority queue에 삽입한 뒤, 다시 (1)을 반복한다.
- 위 과정을 목적 노드에 도달할 때 까지 반복한다.