A* 알고리즘이란?
A* 알고리즘은 그래프의 최단 경로 문제를 푸는 알고리즘으로, 다익스트라 알고리즘을 발전시킨 알고리즘입니다. 다익스트라 알고리즘은 시작 지점에 가까운 정점부터 순서대로 결정하기 때문에 종점에서 멀어지는 방향의 정점의 최단 경로도 결정해나가지만, 이것은 결국 쓰이지 않기 때문에 불필요합니다.
A* 알고리즘 미리 추정 코스트를 힌트로 설정해서, 그 정보를 이용하는 것으로 불필요한 탐색을 줄이도록 개량된 것입니다.
설명
그럼 이 미로의 최단 경로를 우선 다익스트라 알고리즘으로 해결해 봅시다.
S는 Start, G는 Goal을 뜻합니다.
미로는 각 정점 간의 코스트가 1인 그래프라고 해석할 수 있습니다. 이것을 전제로 다익스트라 알고리즘을 이용해 최단거리를 구해봅시다.
다익스트라 알고리즘으로 최단 경로를 구하면 이러한 결과가 됩니다. 각 칸의 숫자는 시작 지점으로부터의 코스트입니다. 파란색과 주황색은 탐색한 장소로, 그중 주황색은 S부터 G까지의 최단 경로를 나타냅니다.
다익스트라 알고리즘에서는 시작점부터의 코스트를 고려해서 다음으로 갈 정점을 결정합니다.
그래서 화살표가 가리키고 있는 경로도 목표 지점으로부터 멀어지는 것을 고려하지 않고 탐색하게 됩니다.
A* 알고리즘에서는 시작점부터의 코스트뿐만 아니라 현시점에서 목표 지점까지의 추정 코스트도 함께 고려해서 탐색합니다. 이 코스트는 자유롭게 설정할 수 있으며, 여기선 오른쪽 아래에 있는 목표 지점으로부터의 직선 경로를 반올림한 값을 이용하도록 합니다.
이처럼 사람이 미리 설정하는 추정 코스트를 휴리스틱 코스트(Heuristic cost)라고 합니다.
이번에는 A* 알고리즘을 사용해 보겠습니다. 우선 시작 지점을 탐색 완료로 설정합니다.
시작점으로부터 갈 수 있는 칸의 코스트를 각각 계산합니다. 코스트는 그곳에 도달할 때까지의 실제 코스트와 휴리스틱 코스트의 합계로 계산합니다.
코스트가 가장 낮은 칸을 하나 선택합니다.
선택한 칸을 탐색 완료 상태로 표시합니다.
탐색을 완료한 칸에서 갈 수 있는 칸의 코스트를 계산합니다.
코스트가 가장 낮은 칸을 하나 선택합니다.
선택한 칸을 탐색 완료 상태로 표시합니다. 이후로는 같은 작업을 목표 지점에 도착할 때까지 반복합니다.
탐색중…
탐색이 종료되었습니다. 다익스트라 알고리즘보다 효율적으로 미로를 탐색할 수 있었습니다. 목표 지점에서 멀어지는 방향의 칸은 거의 탐색되지 않은 것을 알 수 있습니다.
해설
A* 알고리즘은 각 지점에서 목표 지점까지의 거리에 대해, 정확하지는 않지만 어떠한 힌트가 있는 경우에 유용합니다. 물론 그런 정보를 전혀 얻을 수 없는 상황도 있지만, 그 경우에는 사용할 수 없습니다.
휴리스틱 코스트는 현 지점으로부터 목표 지점까지의 실제 코스트에 가까울수록 탐색 효율이 좋아집니다. 반대로, 실제 코스트와 동떨어진 코스트를 사용하면 다익스트라 알고리즘 보다 오히려 효율이 나빠지는 경우가 있습니다. 그리고 그보다 더욱 동떨어진 코스트를 사용하면, 올바른 정답을 얻을 수 없을 수도 있습니다.
또한, 휴리스틱 코스트가 실제 코스트 이하로 설정되어 있으면 올바른 정답이 나오는 것은 보장되어 있습니다(단, 설정에 따라 탐색 효율이 나빠지는 경우도 있습니다).
활용 예시
A* 알고리즘은 게임 프로그래밍에서 플레이어를 쫓는 적을 구현할 때 자주 사용됩니다.
하지만 계산량이 많아서 게임 성능에 악영향을 끼칠 수도 있습니다. 개선된 알고리즘을 사용하거나, 사용하는 장면을 추려내는 등의 궁리가 필요합니다.
마치며
지금까지 A* 알고리즘의 동작을 알아봤습니다. 다음 포스트에서는 Python으로 직접 A* 알고리즘을 작성해 보겠습니다.
좋은 글 감사합니다!