나만의 작은 도서관
[알고리즘] A* 알고리즘(A star algorithm) 본문
A* 알고리즘(A star algorithm)이란?
A* 알고리즘은 가중치가 있는 그래프(weighted graph)에서 시작점과 도착점이 주어졌을 때 최단 거리를 구하는 휴리스틱 기반의 알고리즘이다. 다익스트라 알고리즘에서 변형된 알고리즘이며, 동작 방식 또한 유사하지만 특정 지점까지의 추정 거리를 고려한다는 점에서 다르다.
A* 알고리즘은 다익스트라 알고리즘보다 빠르게 두 정점 간의 최단 경로를 구해낸다는 점 때문에 게임 내에서 길 찾기 기능으로 사용되며, 대표적으로 스타크래프트가 A* 알고리즘을 사용하였다. (특정 게임에서는 A* 알고리즘마저도 느려 A* 알고리즘보다 빠른 JSP 알고리즘을 사용하기도 한다.)
A* 알고리즘의 구성 요소
- g(n): 시작점에서 현재 정점까지의 실제 경로 비용.
- h(n): 현재 정점에서 도착점까지의 휴리스틱(추정) 비용. 이 값은 도착점에서 얼마나 가까운지를 추정하는 함수로, 문제에 따라 다르게 설정된다. 예를 들어, grid가 주어졌을 경우는 맨해튼 거리, 그래프가 주어졌을 경우는 유클리드 거리가 h(n)이 될 수 있다.
- f(n) = g(n) + h(n): 현재까지의 실제 경로 비용과 남은 추정 거리를 더한 값으로, A*는 이 값을 기준으로 최적 경로를 탐색한다.
- 열린 목록(Open List): 탐색한 정점이지만 거리 갱신이 될 여지가 있어 아직 닫히지 않은 정점들의 목록. 다익스트라의 인접 정점 집합과 동일하다.
- 닫힌 목록(Close List): 거리 갱신이 완료되어 닫힌 정점들의 목록. 다익스트라의 방문 정점 집합과 동일하다.
동작방식
동작방식은 다익스트라 알고리즘의 동작방식을 조금 바꿔주면 되는데, 1)우선순위 큐의 정렬 기준을 현재까지의 거리만 고려하는 것이 아닌 현재까지의 거리(g(n)) + 도착점까지의 남은 추정 거리(h(n)) 로 바꿔주고, 2) 도착점에 도착하면 작업을 중지하면 된다.
아래 예시에서 이동 방향은 8방향이며, 상하좌우 움직임은 10, 대각선 움직임은 14의 거리를 갖는다.(아래 예시는 https://www.youtube.com/watch?v=-L-WgKMFuhE에서 가져왔습니다)
1. 초기화
- 시작점을 열린 목록에 넣고, f(n) 값을 계산한다. 사각형 왼쪽 위의 숫자는 g(n), 오른쪽 위의 숫자는 h(n), 아래의 숫자는 이 둘의 합인 f(n)이다.
2. 닫힌 목록으로 이동할 정점 선택
- 열린 목록에서 f(n)이 가장 작은 정점을 선택한다. 처음에는 시작점이 선택된다.
3. 닫힌 목록으로 이동 및 열린 목록에 정점 추가
- 선택한 정점을 닫힌 목록으로 이동시키고, 열린 목록에 이웃 정점을 추가한다. 만약 이미 추가된 정점이라면, 추가하는대신 둘 중 f(n)이 작은 경로로 갱신한다.
4. 2~3번 과정을 반복
- 도착점에 도달할 때까지 2~3번 과정을 반복한다.
5. 최종 결과
- 최종적으로 도착점으로 가는 최단 거리를 구하게 된다.
구현 코드
// 추후 추가 예정
최단 경로 추적하기
다익스트라 알고리즘과 동일한 방식으로 최단 경로를 추적할 수 있다. A* 알고리즘에서 최단 경로를 추적하려면, 각 정점에 도달하기 직전의 경로 정보를 저장하면된다. 이를 위해 부모(이전) 정점을 저장하는 배열을 추가하고, 최단 경로를 구할 때 이 정보를 이용해 경로를 추적하면 된다. 코드는 아래와 같다.
// 추후 추가 예정
짚고 넘어가야 할 점
admissible하다.
A* 알고리즘은 admissible하다. admissible하다는 것은 알고리즘이 사용하는 휴리스틱 함수가 결코 실제 비용을 과대평가하지 않는다(실제 거리를 초과하지 않는다는 의미)는 것을 의미하는데, 이는 A* 알고리즘이 항상 최적의 경로를 보장할 수 있는 중요한 조건이다. A* 알고리즘에서 사용되는 휴리스틱 함수인 맨해튼 거리와 유클리드 거리를 보면 왜 admissible한 지 알 수 있다.
맨해튼 거리와 유클리드 거리
- 맨해튼 거리는 그리드 기반 환경에서 정점 간의 거리 추정에 사용된다. 이는 한 지점에서 다른 지점까지 상하좌우로만 이동할 수 있는 상황에서 유효하다.
- 맨해튼 거리는 실제 거리보다 결코 클 수 없으므로 admissible하다.
- 유클리드 거리는 직선 거리를 기반으로 한 추정치이다. 이는 장애물이 없을 때 유효하다.
- 마찬가지로 실제 거리보다 결코 클 수 없으므로 admissible하다.
시간복잡도?
A* 알고리즘은 휴리스틱 알고리즘이다. 휴리스틱 함수는 완벽하지 않기 때문에 문제의 특성에 따라 휴리스틱 함수(h(n))의 품질에 따라 성능이 좌지우지된다. 따라서, 휴리스틱 함수가 들어가는 알고리즘은 정확한 시간복잡도를 구하기 어렵다. 대신, 아래 영상들을 보고 다익스트라 알고리즘보다 얼마나 효율적인지 알 수 있다.
A* vs 다익스트라 영상
https://www.youtube.com/watch?v=g024lzsknDo
https://www.youtube.com/watch?v=RYdBcnSiwag
참고자료
https://namu.wiki/w/A*%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
http://www.gisdeveloper.co.kr/?p=3897
https://www.youtube.com/watch?v=-L-WgKMFuhE&list=PLFt_AvWsXl0cq5Umv3pMC9SPnKjfp9eGW
'C++ > 알고리즘' 카테고리의 다른 글
| [알고리즘] Union-Find 알고리즘 (0) | 2024.10.29 |
|---|---|
| [알고리즘] 프림 알고리즘(Prim Algorithm), 크루스칼 알고리즘(Kruskal Algorithm) (0) | 2024.10.26 |
| [알고리즘] 벨만-포드 알고리즘(Bellman-Ford Algorithm) (0) | 2024.10.23 |
| [알고리즘] 다익스트라 알고리즘(Dijkstra Algorithm) (0) | 2024.10.19 |
| [알고리즘] 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm) (0) | 2024.10.16 |
