A* 알고리즘

A* 알고리즘은 컴퓨터 게임뿐만 아니라 자동차 네비게이션 자연어 파싱 등에도 사용된다.

A*알고리즘의 수식은 다음과 같다.

   f (n)  =    g(n)   +         h(n)
최종값 = 경로값 + 휴리스틱 예측값

• 휴리스틱 예측값
  - 현위치에서 목적지까지의 최단 거리로 설정
  - 상황에 따라 다른 함수로 만들어서 사용해도 무관하다. -> 다양한 상황에서 사용 가능.

최단 경로를 나타내는 다익스트라 알고리즘의 식은 다음과 같다.

f(n) = g(n)

즉 A*는 다익스트라 알고리즘에서 h(n) (휴리스틱 예측값)이라는 값을 더해서 사용하는 것이다.

 

그래프 예시입니다.

A* 알고리즘 순서를 나타내보겠습니다.

1. A부터 B까지 A*값 = 5.5 , C까지 A*값 = 6.5  -> B가 더 작으므로 B에서 진행
2. B와 이어져있는 D까지 A*값 = 5 < C까지의 A*값 (6.5) -> D에서 계속 진행
3. D와 연결된 F A*값 = 9 > C까지의 A*값(6.5) -> F의 A*값이 더 크므로 C에서 진행.
4. C와 연결된 E A*값 = 7 < F A*값(9) -> E에서 계속 진행 
5. E와 연결된 G A*값 = 7 < F A*값(9) -> 도착

이와 같이 진행을 했을 때 최단거리를 보장 받으며 다익스트라와의 차이점은

F-G 경로의 값을 계산하지 않았다는 것이다.

위 그래프는 간단한 그래프라서 그렇게 효율이 나오는 것처럼 보이진 않지만 그래프가 복잡해지면 더욱 높은 효과를 발휘한다.