A* 알고리즘

A* 알고리즘
분류	그래프 탐색 알고리즘, 검색 알고리즘
자료구조	그래프
최적	아니오.

전산학 분야에 있어서, A* 알고리듬(A* algorithm 에이 스타 알고리듬^[*])은 주어진 출발지 노드에서부터 목적지 노드까지 가는 최단 경로를 찾아내는(다시 말해 주어진 목적지 노드까지 가는 최단 경로임을 판단할 수 있는 테스트를 통과하는) 그래프/트리 탐색 알고리즘 중 하나이다. 이 알고리즘은 각 노드 $x$ 에 대해 그 노드를 통과하는 최상의 경로를 추정하는 순위값인 "휴리스틱 추정값" $h(x)$ 을 매기는 방법을 쓴다. 이 알고리즘은 이 휴리스틱 추정값의 순서로 노드를 방문한다. 그러므로 우리는 A* 알고리즘을 best first search의 한 예로 분류할 수 있다.

이 알고리즘은 1968년 피터 하트, 닐스 닐슨, 버트램 라팰이 처음 기술하였다. 그 3명의 논문에서, 이 알고리즘은 A 알고리즘(algorithm A)이라고 불렸다. 적절한 휴리스틱을 가지고 이 알고리즘을 사용하면 최적(optimal)이 된다. 그러므로 A* 알고리즘이라고 불린다.

A* 알고리즘은 출발노드로부터 목표노드까지의 최적경로를 탐색하기 위한 것이다. 이를 위해서는 각각의 노드에 대한 평가함수를 정의해야 한다. 이를 위한 평가함수 $f(n)$ 은 다음과 같다.