1 개요
다익스트라 알고리즘을 확장하여 만들어진 경로 탐색 알고리즘이다.
지금 까지 가장 최소의 cost로 도달한 지점부터 탐색하는 다익스트라의 알고리즘의 원리를 차용한 것으로, A* 알고리즘은 현재 상태의 cost를 g(x), 현재 상태에서 다음 상태로 이동할 때의 휴리스틱 함수를 h(x)라고 할 때, 둘을 더한 f(x)가 최소가 되는 지점을 우선적으로 탐색하는 방법이다.
이 f(x)가 작은 값부터 탐색하는 특성상 우선순위 큐가 사용된다.
휴리스틱 함수 h(x)에 따라 성능이 극명하게 갈린다.
f(x) = g(x) 로 둔다면, 이것이 곧 다익스트라와 동일하게 된다.
다만 기본적으로 완전한 최단 거리가 도출되는 것이 아니기 때문에 개량하여 사용하는 경우가 많다. 따라서 IDA*, Jump Point Search 등 A*의 파생형 또한 많은 편이다.
A*를 사용하는 이유는 다익스트라의 현실 적용이 매우 어렵기 때문이다. 당장에 네트워크 같은 디지털적인 공간이 아닌, 현실의, 사람이 사는 공간을 생각해보자, 사람이 다닐 수 있는 "거리"는 명백히 아날로그하다. 이것들을 전부 노드화 시키기에는 그 수가 엄청나게 많아질 수 있다. 그렇다면 탐색해야 하는 공간도 그만큼 커지게 되고, 시간 복잡도 역시 무수히 커질것이다. 또한 어찌어찌 잘 노드화 시켜서 다익스트라를 사용 할 수 있는 상황을 만들어서 경로를 발견했다고 치자, 그렇게 탐색한 경로가 자동차 정체 구간, 출근길 등 다양한 변수로 인해 오히려 더 느려질 수 있는 경우도 발생하기 마련이다. 이러한 변수때문에 A* 알고리즘을 사용하는 것이다.
2 원리
가장 기본이 되는 식은 다음과 같다.
[math]f(x) = g(x) + h(x)[/math]
동작은 다음과 같이 된다.
1. f(x)를 제일 작은것을 우선으로 하는 우선순위 큐에 노드를 삽입한다.
2. 우선순위 큐를 pop한다.
3. 해당 노드에서 이동할 수 있는 노드를 찾는다.
4. 그 노드들의 f(x)를 구한다.
5. 그 노드들을 우선순위 큐에 삽입 한다.
6. 목표 노드로 도달할 때 까지 반복한다.
psedo 코드는 다음과 같다.
while pq_size node = pq.pop if node == goal break; for next_node in (next_node_begin...next_node_end) pq.push(next_node, g(node) + cost + h(next_node)) print node
3 예시
8-puzzle, 15-puzzle 이 좋은 예시가 된다.
이와 같이 g(n)을 이동 횟수, 현재 퍼즐의 상태를 노드로 하고 알고리즘을 시행한다면 해결이 가능하다.
보통 현재 퍼즐의 상태는 해시로 노드화한다.
그리고 h(n)은 N-Puzzle의 유명한 휴리스틱 함수, Manhattan distance function으로 한다.
Manhattan distance 는 2차원 평면 좌표계에서의 두 정점을 [math](x_i, y_i), (x_j, y_j)[/math] 라고 할 때, [math]|x_i - x_j| + |y_i - y_j|[/math]를 의미한다.
이때의 [math]h(n) = \Sigma \ Manhattan \ distance(tile, \ correct \ position)[/math] 이다. (tile = 어떤 숫자의 현재 위치, correct_position = 그 노드가 원래 있어야할 위치)
Manhattan distance는 Admissble 하다.
4 기타
휴리스틱 함수가 admissible하다면 최단경로가 보장된다.[2]
Admissible_heuristic을 참고해보면 좋다.