A* 알고리즘

다익스트라 알고리즘을 찾으면서 최단 경로 알고리즘으로 a* 알고리즘이 있어서 작성을 하게 되었다.

다익스트라(Dijkstra) 알고리즘은 시작 노드만을 정하고 각 노드간의 최단 경로를 파악하였습니다.
A* 알고리즘은 목적지를 정하고 두 노드간의 최단 경로를 구하는 알고리즘입니다.

현재 드론이나 로봇 차량의 인공지능 주행을 구현하기 위해 사용되고 있습니다.

g(X) : 출발 노드부터 현재 노드 x까지의 경로 가중치
h(x) : 휴리스틱 추정값, 현재 노트 x로부터 목표 노드까지의 추정 경로 가중치
f(x) : g(x) + h(x), 경로를 도출하기 위한 함수로 최소값을 우선적으로 탐색한다.

그러면 g는 출발 노드도 알 수 있고, 현재의 노드도 알 수 있어서 계산 할 수 있지만 h는 어떤 방식으로 추정해야 될까요?

장애물이 없다는 가정하에 3가지 방법을 소개합니다.

1. 맨하튼 거리

• 네 방향(위, 아래, 오른쪽, 왼쪽)으로만 이동 가능할 때
• 현재의 셀 x 와 y 좌표, 목표의 x, y간의 절대값의 차이만큼을 더합니다.

 h = abs(current_cell.x – goal.x) + abs(current_cell.y – goal.y)

2. 대각선 거리

• 여덟 방향으로만 움직일 수 있을 때 사용합니다.
• 체스에서 King의 이동 가능한 경우의 수와 유사합니다.

dx = abs(current_cell.x – goal.x)
dy = abs(current_cell.y – goal.y)
h = D * (dx + dy) + (D2 - 2 * D) * 최소(dx, dy)

3. 유클리드 거리

• 모든 방향으로 이동할 수 있는 경우 사용합니다.
• 좌표평면에서 두 점 사이의 거리를 구하는 공식을 활용하여서 거리를 계산합니다.

h = sqrt ((current_cell.x – gaol.x)**2 + ((current_cell.y – goal.y)** 2)

a* 알고리즘 코드는 나중에 시간이 되면 짜보는 것으로....
참고 사이트
링크텍스트