[알고리즘] A* 알고리즘(A star 알고리즘)이 뭘까?

 

 

 

 

A* 알고리즘이란?

 

 

 

 

그래프의 최단 경로를 찾기 위한 알고리즘으로, 다익스트라 알고리즘(Dijkstra' algorithm)과는 달리

 

 

 

 

예상 이동 비용인 휴리스틱(Heuristic) 거리값 h(n)이 사용된다는 차이점이 있다.

 

 

 

 

휴리스틱 거리값은 사전에 임의로 설정하는 값이고, 목표 위치까지의 거리 값을 

 

 

 

 

유클리드 거리 혹은 맨하탄 거리 값 등을 활용하여 사전에 설정하는 값이다.

 

 

 

 

휴리스틱 코스트 값은 다음과 같은 식이 성립된다.

 

 

 

 

휴리스틱 코스트 값 F(n) = 출발 지점부터 해당 위치까지의 비용 G(n) + 휴리스틱 거리 측정값 H(n)

 

 

 

 

해당 휴리스틱 코스트 값을 기반으로 가장 작은 값을 가지는 위치를 순차적으로 탐색하는 것이 바로 A* 알고리즘이다.

 

 

 

 

다익스트라 알고리즘은 도착 지점과 멀어지는 노드까지의 거리또한 최단 거리를 갱신하는 과정이 포함되어 있는 반면,

 

 

 

 

A* 알고리즘은 도착 지점을 향해 최단거리를 찾아가는 과정만을 진행하므로 다익스트라보다 효율적이다.

 

 

 

 

 

 

A* 알고리즘 예시

 

 

 

 

우선 다음과 같은 형태의 거리가 있다고 가정하자.

 

 

 

 

시작 상태

 

 

 

 

이번 예시에서는 휴리스틱 거리값을 맨하탄 거리를 기준으로, 출발지점으로부터의 거리는 유클리드 거리값을 반올림하여 설정하겠다.

 

 

 

 

시작 지점 주변의 위치들의 값들은 다음과 같이 된다.

 

 

 

 

주변 거리 측정 후 상태

 

 

 

 

시작 지점 주변 중 가장 휴리스틱 코스트 값이 작은 지점으로 이동한 뒤,

 

 

 

 

시작점에서와 마찬가지로 주변 지점의 휴리스틱 코스트 값을 구하면 다음과 같이 된다.

 

 

 

 

휴리스틱 코스트 값이 가장 작은 위치로 이동 후, 해당 위치를 거쳐서 갈 수 있는 지점들의 거리를 구한 상태

 

 

 

 

이런 방식으로 계속해서 반복해주면, 다음과 같이 노란색으로 칠해진 경로가 최단 경로가 된다.

 

 

 

 

거리를 다 계산 후 노란색 경로를 통해 최단 경로를 찾은 상태

 

 

 

 

위의 방식대로 거리를 측정할 때, 출발지점으로부터의 거리 계산 시 해당 위치에 도착하기 직전에 거친

 

 

 

 

부모 노드의 출발지점 거리 값 + 부모 노드로부터의 거리 값을 바탕으로 G(n)을 계산해야 한다.

 

 

 

 

즉, 출발 지점으로부터의 거리가 실제로는 짧을 지라도, 부모 노드의 출발 지점으로부터의 거리 G(n)에 값에 합하는 식으로 진행한다.