A* 알고리즘

A* 알고리즘

A*(에이 스타) 알고리즘은 주어진 출발 꼭짓점에서부터 목표 꼭짓점까지 가는 최단 경로를 찾아내는 그래프 탐색 알고리즘이다.

다익스트라 알고리즘과 유사한데, 다익스트라가 모든 경로를 찾아가면서 짧은 경로를 발견하면 갱신하는 거라면 A* 알고리즘은 Heuristic(휴리스틱)이라는 계산값을 통해 모든 경로가 아닌 가능성이 제일 높은 방향 부터 계산하며 경로를 찾는다.

<다익스트라 알고리즘>

<A* 알고리즘>

A* 알고리즘 계산

A* 알고리즘은 위에서 말한 것처럼 각 지점을 평가한 후 결과에 따라 다음 탐색 위치를 정한다.
이를 위한 평가는 F(n)으로 정해지며 F(n)에 대한 식은 다음과 같다.
f(n) = g(n) + h(n)
f(n) : 총 예상 거리
g(n) : 출발점부터 n까지의 가중치 (지금까지 이동거리)
h(n) : n으로부터 도착지점까지 추정 경로 가중치 (남은 예상거리)
이렇게 f(n)을 구한 후 f가 낮은 것부터 탐색을 실시한다.

h(n)이 A*알고리즘의 핵심이라고 생각된다. h(n)<< 이 녀석이 다익스트라와 A*를 구분짓는 녀석;
h가 변하지 않고 일정하다면 다익스트라와 동일하다.

위의 f,g,h를 보면 f는 구하기 쉽고 g도 구하기 쉬운데 h는 어떻게 구함 ?;이라는 생각이 든다.
h를 구하는 방법은 유클리드와 맨하튼 방법이 있는데 우선 맨하튼 방법부터 설명하겠다.

우리는 S지점에 서있고 목적지가 E에 있다면 E에 가기 위해 지도를 볼 때 위로 몇 번 오른쪽으로 몇 번을 정하고 그 숫자만 맞춘다면 원하는 지점에 도착하게 되어있다. 왼쪽과 아래쪽은 움직일 생각도 하지 않을 것이다.

맨하튼 방식은 이와 같이 h(x)값을 구한 후 f(x)값을 계산한다.
한 칸의 거리는 10으로 가정한다.

스타트 지점으로부터 상하좌우 네 칸은 출발점으로부터 한 칸 떨어져있기에 g = 10,
도착지점까지 5칸 떨어져 있어 h = 50
f = g + h 에 의하여 f = 60 으로 설정된다.
그 다음 탐색지점은 f 가 가장 낮은 60인 지점에서 탐색된다. (오른쪽, 위 쪽 둘 중 하나 뭐든 상관없음)

위를 탐색하면 탐색 된 지점을 기준으로 다시 상하좌우가 탐색되며 f 값이 기존 값보다 낮아지면 f 값을 갱신한다.

이 다음은 최소 f 가 60인 지점에서 탐색이 일어날텐데 f 값이 같다면 g가 더 큰 쪽을 먼저 탐색한다.
g가 높다는 의미는 지금까지 움직인 거리가 더 많다는 뜻이고, 이미 g만큼 움직였으니 더 움직일 거리가 줄어든다와 같은 말이다.

이와 같은 방법을 반복하면 위의 결과를 얻을 수 있다.

유클리드 방법도 이와 크게 다르지는 않는데, 다른 점은 h 값을 구할 때 대각의 거리까지도 생각을 한다는 점이 다르다. 피타고라스의 정리를 통해 한 칸의 거리를 10으로 둘 때 대각을 14로 계산한다. 계산을 하게 되면 맨하튼 방법에 비해 f 값이 더 정교해지지만 계산하는 부분에 의해 더 느릴 수 있다.

이는 대각선 이동이 가능한 상태에서 유클리드 기법을 통해 휴리스틱을 정한 경우이다.
빨간 부분은 탐색한 부분이고 파란 부분은 실제로 이동한 경로이다.

이동 경로 중 벽을 마주한다고해도 다를거 없이 똑같이 f 값을 계산하고 규칙을 따른다면 경로를 찾을 수 있다.