A* 알고리즘

오늘은 A*알고리즘의 대해 공부하겠습니다.

---

A*

최단 경로 탐색 알고리즘 중 A* 알고리즘은 다익스트라 알고리즘의 확장 개념으로 만들어진 알고리즘입니다.

주로 게임에서 플레이어를 목표지점으로 이동시킬 때 사용하는 알고리즘으로

대표적인 그래프 탐색 알고리즘들과 A*의 차이점은

BFS 는 가중치가 없는 그래프에서 최단 경로를 찾는 완전 탐색 알고리즘

다익스트라는 가중치 그래프에서 시작 노드를 기준으로 모든 노드까지의 최단거리를 구하는 그리디 알고리즘입니다.

반면 A*는 가중치 그래프에서 시작 노드에서 목표 노드까지의 최단 경로만 구하려 하는 그리디 알고리즘 입니다.

출처 : https://mawile.tistory.com/239

---

A*의 개념

A* 알고리즘은 휴리스틱 추정값을 통해 알고리즘을 개선할 수 있습니다. 이러한 휴리스틱 추정값을 어떤 방식으로 제공하느냐에 따라 얼마나 빨리 최단 경로를 파악할 수 있느냐가 결정됩니다.

 

휴리스틱 : 경험에 기반하여 문제를 해결하거나 학습하거나 발견해 내는 방법

A* 알고리즘의 의사 코드는 다음과 같습니다.

 

1. P = 시작점
2. P에 f, g, h 할당
3. Open 리스트에 P 넣기
4. B = Open 리스트에서 가장 낮은 f 값을 가진 노드
    a. B가 목표점이면, 경로 완성
    b. Open 리스트가 비었으면, 목표점까지 경로가 존재하지 않음
5. C = B에 연결된 노드
    a. C에 f, g, h 값 할당
    b. Open/Close 리스트에서 C가 있는지 체크
       1. 있으면, 더 낮은 f 값으로 경로 업데이트
       2. 없으면, C를 Open 리스트에 넣기
    c. 5번으로 돌아가서 B에 연결된 모든 노드를 대상으로 진행
6. 4번으로 돌아감

g값은 출발점부터 현재 노드 위치까지 거리이고, h는 현재 노드 위치부터 목표점 까지의 휴리스틱한 거리입니다.
즉 일관성있는 거리 측정 기준만 있으면 h는 구현마다 다를 수 있습니다. f는 g+h값 최종값입니다.

 

또한 Open리스트 Close리스트는 O, C로 표현되며 Open리스트는 최단 경로를 분석하기 위한 상태 값들이 계속 갱신되며
Close리스트는 처리가 완료된 노드를 담아 두기 위한 목적으로 사용됩니다.
휴리스틱 추정인 h는 보통 한 노드에 갔을때 직선상을 목적지에 거리를 그려 저장을 합니다.
이 값을 g와 더해 최종적인 F를 open리스트에 하나씩 넣어 비교하여 최소 F값을 닫는 리스트(close)에 넣어 다시 연산을 합니다.

이렇게 반복하다 보면 close 리스트에 골인 점이 나옵니다.

도착 노드가 가지고 있던 부모 노드를 추적하여 출발노드를 찾습니다.