[알고리즘 알아보기] A* 알고리즘 알아보기

개요

A*알고리즘은 최적의 경로를 찾는 알고리즘입니다. 

비슷한 알고리즘으로는 다익스트라 알고리즘이 있는데 이를 개선, 확장한 알고리즘입니다.

이 포스팅에서는 2차원을 한정해서 알아보겠습니다.

 

다익스트라 알고리즘은 2차원 평면에서 거리 기반으로 값을 계산하게 되는데 이는 그리드가 크면 클수록 시간, 메모리가 낭비되는 문제가 생깁니다.

 

A*알고리즘은 목적지에 도달할 가능성이 높은 위치로 노드를 확장해 계산 회수를 줄입니다.

이 알고리즘은 Shakey로봇의 주행을 위해 고안되었다고 합니다.

https://en.wikipedia.org/wiki/Shakey_the_robot 

Shakey the robot - Wikipedia

---

A*알고리즘의 개념

위에서 목적지에 도달할 가능성이 높은 위치에 노드를 생성한다고 했는데 이는 휴리스틱 함수를 활용해 계산합니다.

f(n) = g(n) + h(n)

위의 수식이 우선순위를 결정하는 식입니다.

여기서 g(n)은 노드간 거리의 누적 값이고, h(n)은 휴리스틱 함수를 통해 얻어진 값입니다.

h(n)을 사용하지 않는다면 다익스트라 알고리즘와 같아질 것입니다.

 

여기서 휴리스틱 추정값이라고 하면 어렵게 느껴질 수도 있지만, 현재 위치에서 목적지까지의 맨하탄 거리 혹은 유클리드 거리를 주로 사용합니다.

 

목적지로부터 가까워질 수록 해당 위치는 목적지에 도달할 확률이 높아질 것입니다. 따라서 이러한 추정은 간단하면서도 합리적이라고 볼 수 있습니다.

 

openset과 closeSet

A*알고리즘을 구현하기 위해서는 openSet, closeSet자료구조를 사용합니다.

closeSet의 경우 방문한 위치를 저장해 다시 방문하지 않겠다는 표시를 합니다. (일반적인 visted 배열과 비슷합니다.)

openSet의 경우 노드의 위치를 저장합니다. 이 때 key를 노드의 f값으로한  priority queue를 사용해 저장합니다.

 

경로 복원용 자료구조

A*알고리즘으로 노드가 목적지를 찾았을 때 출발지부터 목적지까지의 경로를 얻어야합니다.

이 때 구현 상으로 현재 노드에서 다음 노드의 위치를 저장하는 것보다 노드가 어느 노드를 통해 생성되었는 지를 저장하는 것이 훨씬 간편합니다.

따라서 노드가 생성될 때 노드에 대한 부모 노드의 위치를 함께 저장하게됩니다.

 

 

구현 결과

 

위는 로직 구현 후 탐색 결과를 시각화한 것입니다.

빨간 셀은 시작점, 초록 셀은 도착점입니다.

파란 셀은 openlist에 있어서 노드 생성의 후보가 되는 셀입니다. 파란 셀에 있는 숫자는 f값입니다.

노란 셀은 탐색해 closelist에 있는 셀입니다.

 

도착지에 도착한 후 parent를 찾아가며 전체 경로를 반환하고 이를 선으로 이어 별도로 시각화 했습니다.

---

다음에는 A*알고리즘을 개선한 JPS알고리즘과 결과 경로를 보정하기 위한 브레젠험 알고리즘에 대해 알아보겠습니다.