A* 알고리즘

A* 알고리즘은 출발지에서 목적지까지 가는 최단 경로를 찾아내기 위한 알고리즘입니다.

최단경로를 찾아내기 위해 주로 사용되는 다익스트라 알고리즘과 달리 완전한 최단 경로를 찾지 않고,  최단 경로의 근사값을 찾아내는 것을 목표로 하기 때문에 다익스트라 알고리즘만큼 정확한 답을 찾지 못하는 대신 탐색 속도는 더 빠릅니다.

 

A* 알고리즘은 휴리스틱 함수를 통해 현재 위치가 얼마나 좋은 상태인지를 추정하여 점수를 매겨 탐색을 진행합니다.

 

구분	다익스트라 알고리즘	A* 알고리즘
목표	완전한 최단경로 탐색	최단경로의 근사값
정확도	높음	보통
속도	느림	빠름

 

A* 알고리즘의 동작 방식

• F(n) = G(n) + H(n)
• F(n)
• 모든 노드가 갖는 값
• G(n)
• 출발지에서 현재 노드까지의 비용
• 실제 정보에 대한 가중치
• 다익스트라 알고리즘, BFS 등의 알고리즘 방식 사용
• 계산 쉬움
• H(n)
• 현재 노드에서 목적지까지의 예상 비용
• 정확한 비용 예측을 위해 휴리스틱 사용
• 경로를 택하기 위한 계획에 대한 가중치
• 계산 까다로움
• 예시