용어 목록 > 에이스타알고리즘 (A* Algorithm)

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

쉽게 풀면

지금까지 온 거리와 목표까지 대략 남은 거리를 더해서, 가장 유망해 보이는 길부터 우선적으로 탐색해 나가는 길찾기 방법입니다.

왜 중요한가

격자 지도나 로드맵 위에서 최적 경로를 보장하면서도 다익스트라보다 훨씬 적은 노드만 펼치므로, 이동로봇의 전역경로계획 기본값으로 가장 널리 쓰입니다. 새 계획 알고리즘을 제안하는 논문은 거의 예외 없이 A*를 기준선으로 두고 경로 길이와 탐색 노드 수를 비교합니다.

어떤 절차인가

A*는 시작 노드에서 목표까지 가는 최소 비용 경로를 찾는 탐색 알고리즘입니다(Hart 외, 1968). 각 노드 n마다 f(n) = g(n) + h(n)을 계산합니다. g(n)은 시작에서 n까지 실제로 든 비용, h(n)은 n에서 목표까지의 추정 비용(휴리스틱)입니다.

1. 시작 노드를 열린 목록에 넣는다.
2. f가 가장 작은 노드를 꺼내 닫힌 목록으로 옮긴다.
3. 그 노드가 목표면 끝난다. 아니면 이웃 노드의 g를 갱신하고(더 싼 경로를 찾으면), 열린 목록에 넣는다.
4. 2~3을 반복한다.

h가 항상 0이면 다익스트라 알고리즘과 같습니다.

언제 쓰고 무엇을 얻나

h가 허용적(admissible), 곧 실제 남은 비용을 절대 과대평가하지 않으면 A*는 최단 경로를 보장합니다. 또 h가 일관적(consistent)이면 한 번 닫힌 노드를 다시 열 필요가 없습니다(Dechter & Pearl, 1985의 최적성 논의 참조). 격자에서 상하좌우 이동 비용이 1일 때 맨해튼 거리가 이런 휴리스틱의 대표입니다.

작은 예(코드로 실행). 9행×10열 격자(#은 벽)에서 S에서 G까지 간다고 합시다.

..........
..####....
..#..#....
..#..#.##.
..#..#..#.
S.#..####.
..#.......
..####.##.
........#G

같은 최단 길이를 더 적은 노드로 찾는 것이 휴리스틱의 이점입니다. 맨해튼×2는 과대평가하는 비허용 휴리스틱이어서 최적성이 보장되지 않는데, 이 격자에서는 우연히 최적을 찾았습니다. 노드 수는 동률일 때의 처리 순서(여기서는 g, 좌표 순)에 따라 조금 달라질 수 있습니다.

논문에는 이렇게 적는다

• 그래프(격자 크기, 이동 방향 4방향/8방향, 비용 정의)와 사용한 휴리스틱을 명시하고, 허용성·일관성을 증명하거나 근거를 제시합니다.
• 성능은 확장한 노드 수, 실행 시간, 메모리, 경로 길이(최적 대비 비율)로 비교합니다. 비교 대상은 다익스트라, 가중 A*, JPS, D* Lite 같은 변형으로 합니다.
• 휴리스틱을 부풀려 속도를 얻으면(가중 A*) 최적성이 깨지므로 그 점을 밝혀야 합니다.

논문에서는 이렇게 쓰입니다

실제 논문에서

이 용어를 직접 쓴 국내 논문 문장을 아직 수집하지 못했습니다. 수집되는 대로 출처와 함께 싣겠습니다.

예시 문장

아래는 용어의 쓰임을 보여 주려고 만든 예시로, 실제 논문에서 가져온 문장이 아닙니다.

g(n)은 시작점부터 현재까지 실제로 온 비용, h(n)은 목표까지 남은 거리를 추정한 값으로, 이 둘을 더해 가장 효율적인 다음 노드를 선택한다는 뜻입니다.

목표까지 남은 거리 추정치의 비중을 늘리면 계산은 빨라지지만 항상 최단 경로를 보장하지는 못한다는 절충 관계를 보여줍니다.

조금 더 깊게 보면

최적성은 휴리스틱이 실제 비용을 과대평가하지 않는 허용적 조건을 만족할 때만 성립하며, 이를 어기면 더 빨라지지만 최단 경로를 놓칠 수 있습니다. 환경이 바뀔 때마다 처음부터 다시 계산해야 하는 점이 약점이어서, 부분 변경만 재계산하는 D*가 동적 환경용으로 따로 발전했습니다.

A*는 각 노드마다 시작점까지의 실제 비용 g(n)과 목표까지 남은 비용의 추정치 h(n)을 더한 f(n)이 가장 작은 노드부터 확장하는데, h(n)이 실제 비용을 절대 과대평가하지 않는 허용적 조건을 만족하면 처음 목표에 도달했을 때의 경로가 곧 최단 경로임이 수학적으로 보장된다.

격자 지도에서는 유클리드 거리나 대각선 이동을 고려한 체비쇼프 거리가 흔한 휴리스틱으로 쓰이며, 어떤 거리 함수를 쓰느냐에 따라 확장되는 노드 수와 계산 시간이 달라진다.

주의할 점

휴리스틱 함수가 허용성을 만족하지 못하면 최적 경로를 보장할 수 없으므로 휴리스틱 설계가 매우 중요합니다.

휴리스틱 가중치를 키워 더 빠르게 계산하는 변형(가중 A*)을 쓰면 탐색 속도는 빨라지지만 더 이상 최단 경로를 보장하지 못해, 경로 품질과 계산 시간 사이의 명시적 절충이 필요하다.

헷갈리기 쉬운 용어

참고 문헌

1. Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100–107.
2. Dechter, R., & Pearl, J. (1985). Generalized best-first search strategies and the optimality of A*. Journal of the ACM, 32(3), 505–536.
3. Russell, S., & Norvig, P. (2020). Artificial Intelligence: A Modern Approach (4th ed.). Pearson.

표의 기준값은 위 문헌에 근거한 관례이며, 분야·학술지마다 다른 기준을 쓸 수 있습니다.