A* 알고리즘
1. 개요
다익스트라 알고리즘을 확장하여 만들어진 경로 탐색 알고리즘이다.
에이스타 알고리즘 이라고 읽는다.
지금까지 가장 최소의 비용으로 도달한 지점부터 탐색하는 다익스트라 알고리즘의 원리를 차용한 것으로, A* 알고리즘은 현재 상태의 비용을 $$g(x)$$, 현재 상태에서 다음 상태로 이동할 때의 휴리스틱 함수를 $$h(x)$$라고 할 때, 둘을 더한 $$f(x) = g(x) + h(x)$$가 최소가 되는 지점을 우선적으로 탐색하는 방법이다. 이 $$f(x)$$가 작은 값부터 탐색하는 특성상 우선순위 큐가 사용된다. 휴리스틱 함수 $$h(x)$$에 따라 성능이 극명하게 갈리며, $$f(x) = g(x)$$일 때는 다익스트라 알고리즘과 동일하다.
다만 사용된 휴리스틱에 따라서 최단거리를 도출할 수 없기도 하기 때문에 개량하여 사용하는 경우가 많다. 따라서 IDA*, Jump Point Search 등 A*의 파생형 또한 많은 편이다.
A*를 사용하는 이유는 다익스트라의 현실 적용이 매우 어렵기 때문이다. 당장에 네트워크 같은 디지털적인 공간이 아닌, 현실의, 사람이 사는 공간을 생각해보자. 사람이 다닐 수 있는 "거리"는 명백히 아날로그하다. 이것들을 전부 노드화시키기에는 그 수가 엄청나게 많아질 수 있다. 그렇다면 탐색해야 하는 공간도 그만큼 커지게 되고, 시간 복잡도 역시 아득히 커질 것이다. 또한 어찌어찌 잘 노드화시켜서 다익스트라를 사용할 수 있는 상황을 만들어서 경로를 발견했다고 치자. 그렇게 탐색한 경로가 자동차 정체 구간, 출근길 등 다양한 변수로 인해 오히려 더 느려질 수 있는 경우도 발생하기 마련이다. 이러한 변수 때문에 A* 알고리즘을 사용하는 것이다. 그리고 A*를 발전시킨 형태가 D*(Dynamic A*)알고리즘인데, 현세대의 대부분의 차량 내비게이션은 이를 활용한다고 보면 된다.
2. 원리
가장 기본이 되는 식은 다음과 같다.
$$f(x) = g(x) + h(x)$$
동작은 다음과 같이 된다.
- $$f(x)$$를 오름차순 우선순위 큐에 노드로 삽입한다.
- 우선순위 큐를 pop한다.
- 해당 노드에서 이동할 수 있는 노드를 찾는다.
- 그 노드들의 $$f(x)$$를 구한다.
- 그 노드들을 우선순위 큐에 삽입한다.
- 목표 노드에 도달할 때까지 반복한다.
PQ.push(start_node, g(start_node) + h(start_node)) //우선순위 큐에 시작 노드를 삽입한다.while PQ is not empty //우선순위 큐가 비어있지 않은 동안 node = PQ.pop //우선순위 큐를 pop한다. if node == goal_node //만일 해당 노드가 목표 노드이면 반복문을 빠져나온다. break for next_node in (next_node_begin...next_node_end) //해당 노드에서 이동할 수 있는 다음 노드들을 보는 동안 PQ.push(next_node, g(node) + cost + h(next_node)) //우선순위 큐에 다음 노드를 삽입한다.print goal_node_dist //시작 노드에서 목표 노드까지의 거리를 출력한다.
3. 예시
8-puzzle, 15-puzzle이 좋은 예시가 된다.
[image]
[출처]
이와 같은 상황은 $$g(n)$$을 이동 횟수, 현재 퍼즐의 상태를 노드로 하고 알고리즘을 시행한다면 해결이 가능하다.
보통 현재 퍼즐의 상태는 해시로 노드화한다. 그리고 $$h(n)$$은 N-Puzzle의 유명한 휴리스틱 함수인 Manhattan distance function으로 한다. Manhattan distance, 즉 택시거리는 2차원 평면 좌표계에서의 두 정점을 $$(x_i, y_i), (x_j, y_j)$$ 라고 할 때, $$|x_i - x_j| + |y_i - y_j|$$를 의미한다.
이때의 $$h(n) = \Sigma d(t, p)$$이다. 이때 $$d$$는 두 위치 사이의 택시거리, $$t$$는 어떤 숫자의 현재 위치, $$p$$는 그 노드가 원래 있어야 할 위치이다.
Manhattan distance는 Admissible하다.
4. 기타
휴리스틱 함수가 admissible하면(#1, #2) 최단경로가 보장된다. admissible하지 않은 휴리스틱 함수를 사용하면 탐색 노드가 증폭될 수 있다.
휴리스틱 함수가 admissible하다는 말은 휴리스틱 함수가 목적지까지 남은 거리를 과대평가 하지 않는다는 뜻이다. 남은 거리를 과대평가하면 현재 경로가 실제로는 최단거리라도 당장 알고리즘이 보기에는 최단거리가 아닌것처럼 오인하기 때문에 최단경로를 찾을 수 없을수도 있다.