a*

A* Algorithm 구현

C++ 로 A* 알고리즘을 구현하는데 성공했다. 다익스트라 알고리즘도 직전에 구현했는데 곧 포스팅 하도록 하겠다. A* 알고리즘이란? 길찾기 알고리즘의 일종으로 Openlist, Closedlist, Parent 와 F=G+H 라는 식을 통해 최적의 경로를 찾는다. Openlist 는 경로를 탐색하면서 고려대상으로 포함이 되는 노드들을 말한다. Closedlist는 Openlist 중에 목적지까지의 가장 짧은 거리를 가진 노드들이다. Parent는 현재 노드의 바로 직전 노드, 이걸 통해서 경로를 이어줄 수 있다. F, G, H는 보통 프로그래머가 어떤 식으로 계산하느냐에 따라 달라질 수 있다. 일반적으로 G는 시작노드에서 특정노드까지의 이동거리, H는 특정노드에서 목적노드까지의 이동거리, F는 G+H ..