A* 알고리즘

우리은하 중심의 초대질량 블랙홀에 대한 내용은 궁수자리 A* 문서 참고하십시오.

1. 개요[편집]

---

다익스트라 알고리즘을 확장하여 만들어진 경로 탐색 알고리즘이다. 드론이나 로봇 차량의 인공지능 주행을 구현하기 위해 개발되었다.
에이스타 알고리즘 이라고 읽는다.

2. 개념[편집]

---

지금까지 가장 최소의 비용으로 도달한 지점부터 탐색하는 다익스트라 알고리즘의 원리를 차용한 것으로, A* 알고리즘은 현재 상태의 비용을 [math(g(x))], 현재 상태에서 다음 상태로 이동할 때의 휴리스틱 함수를 [math(h(x))]라고 할 때, 둘을 더한 [math(f(x) = g(x) + h(x))]가 최소가 되는 지점을 우선적으로 탐색하는 방법이다. 이 [math(f(x))]가 작은 값부터 탐색하는 특성상 우선순위 큐가 사용된다. 휴리스틱 함수 [math(h(x))]에 따라 성능이 극명하게 갈리며, [math(f(x) = g(x))]일 때는 다익스트라 알고리즘과 동일하다.

A*를 사용하는 이유는 다익스트라를 직접 현실 문제에 적용하기가 매우 부담되기 때문이다. 당장에 네트워크 같은 디지털적인 공간이 아닌, 현실의, 사람이 사는 공간을 생각해보자. 사람이 다닐 수 있는 "거리"는 명백히 아날로그하다. 이것들을 전부 노드화시키기에는 그 수가 엄청나게 많아질 수 있다. 그렇다면 탐색해야 하는 공간도 그만큼 커지게 되고, 시간 복잡도 역시 아득히 커질 것이다. 또한 어찌어찌 잘 노드화시켜서 다익스트라를 사용할 수 있는 상황을 만들어서 경로를 발견했다고 치자. 그렇게 탐색한 경로가 자동차 정체 구간, 출근길 등 다양한 변수로 인해 오히려 더 느려질 수 있는 경우도 발생하기 마련이다. 이러한 변수 때문에 A* 알고리즘을 사용하는 것이다.

---

가장 기본이 되는 식은 다음과 같다.
[math(f(x) = g(x) + h(x))]

동작은 다음과 같이 된다.

1. [math(f(x))]를 오름차순 우선순위 큐에 노드로 삽입한다.
2. 우선순위 큐에서 최우선 노드를 pop한다.
3. 해당 노드에서 이동할 수 있는 노드를 찾는다.
4. 그 노드들의 [math(f(x))]를 구한다.
5. 그 노드들을 우선순위 큐에 삽입한다.
6. 목표 노드에 도달할 때까지 반복한다.

의사코드는 다음과 같다.

3. 응용[편집]

---

다만 사용하는 휴리스틱에 따라서 최단거리를 확실하게 보장하는 대신 속도를 더 높이는 방법 등이 여럿 연구되어, 목적에 따라 개량하여 사용하는 경우가 많다. 따라서 Weighted A*, LPA*, IDA*, D*, D* Lite[1], JPS 등등 A*의 개념에 기본을 두고 발달한 무수히 많은 알고리즘들이 있다. 학문적 길찾기 알고리즘 경진대회[2]를 보면 전처리를 하거나 메모리를 사용하거나 추가적인 전제[3]를 넣는 등의 여러 접근 방식이 있음을 알 수 있다. 동일한 공간을 탐색하는 데 어느 알고리즘은 추가 메모리를 아예 소모하지 않는 반면 어느 알고리즘은 수십, 수백 기가바이트씩 차지하는 것을 볼 수 있다.

처음부터 길과 장벽을 모두 알고 시작하는 결정론적인 공간이 아니라 점진적으로 주위 환경을 탐색하면서 길을 탐색해 나가는 목적으로 개발된 변형이 D*(Dynamic A*)알고리즘인데 A*보다 메모리를 대량으로 소비하는 탓에 여러 개의 오브젝트들이 동시에 빠르게 길을 찾아야 하는 게임 등에는 잘 쓰이지 않지만 단일 물체를 확실하게 조향해야 하는 자율주행차나 행성 탐사로봇 등에 사용되기 적합하다. 현세대의 대부분의 차량 내비게이션은 이를 기반으로 만들어져 있다고 보면 된다.

4. 예시[편집]

---

8-puzzle, 15-puzzle이 좋은 예시가 된다.


[출처]

이와 같은 상황은 [math(g(n))]을 이동 횟수, 현재 퍼즐의 상태를 노드로 하고 알고리즘을 시행한다면 해결이 가능하다.
보통 현재 퍼즐의 상태는 해시로 노드화한다. 그리고 [math(h(n))]은 N-Puzzle의 유명한 휴리스틱 함수인 Manhattan distance function으로 한다. Manhattan distance, 즉 택시거리는 2차원 평면 좌표계에서의 두 정점을 [math((x_i, y_i), (x_j, y_j))] 라고 할 때, [math(|x_i - x_j| + |y_i - y_j|)]를 의미한다.
이때의 [math(h(n) = \Sigma d(t, p))]이다. 이때 [math(d)]는 두 위치 사이의 택시거리, [math(t)]는 어떤 숫자의 현재 위치, [math(p)]는 그 노드가 원래 있어야 할 위치이다.

Manhattan distance는 Admissible하다.

5. 기타[편집]

---

휴리스틱 함수가 admissible하면(#1, #2) 최단경로가 보장된다. admissible하지 않은 휴리스틱 함수를 사용하면 탐색 노드가 증폭될 수 있다.

휴리스틱 함수가 admissible하다는 말은 휴리스틱 함수가 목적지까지 남은 거리를 과대평가 하지 않는다는 뜻이다. 남은 거리를 과대평가하면 현재 경로가 실제로는 최단거리라도 당장 알고리즘이 보기에는 최단거리가 아닌것처럼 오인하기 때문에 최단경로를 찾을 수 없을수도 있다.

스타크래프트도 이동 알고리즘을 해당 알고리즘을 썼다. #