A* 알고리즘

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
A* 알고리즘
분류 그래프 탐색 알고리즘, 검색 알고리즘
자료구조 그래프
최적 아니오.

전산학 분야에 있어서, A* 알고리듬(A* algorithm 에이 스타 알고리듬[*])은 주어진 출발지 노드에서부터 목적지 노드까지 가는 최단 경로를 찾아내는(다시 말해 주어진 목적지 노드까지 가는 최단 경로임을 판단할 수 있는 테스트를 통과하는) 그래프/트리 탐색 알고리즘 중 하나이다. 이 알고리즘은 각 노드 x에 대해 그 노드를 통과하는 최상의 경로를 추정하는 순위값인 "휴리스틱 추정값" h(x)을 매기는 방법을 쓴다. 이 알고리즘은 이 휴리스틱 추정값의 순서로 노드를 방문한다. 그러므로 우리는 A* 알고리즘을 best first search의 한 예로 분류할 수 있다.

이 알고리즘은 1968년 피터 하트, 닐스 닐슨, 버트램 라팰이 처음 기술하였다. 그 3명의 논문에서, 이 알고리즘은 A 알고리즘(algorithm A)이라고 불렸다. 적절한 휴리스틱을 가지고 이 알고리즘을 사용하면 최적(optimal)이 된다. 그러므로 A* 알고리즘이라고 불린다.

A* 알고리즘은 출발노드로부터 목표노드까지의 최적경로를 탐색하기 위한 것이다. 이를 위해서는 각각의 노드에 대한 평가함수를 정의해야 한다. 이를 위한 평가함수 f(n)은 다음과 같다.

f(n) = g(n) + h(n)
  • g(n) : 출발노드로부터 노드 n까지의 경로비용
  • h(n) : 노드 n으로부터 목표 노드까지의 추정 경로비용

예제: 8-퍼즐 문제[편집]

8-puzzle by ddong.jpg

     f(n)     g(n)     h(n)