A*(길 찾기) 알고리즘 - 구현

A* 알고리즘은 주어진 지점에서 목표 지점까지 가는 최단 경로를 찾아내는 그래프 탐색 알고리즘 중 하나이다. A* 는 F = G + H라는 공식을 사용하는데 F 값이 적을 수록 최적의 경로를 나타낸다. G는 다음 경로를 가는데 필요한 비용 H는 현재 지점에서 목표 지점까지의 추정 비용 H가 A* 알고리즘의 핵심인데 휴리스틱(heuristic) 이라고 불린다. 길 찾기 알고리즘 중 A* 알고리즘과 더불어 유명한 것이 다익스트라 알고리즘이다. 다익스트라에 대해서는 아래 링크를 참조 바란다. 다익스트라(Dijkstra) - 구현 다익스트라는 목표 노드 부터 각 노드까지 최단경로를 구할 때 쓰는 알고리즘이다. 아래 그림을 통해 확인... blog.naver.com 다익스트라 알고리즘은 휴리스틱이 0인 A* 알고리즘이라고 보면 된다. A*에서는 목표 지점까지의 가중치를 추가함으로써 다익스트라 알고리즘에 백트래킹 기법을 더한 것이라고 볼 수 있다. 일반적으로 휴리스틱의 값은 현재 지점에서 목표...

원문링크 : A*(길 찾기) 알고리즘 - 구현