A* 알고리즘

수치해석 게임 개발 마지막 수정: 2026-08-23 04:48:37

1. 개요[편집]

A* 알고리즘 A* search algorithm
발표	Hart, Nilsson, Raphael (1968)
평가함수	$f(n) = g(n) + h(n)$
최적성 조건	허용적(admissible) $h \le h^{*}$
재확장 없음 조건	일관적(consistent) $h(u) \le w(u,v) + h(v)$
퇴화	$h \equiv 0$ 이면 다익스트라
주 무대	격자·내비메시·경로 계획·퍼즐 탐색

다익스트라는 사방으로 퍼진다. A*는 목적지 쪽을 힐끗 보고 그쪽으로만 퍼진다. 힐끗 보는 값이 거짓말만 안 하면, 답은 똑같이 최적이다.

A* 알고리즘(A-star)은 시작점부터의 실제 비용 $g(n)$ 과 목표까지의 추정 비용 $h(n)$ 을 더한 $f(n) = g(n) + h(n)$ 이 가장 작은 노드부터 확장하는 최선 우선 그래프 탐색 알고리즘이다. 1968년 스탠퍼드 연구소에서 로봇 셰이키(Shakey)의 경로를 계획하려던 하트·닐슨·라파엘이 발표했다.¹

이 알고리즘의 지위는 특이하다. 순수 알고리즘으로 보면 다익스트라 알고리즘에 항 하나를 더한 것에 불과한데, 게임 AI·로보틱스·퍼즐 탐색에서 사실상 유일한 표준이 되었다. 이 문서는 그 “항 하나”가 정확히 무엇을 요구하고 무엇을 보장하는지 — 허용성과 일관성의 차이, 그리고 그 차이를 무시했을 때 터지는 재확장 문제 — 를 중심에 둔다. 그래프 탐색의 일반론과 힙 구현은 다익스트라 알고리즘과 우선순위 큐 쪽이 본진이므로 여기서는 되풀이하지 않는다.

2. 다익스트라에서 A*까지[편집]

세 알고리즘이 사실 같은 루프의 세 파라미터화다.

알고리즘	우선순위 키	성질
너비 우선 탐색	간선 개수	단위 가중치 전용
다익스트라 (균일비용)	$g(n)$	최적, 사방으로 등거리 확장
탐욕 최선우선	$h(n)$	빠르지만 최적성 없음
A*	$g(n) + h(n)$	$h$ 가 허용적이면 최적

$h \equiv 0$ 이면 A*는 그대로 다익스트라이고, $h = h^{*}$ (참값)면 확장 없이 최적 경로를 곧장 따라간다. 그 사이 어딘가가 실전이다. 흔히 “다익스트라 = 균일비용 탐색”이라 쓰지만 미묘한 차이가 있다 — 균일비용 탐색은 목표를 꺼낼 때 종료하고, 원조 다익스트라는 모든 정점의 최단거리를 계산한다. 목표가 하나면 꺼낼 때 멈추면 되고, 목표가 여럿이거나 미리 모르면(가장 가까운 회복 아이템 찾기) 휴리스틱을 만들 수 없으므로 그냥 다익스트라를 돌리는 것이 정답이다.

3. 허용성과 일관성 — 자주 헷갈리는 두 조건[편집]

허용성(admissible): 모든 노드에서 $h(n) \le h^{*}(n)$ , 즉 절대 과대평가하지 않는다.

일관성(consistent, 단조성): 모든 간선 $(u,v)$ 에서

h(u) \le w(u,v) + h(v), \qquad h(\text{goal}) = 0

즉 휴리스틱 자체가 삼각부등식을 만족한다. 일관적이면 허용적이다(목표까지의 최적 경로를 따라 귀납하면 나온다). 역은 성립하지 않는다.

두 조건이 보장하는 것이 다르다.

허용적이기만 하면: A*가 반환하는 경로는 최적이다. 단, 어떤 노드가 확장된 시점의 $g$ 가 최적이라는 보장은 없다.
일관적이면: $f$ 가 어떤 경로를 따라가도 감소하지 않고(단조), 노드를 꺼내는 순간 $g(n) = g^{*}(n)$ 이며, 각 노드는 정확히 한 번만 확장된다.

일관적일 때 A*가 정확히 무엇인지도 깔끔하게 말할 수 있다. 간선을 재가중해

w'(u,v) = w(u,v) - h(u) + h(v) \;\ge\; 0

으로 놓으면 $w'$ 은 비음수이고, 경로 전체의 $w'$ 합은 원래 비용에서 $h(\text{start})$ 만 빠진 값이라 최단경로 집합이 보존된다. 즉 일관적 휴리스틱을 쓴 A*는 재가중된 그래프 위의 다익스트라 그 자체다. 최단경로 이론에서 이 재가중 장치를 존슨 퍼텐셜이라 부르며, 일관성은 곧 ” $h$ 가 유효한 퍼텐셜”이라는 뜻이다.

3.1. 재확장 문제[편집]

허용적이지만 일관적이지 않은 $h$ 를 쓰면, 이미 닫힌(closed) 노드로 더 짧은 경로가 뒤늦게 발견될 수 있다. 그러면 그 노드를 다시 열어(reopen) 후손 전체를 다시 전파해야 하고, 여기서 비용이 폭발한다. 마르텔리(1977)는 노드 $N$ 개짜리 그래프에서 A*가 $\Omega(2^N)$ 번 확장하도록 만드는 예를 구성했다. 최적해는 여전히 나오지만 지수 시간이 걸린다는 것이 이 문제의 성격이다.

대응은 세 가지다. (1) 애초에 일관적인 휴리스틱만 쓴다 — 격자의 유클리드/옥타일 거리, 유클리드 공간의 직선거리는 전부 일관적이라 실무에서는 이게 대부분이다. (2) 재개방을 허용하되 회수를 감시한다. (3) 경로최대화(pathmax) 같은 보정으로 $h$ 를 국소적으로 끌어올려 일관성을 회복시킨다 — 자식 $v$ 에 대해 $h(v) \leftarrow \max\big(h(v),\, h(u) - w(u,v)\big)$ . 패턴 데이터베이스처럼 여러 허용적 휴리스틱의 최댓값을 쓰는 경우 비일관이 생기기 쉬워서, 양방향 보정(BPMX)을 같이 쓴다.

3.2. 얼마나 효율적인가[편집]

데흐터와 펄(1985)의 결과가 A*의 명성을 뒷받침한다. 일관적 $h$ 를 쓰는 A*는, 같은 정보를 가진 어떤 허용적 알고리즘보다도 확장 노드가 많지 않다(동점 처리를 제외하면). 조금 더 실용적인 형태로는 이렇다 — $C^{*}$ 를 최적 비용이라 할 때, $f(n) < C^{*}$ 인 노드는 어떤 최적 알고리즘이든 반드시 확장해야 하고, A*는 정확히 그것들과 $f = C^{*}$ 인 것 일부만 확장한다.² 그래서 실무 최적화의 절반이 동점 처리다. $f$ 가 같으면 $g$ 가 큰 쪽(목표에 더 가까이 간 쪽)을 먼저 꺼내도록 키를 $(f, -g)$ 사전식으로 주는 것만으로 확장 수가 몇 배 줄어드는 일이 흔하다.

4. 격자 위의 휴리스틱[편집]

게임에서 A*를 쓰는 무대는 대개 정사각 격자다. 여기서 휴리스틱을 잘못 고르면 최적성이 조용히 깨진다.

4방향 이동: 맨해튼 거리 $h = |dx| + |dy|$ . 정확히 자유공간 거리라 일관적이고 가장 강하다.
8방향 이동, 대각선 비용 $\sqrt{2}$ : 옥타일 거리를 쓴다.

h = (|dx| + |dy|) + (\sqrt{2} - 2)\,\min(|dx|, |dy|)

대각선으로 갈 수 있는 만큼 가고 나머지를 직진하는 비용 그대로다. 자유공간에서 참값이므로 가장 조인 허용적 휴리스틱.

8방향 이동, 대각선 비용 1: 체비쇼프 거리 $h = \max(|dx|, |dy|)$ .
유클리드 거리: 어떤 격자에서도 허용적이고 일관적이지만, 8방향 격자에서는 옥타일보다 작다(과소평가가 심하다). 최적해는 나오지만 확장 노드가 눈에 띄게 늘어난다.

여기서 흔한 사고가 맨해튼 거리를 8방향 격자에 그대로 쓰는 것이다. 대각선 한 칸의 실제 비용이 $\sqrt{2}$ 인데 맨해튼은 2로 세므로 과대평가가 되어 허용성이 깨지고, 경로가 최적이 아니게 된다. 반대로 대각선 비용을 1로 두고 맨해튼을 쓰면 훨씬 심하게 과대평가한다. “격자 A*가 이상한 길로 간다”는 버그의 상당수가 이 조합 실수다.

그리고 격자 A*에는 근본적인 한계가 하나 있다. 이동 방향이 8개로 제한되므로 격자를 아무리 잘게 쪼개도 경로 길이가 유클리드 최단거리로 수렴하지 않는다(8방향의 경우 최악 약 8.24% 과대). 이 이방성 오차의 정확한 계산은 다익스트라 알고리즘 문서에 정리돼 있고, 연속 영역에서 이를 없애는 것이 고속 행진법이다.

5. 변종들[편집]

가중 A*(Weighted A*)는 $f = g + \varepsilon h$ ( $\varepsilon > 1$ )로 휴리스틱을 부풀린다. 허용성이 깨지지만 대신 해가 최적의 $\varepsilon$ 배 이내라는 보장이 남고, 탐색이 목표 쪽으로 훨씬 공격적으로 쏠려 확장 수가 급감한다.³ $\varepsilon$ 을 크게 시작해 시간이 허락하는 만큼 줄여 가며 해를 개선하는 애니타임 변종(ARA*)이 로보틱스에서 널리 쓰인다. 실시간 게임에서는 “최적 경로”보다 “16 ms 안에 나온 그럴싸한 경로”가 언제나 이긴다.

IDA*(Korf 1985)는 메모리를 포기 대신 시간을 낸다. $f$ 임계값을 정해 깊이우선으로 훑고, 임계값을 넘어선 최소 $f$ 로 임계값을 올려 다시 훑는다. 메모리가 경로 깊이에 선형이라 오픈 리스트가 메모리를 다 먹는 상황(15퍼즐·루빅스 큐브)에서 유일한 선택지다. 대가는 같은 노드를 여러 번 다시 확장하는 것인데, 분기수가 크면 마지막 반복이 지배해 상수 배 손해로 끝난다. 비슷한 발상의 RBFS·SMA*도 같은 계열.

JPS(Jump Point Search, Harabor·Grastien 2011)는 균일비용 8방향 격자에 특화된 대칭성 제거다. 장애물이 없는 넓은 영역에서는 같은 길이의 경로가 조합적으로 무수히 많은데(대각선을 언제 넣느냐 차이), JPS는 그중 정규 대표 하나만 남기고 나머지를 가지친다. 방향을 따라 “점프”하며 강제 이웃(forced neighbor)이 생기는 지점만 오픈 리스트에 넣으므로 힙에 들어가는 노드가 극적으로 줄고, 최적성은 그대로다. 전처리도 필요 없다. 다만 전제가 빡빡해서 — 균일 비용, 정사각 격자, 정적 지형 — 지역 비용이 다른 지형이나 내비게이션 메시에는 못 쓴다. 자세한 가지치기 규칙은 점프 포인트 탐색 쪽 이야기.

재계획 변종. 지형이 조금 바뀌었다고 처음부터 다시 푸는 것은 낭비다. D*와 D* Lite는 이전 탐색의 $g$ 값을 재활용해 영향받은 부분만 고친다. 화성 탐사차와 자율주행 스택의 전역 계획기가 이 계열이며, D* Lite가 구현이 간단해 사실상 표준.

더 나은 휴리스틱 만들기. 대륙 규모 도로망에서는 직선거리가 너무 약해서 A*가 거의 다익스트라처럼 퍼진다. 랜드마크 몇 개를 골라 모든 정점까지의 거리를 미리 계산해 두고 삼각부등식으로 하계를 만드는 ALT 휴리스틱, 퍼즐에서 부분 상태를 완화해 미리 푼 값을 쓰는 패턴 데이터베이스가 대표적이다. 둘 다 휴리스틱의 질에 시간을 투자하는 것이 탐색 알고리즘을 바꾸는 것보다 남는 장사라는 교훈의 사례다.

6. 게임에서의 실제[편집]

게임 길찾기는 A* 한 방으로 끝나지 않고 층이 나뉜다.

그래프 탐색. 내비게이션 메시의 볼록 다각형을 노드로, 공유 변(포탈)을 간선으로 A*를 돌린다. 결과는 점의 열이 아니라 다각형의 띠(코리도)다.
경로 평활화. 코리도 안에서 퍼널(스트링 풀링) 알고리즘으로 실을 팽팽히 당겨 코너만 남긴다. 이걸 안 하면 NPC가 다각형 중심을 따라 지그재그로 걷는다. 격자 A*라면 같은 역할을 시선 검사 기반 경로 다듬기가 한다. 임의 각도 경로를 탐색 단계에서 바로 뽑는 Theta* 계열도 있다.
국소 회피. 다른 에이전트와 동적 장애물은 경로에 반영하지 않고 RVO/ORCA 같은 스티어링 층이 처리한다. 정적 세계는 A*, 동적 이웃은 스티어링이 현대 게임 AI의 기본 골격이다.
예산 관리. 유닛 수백 개가 동시에 길을 찾으면 프레임 예산이 날아간다. 그래서 요청을 큐에 넣어 프레임당 개수를 제한하고, 탐색을 여러 프레임에 걸쳐 쪼개며(시분할 A*), 계층 지도로 먼 거리를 성기게 푼 뒤 근처만 세밀하게 푼다. 흐름장(flow field) 방식으로 다수 유닛의 목표를 하나로 묶어 다익스트라 한 번으로 때우는 RTS식 해법도 있다.

7. 여담[편집]

이름의 별표는 “허용적 평가함수를 쓴 알고리즘 A 중 최적인 것”이라는 의미로 붙었다. 통계학의 $\hat{\theta}^{*}$ 처럼 최적성을 나타내는 관습이었는데, 덕분에 파일명·URL·정규식에서 두고두고 이스케이프를 요구하는 이름이 되었다.
발표 당시 원논문의 최적성 증명에 결함이 있어 1972년에 저자들이 정정 논문을 냈다. “허용적”과 “일관적”을 제대로 분리한 것이 그 과정에서다. 반세기 뒤에도 같은 자리에서 사람들이 넘어지는 것을 보면, 그 구분이 원래 헷갈리는 게 맞다.
가중치에 음수가 있으면 A*도 못 쓴다. 이 경우는 벨만-포드 알고리즘으로 퍼텐셜을 먼저 잡아야 하는데, 게임에서 “지나가면 체력이 회복되는 칸”을 음수 비용으로 모델링하려다 이 벽을 만나는 일이 종종 있다. 대개는 비용을 양수로 재설계하는 쪽이 답이다.

8. 관련 문서[편집]

Hart, P. E., Nilsson, N. J., Raphael, B. (1968). “A Formal Basis for the Heuristic Determination of Minimum Cost Paths”. IEEE Trans. Systems Science and Cybernetics 4(2), 100–107. 셰이키는 한 걸음 옮기는 데 몇 분씩 걸리던 로봇이라, 계획 계산을 아끼는 것이 정말로 절실했다. 세계 최초의 “생각하는 로봇”이 남긴 유산 중 지금까지 가장 널리 쓰이는 것이 결국 이 알고리즘이다. ↩
이 “최적 효율성”에는 잔글씨가 여럿 붙는다. 일관적 휴리스틱일 것, 비교 대상이 같은 휴리스틱 정보만 쓰는 허용적 알고리즘일 것, 그리고 $f = C^{*}$ 인 노드들의 확장 여부는 동점 처리 운에 맡긴다는 것. 그래서 “A*보다 노드를 덜 여는 알고리즘은 없다”는 흔한 요약은 조금 과하다. 그럼에도 반세기 동안 이 자리를 지킨 것은 사실이다. ↩
$\varepsilon$ -준허용적이라 부른다. 재미있는 건 실측에서 해의 품질이 보장치보다 훨씬 좋다는 점이다. $\varepsilon = 3$ 으로 돌려도 실제 경로는 최적 대비 몇 퍼센트 안쪽인 경우가 흔하다. 게임 쪽에서 ” $\varepsilon$ 좀 올려서 쓰자”가 죄책감 없이 통하는 이유. ↩