A* 알고리즘(A star)

1. A* 알고리즘 이란?

• 최단 경로 탐색 알고리즘

• 목적지를 정확하게 알고 있을 때 사용 가능

• 특징

  • 노드는 4개의 상태 중 하나로 표시(empty, block, close, open)

  • 휴리스틱(heuristic)을 사용하여 다음 노드를 선택

2. 과정

• Step 1 ~ 3

  • Step 1 : 도착한 Node는 Close state

  • Step 2 : 주변 Node 탐색, State에 따라

    • Empty => Open State

    • Block => Nothing

    • Close => Nothing

    • Open =>

      • G 값이 작다 => 부모 Node 바꿈

      • G 값이 크다 => Nothing

  • Step 3 : Open Node 중, 최소 F 값 Node로 이동

    • G : 출발지에서 이동한 거리

    • H : 도착지까지 남은 거리(휴리스틱 ex) Manhattan distance)

    • F = G + H

• 종료 조건

  • Step 1 : 도착한 Node가 도착지점이면 종료(성공)

  • Step 3 : Open Node가 한 개도 없다면 종료(실패, 도착 불가능)

3. 휴리스틱

• 가용한 정보를 기반으로 각 분기 단계에서 어느 한 분기를 선택하기 위해 사용하는 다양한 탐색 알고리즘의 대안 함수

• 최단 거리에서 사용할 수 있는 휴리스틱 함수

  • Manhattan distance

    • y 좌표의 차의 절대값 + x 좌표의 차의 절대값을 이용하는 경우

  • Diagonal distance

    • x, y 좌표 중 최대값을 사용하는 경우

  • Euclidean distance

    • 피타고라스 정리를 활용하는 경우

비교

• 장애물이 없을 때(Dijkstra, Greedy Best-First-Search, A* 순)

• 장애물이 있을 때(Dijkstra, Greedy Best-First-Search, A* 순)

출처

• A* 알고리즘

• 휴리스틱