에이스타알고리즘 (A* Algorithm)
한 줄 정의: 실제 이동 비용과 목표까지의 추정 비용(휴리스틱)을 합한 값을 기준으로 최단 경로를 탐색하는 그래프 탐색 알고리즘.
쉽게 풀면
지금까지 온 거리와 목표까지 대략 남은 거리를 더해서, 가장 유망해 보이는 길부터 우선적으로 탐색해 나가는 길찾기 방법입니다.
논문에서는 이렇게 쓰입니다
A* 알고리즘은 평가 함수 f(n) = g(n) + h(n)을 이용해 노드를 확장하며, h(n)이 실제 남은 비용을 과대평가하지 않는 허용성(admissible)을 만족하면 최적 경로를 보장한다.
g(n)은 시작점부터 현재까지 실제로 온 비용, h(n)은 목표까지 남은 거리를 추정한 값으로, 이 둘을 더해 가장 효율적인 다음 노드를 선택한다는 뜻입니다.
주의할 점
휴리스틱 함수가 허용성을 만족하지 못하면 최적 경로를 보장할 수 없으므로 휴리스틱 설계가 매우 중요합니다.