A* 알고리즘

A*은(는) 여기로 연결됩니다.

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

, 스웨덴의 팝 그룹에 대한 내용은 A*Teens 문서

참고하십시오.

''' 이론 컴퓨터 과학 {{{#!wiki style="display: inline-block; font-family:Times New Roman, serif;font-style:italic"'''
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px"	<colbgcolor=#a36> 이론
기본 대상	수학기초론{ 수리논리학( 논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학( 그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학
다루는 대상과 주요 토픽
계산 가능성 이론	재귀함수 · 튜링 머신 · 람다대수 · 처치-튜링 명제 · 바쁜 비버
오토마타 이론	FSM · 푸시다운 · 튜링 머신( 폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임 · 형식언어
계산 복잡도 이론	점근 표기법 · 튜링 기계^^{고전, 양자, 비결정론적, 병렬 임의접근 기계}^ · 알고리즘 · 자료구조 · 알고리즘 패러다임( 그리디 알고리즘, 동적 계획법)
정보이론	데이터 압축( 무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학
프로그래밍 언어이론	프로그래밍 언어( 함수형 언어 · 객체 지향 프로그래밍 · 증명보조기) · 메타 프로그래밍 · 유형 이론 · 프로그래밍 언어 의미론 · 파싱 · 컴파일러 이론
주요 알고리즘 및 자료구조
기초	정렬 알고리즘 · 순서도 · 탐색 알고리즘
추상적 자료형 및 구현	배열^^벡터^ · 리스트^^{연결 리스트}^ · 셋(set)^^{레드-블랙 트리, B-트리}^ · 우선순위 큐^^{힙, 피보나치 힙}^
수학적 최적화	조합 최적화	외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습
	볼록 최적화	내부점 방법 · 경사하강법
	선형계획법	심플렉스법
계산 수론 및 암호학	밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘 · 해시( MD5 · 암호화폐 · 사전 공격( 레인보우 테이블) · SHA) · 양자 암호
	대칭키 암호화 방식	블록 암호 알고리즘( AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4)
	공개키 암호화 방식	공개키 암호 알고리즘( 타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9)
계산기하학	볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^^{Fortune의 line-sweeping 알고리즘}^ · 범위 탐색^^{vp-tree, R-tree}^ · k-NN
그래프 이론	탐색^^{BFS, DFS, 다익스트라 알고리즘, A* 알고리즘}^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론
정리
정지 문제^{대각선 논법} · 암달의 법칙 · P-NP 문제^미해결 · 콜라츠 추측^미해결
틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학			}}}}}}}}}

1. 개요2. 개념3. 응용4. 예시5. 기타

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))]

동작은 다음과 같이 된다.

[math(f(x))]를 오름차순 우선순위 큐에 노드로 삽입한다.
우선순위 큐에서 최우선 노드를 pop한다.
해당 노드에서 이동할 수 있는 노드를 찾는다.
그 노드들의 [math(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. 응용

다만 사용하는 휴리스틱에 따라서 최단거리를 확실하게 보장하는 대신 속도를 더 높이는 방법 등이 여럿 연구되어, 목적에 따라 개량하여 사용하는 경우가 많다. 따라서 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하다는 말은 휴리스틱 함수가 목적지까지 남은 거리를 과대평가 하지 않는다는 뜻이다. 남은 거리를 과대평가하면 현재 경로가 실제로는 최단거리라도 당장 알고리즘이 보기에는 최단거리가 아닌것처럼 오인하기 때문에 최단경로를 찾을 수 없을수도 있다.

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

[1] 이름은 D*에서 파생되었지만 정작 알고리즘은 상당히 다르다 [2] 목록에 있는 것은 논문화된 알고리즘 중 극히 일부분이다. [3] 예를 들어, JPS의 경우 각 노드들의 이동 weight가 모두 동일하고 방향에 따라 대칭적인 구조를 지닌 공간이라는 제약사항을 추가하여 대칭공간에 대한 탐색을 크게 간소화한다. [출처] http://courses.cs.washington.edu/courses/cse143/04au/projects/project3/partB.html