[알고리즘] A* (에이 스타) 알고리즘

오늘 포스팅할 알고리즘은 A* (에이 스타)알고리즘이다,

A*(에이 스타)는 그래프의 최단 경로 문제를 해결하는 알고리즘으로 다익스트라 알고리즘을 발전시킨 것 입니다.

 

다익스트라 알고리즘은 시작점에서 각 정점에 이르는 최단 경로를, 시작점에서 가까운 정점부터 결정한다. 그러다 보니 종점에서 멀어지는 방향에 있는 정점들의 최단 경로도 결정하게 되는데 이 계산은 결국 사용되지 않기 때문에 불필요한 계산이 된다. A*는 이를 방지하기 위한 알고리즘이다.

 

다익스트라 알고리즘을 잘모른다면 아래의 포스팅을 보고 오는 것을 추천한다.

[알고리즘] 다익스트라 알고리즘 (Dijkstra Algorithm)

 

 

현재 차근차근 해보자는 생각에 기초 공부를 하는 중이다. 좀 더 자세한 내용은 다른 글에 작성하거나 추후 글을 수정하는 방향으로 작성해 보겠다. 

틀린 내용이 있거나 궁금한게 있다면 편하게 댓글 남겨주시면 감사하겠습니다!

---

📝 개념

A*(에이 스타) 알고리즘은 그래프의 최단 경로 문제를 해결하는 알고리즘으로 다익스트라 알고리즘에서 발전시킨 알고리즘이다.

다익스트라 알고리즘은 불필요한 최단 경로도 결정하게 되는데 이를 방지하기 위해 A*는 미리 추정 비용을 힌트로 설정하여 이 정보를 이용함으로써 불필요한 탐색을 생략하도록 개선되었다.

 

A* 알고리즘

위 미로의 최단 경로를 먼저 다익스트라 알고리즘으로 풀어 보겠다.

S가 시작점이고 G가 종점이 된다.

 

A* 알고리즘

미로는 한 칸이 하나의 정점이고 각 정점 간 거리(비용)가 1인 그래프로 볼 수 있다.

이를 전제로 다익스트라 알고리즘으로 최단경로를 찾아보겠다.

 

다익스트라 알고리즘

다익스트라 알고리즘으로 최단 경로를 구하면 위 그림과 같은 결과를 얻는다.

각 칸의 숫자는 시작점에서 해당 칸까지의 비용이다. 하늘색과 연두색은 탐색한 장소이며, 그 중 연두색 칸은 S에서 G까지의 최단 경로이다.

 

다익스트라 알고리즘

다익스트라 알고리즘에서는 시작점에서부터의 비용만 고려하여 다음에 이동할 정점을 결정한다.

따라서 화살표 방향, 즉 목적지에서 멀어지는 경로도 탐색하게 된다.

 

A* 알고리즘

A*는 시작점에서부터의 비용뿐만 아니라 현재 위치에서 목적지까지의 추정 비용을 함께 고려하여 탐색한다.

이 추정 비용은 자유롭게 설정할 수 있다. 여기선 오른쪽 아래에 있는 목적지와의 직선 거리를 반올림한 값을 설정하겠다.

 

위 미로에 표시한 것 처럼 사람의 손으로 미리 설정한 추정 비용을 휴라스틱 비용이라 한다. 사전에 알고 있는 정보를 바탕으로 적잘한 추정 비용을 설정하여 힌트를 제공하면 더 효율적으로 탐색할 수 있다. 여기서는 목적지의 위치는 알지만, 가는 길을 모른다는 전제로 직선 거리를 이용했다.

 

A* 알고리즘

그러면 A*로 문제를 해결해 보겠다.

먼저 시작점을 탐색 완료로 설정한다. 탐색을 완료한 칸은 하늘색으로 표시해두었다.

 

A* 알고리즘

시작점에서 이동할 수 있는 점의 비용을 각각 계산한다. 비용은 해당 위치로 이동하기 위한 비용(왼쪽 아래 값)과 휴라스틱 비용(오른쪽 아래 값)의 합으로 계산한다.

 

각 지점에 대해 시작점에서부터 실제로 걸린 비용과 목적지까지의 추정 비용을 더하면 시작점에서 목적지까지의 추정 비용을 계산한것 이다.

 

A* 알고리즘

비용이 제일 작은 점을 하나 선택한다. 선택한 점은 핑크색으로 표시하겠다.

 

A* 알고리즘

선택한 점을 탐색 완료한 것으로 처리한다.

 

A* 알고리즘

탐색 완료한 점에서 이동할 수 있는 점들의 비용을 게산한다.

 

A* 알고리즘

비용이 제일 작은 점을 하나 선택한다.

 

A* 알고리즘

선택한 점을 탐색 완료한 것으로 처리한다. 목적지에 도착할 때까지 동일한 작업을 반복한다.

 

A* 알고리즘

탐색 중...

 

A* 알고리즘

탐색이 끝났다. 다익스트라 알고리즘과 비교하여 훨씬 효율적으로 미로를 탐색한 것을 볼 수 있다.

목적지에 가까워지지 않는 방향으로는 거의 탐색하지 않음을 알 수 있다.

---

✔️ 추가 내용

A* 알고리즘은 각 지점에서 목표까지의 거리에 대해 정확하지 않더라도 힌트가 주어진 경우에 유용하다.

만약 그런 정보가 전혀 없다면, A*를 사용하면 안된다.

 

휴라스틱 비용과 실제 비용이 가까우면 가까울수록 검색 효율이 높다. 반대로 실제 비용과 동떨어진 값을 휴라스틱 비용으로 사용하면 아예 정답을 찾을 수 없을 수도 있다.

 

참고로, 휴라스틱 비용이 실제 비용보다 낮게 설정 되어 있으면 바른 답을 찾는 것이 보장된다. 단, 설정에 따라 검색 효율이 나빠질 수 있다.

 

A* 알고리즘의 활용 사례로는 게임 프로그래밍에서 플레이어를 쫓는 적의 움직임을 계산할 때 사용 되는 경우가 있다.

하지만 계산량이 많기 때문에 게임 전체의 진행 속도에 나쁜 영향을 미칠 수 있다. 이를 사용하려면 다른 알고리즘과 조합하거나 사용하는 장면을 제한하는 등의 방법을 선택해야한다.

 

---

참고 자료

그림으로 이해하는 알고리즘 : 이시다 모리테루, 미야자키 슈이츠