최단 경로 - A* 알고리즘

다익스트라 : Source에서 다른 모든 노드까지의 최단경로 찾아줌

A* : Source와 Destination을 정하면, 그 사이의 최단경로 찾아줌. Heuristic 사용 (현재 위치에서 dest까지의 '짐작한' 거리 필요). Complete and optimal (iff admissible)

 

Heuristic (혹은 Objective) function f(n) = g(n) + h(n)

g(n) : 시작점 Source로부터 노드 n까지의 실제 거리 (cost)

h(n) : 현재 노드 n에서 Destination까지의 추정(estimated) 거리

(🤔 추정 → 직접 재든가, Manhattan 거리, 피타고라스 정리, ...)

 

Open List, Closed List

Open List에 있는 노드 중, f(n)이 가장 작은 노드 선택해서 closed list로 보내고, 인접한 노드 중 아직 closed list에 없는 노드 방문해서 heuristic function f값 계산.

Destination 방문하면 끝.

 

 

Step-by-step 따라가면 좋은 글

http://www.gisdeveloper.co.kr/?p=3897#:~:text=A*+%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%80+%EC%8B%9C%EC%9E%91+%EB%85%B8%EB%93%9C,%EC%9D%84+%EA%B0%9C%EC%84%A0%ED%95%A0+%EC%88%98+%EC%9E%88%EB%8A%94%EB%8D%B0%EC%9A%94.

최단 경로 탐색 – A_ 알고리즘 – GIS Developer.mhtml

3.62MB