A Star 알고리즘은 기본으로 Djikstra 알고리즘을 확장한 개념으로 다음 노드로 이동하는 과정에서 가중치가 가장 작은 노드를 우선으로 탐색하는 개념은 동일하다. 우선순위 큐에서 Top을 뽑을 때 djikstra는 시작부터 현재 노드까지 누적비용(g)가 가장 작은 노드를 우선으로 뽑는다. 하지만 A*는 현재까지 누적 비용(g)와 현재 부터 목적지 까지의 휴리스틱 비용(h)를 합쳐 가장 작은것을 우선으로 뽑는다. 이해를 돕자면 djikstra는 현재에 충실하는 반면, A*는 미래까지도 확인하여 탐색하는 노드 확장을 기하 급수적으로 줄일 수 있다. 아래 그림은 (Djikstra, A*, Weighted A*)를 사용했을때 탐색 범위이다. G 값 계산 A*의 g값을 계산하는 방법은 다양하며, 확장 방향에..
