[목차] == 개요 == [[다익스트라 알고리즘]]을 확장하여 만들어진 경로 탐색 알고리즘이다. 에이스타 알고리즘 이라고 읽는다. 지금까지 가장 최소의 비용으로 도달한 지점부터 탐색하는 다익스트라 알고리즘의 원리를 차용한 것으로, A* 알고리즘은 현재 상태의 비용을 [math(g(x))], 현재 상태에서 다음 상태로 이동할 때의 [[휴리스틱]] 함수를 [math(h(x))]라고 할 때, 둘을 더한 [math(f(x) = g(x) + h(x))]가 최소가 되는 지점을 우선적으로 탐색하는 방법이다. 이 [math(f(x))]가 작은 값부터 탐색하는 특성상 [[큐(자료구조)#s-3.2|우선순위 큐]]가 사용된다. 휴리스틱 함수 [math(h(x))]에 따라 성능이 극명하게 갈리며, [math(f(x) = g(x))]일 때는 다익스트라 알고리즘과 동일하다. 다만 사용된 휴리스틱에 따라서 최단거리를 도출할 수 없기도 하기 때문에 개량하여 사용하는 경우가 많다. 따라서 [[IDA*]], [[Jump Point Search]] 등 A*의 파생형 또한 많은 편이다. A*를 사용하는 이유는 다익스트라의 현실 적용이 매우 어렵기 때문이다. 당장에 네트워크 같은 디지털적인 공간이 아닌, 현실의, 사람이 사는 공간을 생각해보자. 사람이 다닐 수 있는 "거리"는 명백히 아날로그하다. 이것들을 전부 노드화시키기에는 그 수가 엄청나게 많아질 수 있다. 그렇다면 탐색해야 하는 공간도 그만큼 커지게 되고, 시간 복잡도 역시 아득히 커질 것이다. 또한 어찌어찌 잘 노드화시켜서 다익스트라를 사용할 수 있는 상황을 만들어서 경로를 발견했다고 치자. 그렇게 탐색한 경로가 자동차 정체 구간, 출근길 등 다양한 변수로 인해 오히려 더 느려질 수 있는 경우도 발생하기 마련이다. 이러한 변수 때문에 A* 알고리즘을 사용하는 것이다. 그리고 A*를 발전시킨 형태가 D*(Dynamic A*)알고리즘인데, 현세대의 대부분의 차량 [[내비게이션]]은 이를 활용한다고 보면 된다. == 원리 == 가장 기본이 되는 식은 다음과 같다. [math(f(x) = g(x) + h(x))] 동작은 다음과 같이 된다. 1. [math(f(x))]를 오름차순 우선순위 큐에 노드로 삽입한다. 1. 우선순위 큐를 pop한다. 1. 해당 노드에서 이동할 수 있는 노드를 찾는다. 1. 그 노드들의 [math(f(x))]를 구한다. 1. 그 노드들을 우선순위 큐에 삽입한다. 1. 목표 노드에 도달할 때까지 반복한다. 의사코드는 다음과 같다. {{{#!html <!-- HTML generated using hilite.me --><div style="background: #ffffff; overflow:auto;width:auto;border:solid gray;border-width:.1em .1em .1em .8em;padding:.2em .6em;"><pre style="margin: 0; line-height: 125%"> PQ.push(start_node, g(start_node) + h(start_node)) <span style="color: #888888">//우선순위 큐에 시작 노드를 삽입한다.</span> <span style="color: #008800; font-weight: bold">while</span> PQ is not empty <span style="color: #888888">//우선순위 큐가 비어있지 않은 동안</span> node = PQ.pop <span style="color: #888888">//우선순위 큐를 pop한다.</span> <span style="color: #008800; font-weight: bold">if</span> node == goal_node <span style="color: #888888">//만일 해당 노드가 목표 노드이면 반복문을 빠져나온다.</span> <span style="color: #008800; font-weight: bold">break</span> <span style="color: #008800; font-weight: bold">for</span> next_node in (next_node_begin...next_node_end) <span style="color: #888888">//해당 노드에서 이동할 수 있는 다음 노드들을 보는 동안</span> PQ.push(next_node, g(node) + cost + h(next_node)) <span style="color: #888888">//우선순위 큐에 다음 노드를 삽입한다.</span> <span style="color: #008800; font-weight: bold">print</span> goal_node_dist <span style="color: #888888">//시작 노드에서 목표 노드까지의 거리를 출력한다.</span> </pre></div> }}} == 예시 == 8-puzzle, 15-puzzle이 좋은 예시가 된다. [[파일:depthfirstsearch.jpg]] [*출처 [[http://courses.cs.washington.edu/courses/cse143/04au/projects/project3/partB.html]]] 이와 같은 상황은 [math(g(n))]을 이동 횟수, 현재 퍼즐의 상태를 노드로 하고 알고리즘을 시행한다면 해결이 가능하다. 보통 현재 퍼즐의 상태는 [[해시]]로 노드화한다. 그리고 [math(h(n))]은 N-Puzzle의 유명한 휴리스틱 함수인 Manhattan distance function으로 한다. Manhattan distance, 즉 [[http://navercast.naver.com/contents.nhn?rid=22&contents_id=629|택시거리]]는 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하다. == 기타 == 휴리스틱 함수가 admissible하면([[https://en.wikipedia.org/wiki/Admissible_heuristic|#1]], [[https://heuristicswiki.wikispaces.com/Admissible+Heuristic|#2]]) 최단경로가 보장된다. admissible하지 않은 휴리스틱 함수를 사용하면 탐색 노드가 증폭될 수 있다. 휴리스틱 함수가 admissible하다는 말은 휴리스틱 함수가 목적지까지 남은 거리를 과대평가 하지 않는다는 뜻이다. 남은 거리를 과대평가하면 현재 경로가 실제로는 최단거리라도 당장 알고리즘이 보기에는 최단거리가 아닌것처럼 오인하기 때문에 최단경로를 찾을 수 없을수도 있다. [[분류:탐색 알고리즘]]