1. A* Algorithm ?
A* 알고리즘은 두 점(시작지점과 도착지점)을 잇는 최단경로를 찾아주는 그래프/트리 탐색 알고리즘 중 하나입니다. 특히나 이 알고리즘에서는 각 길목에서 최상의 경로를 추정하기 위해 “휴리스틱 값”, 즉 추정값을 사용합니다.
2. Heuristics (휴리스틱) ?
시간이 부족하거나 정보가 부족한 경우, 혹은 굳이 합리적인 판단이 필요하지 않은 상황에서 사용하는 어림짐작의 기술 중 하나입니다.
3. 알고리즘 설명
3.1. 시작조건
1) 기본적으로 그래프/트리 구조를 이용하는 탐색 알고리즘임을 기억합니다. 2) 다음으로는 두 가지의 상태를 확인할 수 있는 그릇(큐1)이 필요합니다.
여기서는 리스트의 형태를 사용하겠습니다.
2-1) 아직 조사하지 않았던, 기나가지 않았던 곳을 담는 그릇 (이하 **"Open List"**)
2-2) 조사 했던 곳, 혹은 지나왔었던 곳을 담는 그릇 (이하 **"Close List"**)
3) 평가 함수라고 불리는 다음과 같은 식을 사용하여 각 지점을 조사하겠습니다. 이 식을 사용하여 나온 값으로 최단거리를 판단하게 됩니다.
f(n) = g(n) + h(n)
1) g(n) : 시작지점부터 N 지점까지의 이동 비용
2) h(n) : N 지점부터 목표 지점까지의 예상 이동 비용, 추정값 (휴리스틱 값, Heuristics)
g(n)은 보통 다음과 같은 예로 들 수 있습니다. 상, 하, 좌, 우로 이동하는 경우는 1 만큼 비용이 들고, 대각방향은 √(가로^2 + 세로^2) 이므로 1.414…가 됩니다. 계산하기 쉽게 각 *10을 취하면, 직진방향 이동 비용은 10, 대각 방향 이동 비용은 14 로 정할 수 있습니다.
3.2. 순서 및 설명
1) 시작 지점을 Open List에 넣습니다.
2) Open List에 담긴 지점을 꺼내어 Close List에 넣습니다. 그리고 해당 지점의 주변 8방향을 탐색/조사 합니다.
* 탐색/조사에는 다음과 같은 조건이 존재하며, 평가함수를 사용하여 각 값을 계산합니다.
1) 조사는 Close List에 담긴 지점과 장애물을 제외합니다.
2) 목표 지점이 있는지 조사합니다. 목표 지점이 있다면, 각 지점의 부모 지점을 추적하여 스택에 담습니다.
3) Open List가 비게 되는 경우는 목표 지점을 찾는데, 실패한 경우입니다. 길이 없는 것입니다.
3) 직전에 탐색한 지점들을 Open List에 담도록 합니다.
* Open List에 담는 조건이 존재합니다.
1) Open List에 이미 존재하는 지점은 g(n) 값을 비교하여 더 작은 값으로 교체합니다.
2) Open List는 f(n) 의 값이 적은 순서대로 정렬되어야 합니다.
4) “2)”번의 단계부터 다시 반복합니다.
그릇(큐, Queue), 주로 빠른 속도를 지향하기 위해서 우선 순위 큐를 사용합니다. ↩