최단 경로 탐색 - A* 알고리즘

최단 경로 탐색

목적지가 분명하다.

 

-과정

O: open 앞으로 갈 지점
C: close 현재 지점

F score: G + H, F가 짧은거 선택
G score: 처음 노드부터 자기 노드까지 거리
H score: 앞으로 갈 목적지까지 예상 거리, 1->6은 직접 못간다. 그래서 직선 거리를 구한다, 대충 눈대중으로 구함

parent node로 추적해서 경로 찾는다.

가장 짧은 3을 선택

 

이렇게 하다 보면 최종적으로

이렇게 나온다. 그러면 C의 마지막부터 parent node를 따라가서 출발지가 나오면 그게 최종 경로이다.