A star 알고리즘가중치를 이용한 길찾기 알고리즘 (나무위키 긁어옴) A* 알고리즘은 현재 상태의 비용을 g(x)g(x), 현재 상태에서 다음 상태로 이동할 때의 휴리스틱 함수를 h(x)h(x)라고 할 때, 둘을 더한 f(x)=g(x)+h(x)f(x)=g(x)+h(x)가 최소가 되는 지점을 우선적으로 탐색하는 방법이다. 이 f(x)f(x)가 작은 값부터 탐색하는 특성상 우선순위 큐가 사용된다. 휴리스틱 함수 h(x)h(x)에 따라 성능이 극명하게 갈리며, f(x)=g(x)f(x)=g(x)일 때는 다익스트라 알고리즘과 동일하다.A*를 사용하는 이유는 다익스트라를 직접 현실 문제에 적용하기가 매우 부담되기 때문이다. 당장에 네트워크 같은 디지털적인 공간이 아닌, 현실의, 사람이 사는 공간을 생각해보자. 사..
