A*  Algorithm

 

............ A* search algorithm (A star 라고 발음) 초기 노드에서 목표 노드까지의 경로를 찾는 그래프 탐색 알고리즘이다. 목표 노드까지의 가장좋은 경로를 추정 (estimate of the best route) 하기 위해 각 노드에 랭킹을 부여하는 "heuristic estimate" 를 사용하고 그 순서대로 노드를 방문한다. 따라서 A* algorithm 은 best-first search 의 한 예이다. A* algorithm 은 그래프에서 최단경로를 찾는 것을 보장하며 최소의 계산 (minimum computation) 으로 수행한다. 최초로 소개된 논문 (A Formal Basis for the Heuristic Determination of Minimum Cost Paths in Graphs, 1968) 에서 허용성과 최적성 (admissibility and optimality properties) 이 증명되었다. ............

A* 는 최단 거리 찾기 (Path finding problem) 에서 가장 훌륭한 선택이 될 것이다. 왜냐하면 Dijkstra's algorithm 이나 Best-First Search (BFS) 보다 훨씬 빠르기 때문이다. A* 는 휴리스틱 방법 (의사결정을 할 때 해당 문제에 대한 정보를 이용하는 것) 과 형식적 방법 (formal method : 문제와 관련된 정보를 사용하지 않지만 formally analyzed 될 수 있는 것)을 결합하기 위해 1968 년에 개발되었다. A* 의 대략의 구조는 그래프 탐색 알고리즘이다. 그러나 다른 그래프 탐색 알고리즘과 다른 점은 목표에 얼마나 근접한 것인지를 평가하는데 휴리스틱 함수를 사용한다는 것이다. 휴리스틱에 의해 먼저 가장 바람직한 방향을 탐색하게 된다. 그 방향이 실패하면 다른 경로를 찾게 된다. 여기서는 A* 알고리즘의 세세한 부분까지는 다루지 않고, A* 가 어떻게 움직이는지를 다루어서 게임에 어떻게 응용되는지에 초점을 맞춘다 .............. (Amit's Thought on Path Finding : A* Algorithm)

A* algorithm 은 많은 종료의 문제 해결에 이용돼 왔으며 게임 개발에서 효율적인 path finding 으로 많이 쓰인다.  A* 는 공간안의 어떤 특정 state 에서 인접한 state를 조사해 나가면서 시작 state에서 목표 state 까지 가장 싼 비용의 경로를 찾는 algorithm 이다 ........ A* algorithm 이 쓰인 유명한 문제는 1칸이 빈 15 puzzle 이다.  4*4 에서 하나가 빈 15 puzzle에서 어떤 state 란 15개 타일들의 특정한 배치를 의미하고, 인접한 state 란 하나의 타일을 빈 곳으로 이동시킴으로써 새로이 생기는 특정한 배치를 의미한다 ...... 비슷하게 path finding 문제에서 어떤 state 는 게임 세계에서 unit 이 차지하고 있는 특정한 위치로 구성되며, 인접한 state 는 그 유닛이 한번에, 직접 이동할 수 있는 인접한 위치들로 구성된다.

A* algorithm 의 기본은 아직 조사하지 않은 state들 중 가장 유용할 듯한 state를 조사하는 과정을 반복하는 것이다. 조사중 목표된 state 라고 판단되면 algorithm 은 끝나고, 그렇지 않으면 목표에 도달할때까지 계속 인접 state를 조사해나간다 ..... A* 가 관리하는 state의 list 는 두 종류이다.  하나는 아직 조사하지 않은 상태들이 담긴 'Open list' 이고 다른 하나는 이미 조사한 상태들을 담은 'Closed list' 이다. 처음  algorithm을 시작할 때 탐색된 곳이 없으므로 Closed list 들은 비어 있고, Open list 는 처음 위치- 즉 시작 state 만 갖고 있다.

algorithm 은 수행되면서 Open list 중 가장 유망한 것(1)을 가져와 다음 state를 계산하고, 이들은 Open list 들에서는 삭제된다. 그 state 가 목표한 state 가 아니면 인접한 위치들을 정렬해서 아직 탐색되지 않은 곳이라면 Open list 에 넣고, 이미 Open list 에 있는 것일때는 그 위치를 통하는 새로운 경로가 이전 보다 비용이 싸면 그 state 의 정보를 갱신해준다. 반대로 그 위치들이 Closed list 에 있는 것이라면 이미 search 한 것이므로 무시한다. 목표에 도달하기 전에 Open list 가 빈다면 이것은 start point에서 목표한 곳으로 가는 경로가 존재하지 않는다는 뜻이다 ......... 유망한 state란 그 위치를 지나서 목표에 도달하는 경로의 비용이 가장 싸거나 또는 가장 쌀 가능성이 큰 위치를 말한다 ........

A* 는 몇가지 유용한 특징들을 가지고 있다.

을 노드 과 목표 노드 사이의 최단 경로 ( 에서 모든 목표 노드까지의 모든 가능한 경로 중에서) 의 실제 값이라고 하자. 을 시작 노드 에서 까지의 최단 경로의 값이라고 하자. 그러면 에서 목표 노드까지 노드 을 통하여 갈 수 있는 모든 가능한 경로 중에서 최단 경로의 값이 된다. 그리고 에서 목표 노드까지의 (조건 없는) 최단 경로의 값을 나타낸다. 각 노드 에 대하여 (휴리스틱 요소) 을 의 추정값 이라고 하고, (깊이 요소) 을 A* 에 의하여 지금까지 발견된 노드 까지의 경로 중에서 최단 경로의 값이라고 하자. 알고리즘 A* 에서는  를 평가 함수 로 사용한다. 알고리즘 A* 에서  이 0 이면 균일비용 탐색이 된다 ............... (Nils J.Nilsson 1998)

term :

그래프 (Graph)   탐색 (Search)    휴리스틱 (Heuristic)   최단경로 찾기 문제 (Shortest Path Finding Problem)    문제해결 (Problem Solving)   휴리스틱 탐색 (Heuristic Search)   최상우선 탐색 (Best-first Search)   A * 알고리즘   

site :

Wikipedia : A* Algorithm

A* Algorithm : AI Java Implemented

paper :

A Formal Basis for the Heuristic Determination of Minimum Cost Paths in Graphs : Peter E. Hart, Nils J.Nilsson, Bertram Raphael, IEEE Trans. on Systems Science and Cybernetics, Vol. SSC-4, No. 2, pp 100-107, (July 1968).

A* 알고리즘 (Algorithm A*) : Nils J.Nilsson

A* 알고리즘의 휴우리스틱 유도 방법 : 유석인