A* algorithm
개요
에이스타 알고리즘(A* algorithm)은 다익스트라 알고리즘을 확장하여 만들어진 경로 탐색 알고리즘이다. 다익스트라 알고리즘이 가장 최소의 비용으로 도달한 지점부터 모든 정점에 대해 탐색한다면 에이스타 알고리즘은 모든 정점이 아닌 시작점과 목표지점 간의 최소 비용을 탐색한다는 차이가 있다.
에이스타 알고리즘이 등장하게 된 배경은 다익스트라 알고리즘을 현실 문제에 적용시키기에는 연산량이 부담되기 때문이다. 사람이 다니는 도로는 굉장히 다양하기에 이를 전부 노드화하여 탐색을 할 때 다익스트라 알고리즘을 적용할 경우의 탐색 시간은 아득히 오래 걸릴 것이다.
동작
에이스타 알고리즘의 동작 순서를 나타내면 다음과 같다.
- 시작 정점과 목표 정점 간의 최단 비용 계산
- 정점의 값(F)를 현재까지의 비용(G)과 목표지점까지의 비용(H)의 합으로 계산(F = G + H)
- 방문 예정 정점을 F값을 기준으로 우선순위 큐에 저장하여 다음 방문 정점을 빠르게 도출
목표지점까지의 비용인 H를 휴리스틱이라고 하여 이를 조절해 최단거리를 확실하게 보장하도록하거나, 탐색 시간을 줄이도록 하는 것이 가능하다. 따라서 A* 알고리즘을 기반으로 목적에 따라 다양한 알고리즘이 파생되었다.
구현
A* 알고리즘 구현에는 우선순위 큐가 사용되는데 이는 이전 포스트에서 구현한 것을 그대로 활용했다. 휴리스틱 함수(H)로 두 정점 사이의 직선 거리를 피타고라스 법칙을 사용하여 계산했다.
Node : IComparable
우선 각 정점의 데이터를 담기 위한 Node 클래스가 필요하다. 기본적으로 총 비용인 F, 현재까지의 비용인 G, Index를 property로써 가지며, 우선순위 큐에 넣기 위해 인터페이스 IComparable을 상속하여 CompareTo()를 F값을 기준으로 구현했다.
class Node : IComparable<Node>
{
public int Index;
public float F;
public float G;
public int CompareTo(Node? other)
{
if (F == other.F)
{
return 0;
}
return F < other.F ? 1 : -1;
}
}struct, 기타 Method
정점의 좌표를 저장하기 위한 point 구조체 하나를 선언하고, 피타고라스 법칙을 활용한 거리 계산 메서드를 static으로 구현했다.
struct Point
{
public int X;
public int Y;
}
static float CalDistance(int x, int y)
{
float powSum = (float)(Math.Pow(x, 2) + Math.Pow(y, 2));
return (float)Math.Round(Math.Sqrt(powSum), 2);
}A* algorithm Method
A* 알고리즘에서 최단 경로 탐색은 while 반복문 내부에서 일어나게 된다. 현재 방문한 정점이 목표 정점과 같은 경우 반복문이 끝나게 되며, 시작 정점부터 목표 정점에 도달할 때까지 경유한 정점을 출력하고, 해당 비용을 출력하도록 구현했다.
static void Astar(float[,] graph, Point[] points, int start, int goal)
{
// 사용 편의를 위한 캐싱
int goalX = points[goal].X;
int goalY = points[goal].Y;
// 정점(노드)의 개수
int size = graph.GetLength(0);
// 각 정점의 비용 데이터를 담기 위한 배열
float[] cost = new float[size];
// 각 정점의 비용을 Max값으로 세팅
Array.Fill(cost, float.MaxValue);
// 각 정점의 방문 여부 데이터를 담기 위한 배열
bool[] visited = new bool[size];
// 정점의 데이터를 담을 우선순위 큐<Node> 생성
PriorityQueue<Node> que = new PriorityQueue<Node>();
// 1. 시작 정점과 목표 정점 간의 최단 비용 계산
float distance = CalDistance(
(goalX - points[start].X), (goalY - points[start].Y));
// 우선순위 큐에 시작 정점 데이터 저장
que.Enqueue(new Node { F = distance, G = 0, Index = start});
// 최단 경로를 탐색하기 위한 반복문 진입
while (que.Count > 0)
{
// 현재 방문한 노드의 데이터를 지역 변수로 캐싱
Node curNode = que.Dequeue();
int cur = curNode.Index;
// 방문 여부 확인하고 이미 방문했을 경우 스킵
if (visited[cur])
{
continue;
}
// 방문 여부 true로 저장 후 방문 내역 출력
visited[cur] = true;
Console.WriteLine($"{cur}번 정점 방문");
// 현재 방문한 정점이 목표 정점인 경우 반복문 종료
if (cur == goal)
{
break;
}
// 현재 방문 정점으로부터 모든 정점에 대한 데이터 수집을 위한 반복문
for(int next = 0; next < size; next++)
{
// 이미 방문한 정점이거나, 연결되지 않은 정점은 스킵
if (visited[next] || graph[cur, next] < 0)
{
continue;
}
// 2-1.Next 정점에 대한 목표지점까지의 비용(H) 계산
float H = CalDistance(
(goalX - points[next].X), (goalY - points[next].Y));
// 2-2 Next 정점에 대한 현재까지의 비용(G) 계산
float G = curNode.G + graph[cur, next];
// 도출된 F(G + H)값이 이전에 계산된 비용(F)보다 높다면 스킵
if (G + H > cost[next])
{
continue;
}
// 2-3 Next 정점에 대한 총 비용(F) 갱신
cost[next] = G + H;
// 3. 방문 예정 정점을 우선순위 큐에 저장하여 다음 방문 정점을 도출
que.Enqueue(new Node(){ F = G + H, G = G, Index = next});
}
}
// 계산된 경로에 대한 비용 출력
Console.WriteLine
($"{start}번 정점부터 {goal}번 정점까지의 최단 거리 : {Math.Round(cost[goal],2)}");
}test code
테스트 코드는 해당 블로그를 참고했다.
static void Main(string[] args)
{
float[,] graph =
{
{ -1f, 2.0f, 2.83f, 3.16f, -1f, -1f, -1f },
{ 2.0f, -1f, 2.0f, -1f, -1f, 1.41f, -1f },
{ 2.83f, 2.0f, -1f, 1.41f, 2.24f, 1.41f, -1f },
{ 3.16f, -1f, 1.41f, -1f, 2.24f, -1f, -1f },
{ -1f, -1f, 2.24f, 2.24f, -1f, -1f, 1.0f },
{ -1f, 1.41f, 1.41f, -1f, -1f, -1f, 3.16f },
{ -1f, -1f, -1f, -1f, 1.0f, 3.16f, -1f }
};
Point[] points =
{
new Point() { X = 0, Y = 0 },
new Point() { X = 2, Y = 0 },
new Point() { X = 2, Y = 2 },
new Point() { X = 1, Y = 3 },
new Point() { X = 3, Y = 4 },
new Point() { X = 3, Y = 1 },
new Point() { X = 4, Y = 4 }
};
Astar(graph, points, 0, 6);
}0번 정점 방문
2번 정점 방문
4번 정점 방문
6번 정점 방문
0번 정점부터 6번 정점까지의 최단 거리 : 6.07