A* (A-star) 알고리즘은 그래프 탐색 및 최단 경로 문제를 해결하는 휴리스틱(heuristic) 기반의 알고리즘입니다. 다익스트라 알고리즘과 유사하지만, 특정 방향으로 더 빠르게 탐색할 수 있도록 휴리스틱 함수를 사용하여 성능을 향상시킵니다.
개념
A* 알고리즘은 **비용 함수 f(n)**을 사용하여 최적의 경로를 찾습니다.
비용 함수는 다음과 같이 정의됩니다.
f(n) = g(n) + h(n)
- g(n) : 시작 노드에서 현재 노드까지의 실제 비용
- h(n) : 현재 노드에서 목표 노드까지의 예상 비용(휴리스틱 함수)
이러한 방식으로 탐색을 진행하면, 다익스트라 알고리즘보다 더 효율적으로 목표 지점까지의 최단 경로를 찾을 수 있습니다.
휴리스틱(Heuristic) 함수란?
휴리스틱 함수는 탐색 공간을 줄이고 최적 경로를 빠르게 찾도록 도와주는 함수입니다. 일반적으로 목표까지의 예상 비용을 제공하며, 정확성과 성능 사이에서 균형을 맞추는 것이 중요합니다. 휴리스틱 함수의 종류에는 다음과 같은 것들이 있습니다.
- 맨해튼 거리(Manhattan Distance): 격자 기반 탐색에서 사용되며, 이동이 수직 또는 수평으로만 가능할 때 적합합니다.
h(n)=∣x1−x2∣+∣y1−y2∣h(n) = |x1 - x2| + |y1 - y2| - 유클리드 거리(Euclidean Distance): 대각선 이동이 가능한 환경에서 적절합니다.
h(n)=(x1−x2)2+(y1−y2)2h(n) = \sqrt{(x1 - x2)^2 + (y1 - y2)^2} - 체스판 거리(Chebyshev Distance): 모든 방향 이동이 가능할 때 활용됩니다.
h(n)=max(∣x1−x2∣,∣y1−y2∣)h(n) = \max(|x1 - x2|, |y1 - y2|)
적절한 휴리스틱 함수를 선택하는 것은 A* 알고리즘의 성능을 결정짓는 중요한 요소입니다.
동작 과정
- 시작 노드를 열린 리스트(Open List)에 추가합니다.
- 열린 리스트에서 f(n) 값이 가장 작은 노드를 선택하여 확장합니다.
- 선택한 노드의 이웃 노드들을 확인하고, g(n)과 h(n)을 계산하여 열린 리스트에 추가합니다.
- 만약 목표 노드에 도달하면 탐색을 종료하고 경로를 반환합니다.
- 열린 리스트가 비어 있다면 경로가 존재하지 않는 것으로 판단합니다.
특징
- 최단 경로 보장: h(n)이 최적성을 만족하는 경우(예: 유클리드 거리) 최적의 경로를 찾을 수 있습니다.
- 효율성: 다익스트라보다 빠르게 동작하며, 탐색을 최적화할 수 있습니다.
- 유연성: 다양한 휴리스틱 함수를 적용하여 문제에 맞게 조정할 수 있습니다.
구현 (C#)
using System;
using System.Collections.Generic;
using System.Linq;
class Node : IComparable<Node>
{
public (int, int) Position;
public Node Parent;
public int G, H;
public int F => G + H;
public Node((int, int) position, Node parent = null, int g = 0, int h = 0)
{
Position = position;
Parent = parent;
G = g;
H = h;
}
public int CompareTo(Node other) => F.CompareTo(other.F);
}
class AStar
{
public static List<(int, int)> FindPath(int[,] grid, (int, int) start, (int, int) end)
{
var openList = new SortedSet<Node>(Comparer<Node>.Create((a, b) => a.F == b.F ? a.G.CompareTo(b.G) : a.F.CompareTo(b.F)));
var closedSet = new HashSet<(int, int)>();
var startNode = new Node(start, null, 0, Heuristic(start, end));
openList.Add(startNode);
while (openList.Any())
{
var currentNode = openList.Min;
openList.Remove(currentNode);
if (currentNode.Position == end)
return ReconstructPath(currentNode);
closedSet.Add(currentNode.Position);
foreach (var (dx, dy) in new (int, int)[] { (-1, 0), (1, 0), (0, -1), (0, 1) })
{
var neighborPos = (currentNode.Position.Item1 + dx, currentNode.Position.Item2 + dy);
if (closedSet.Contains(neighborPos) || !IsValid(grid, neighborPos))
continue;
int g = currentNode.G + 1;
int h = Heuristic(neighborPos, end);
var neighborNode = new Node(neighborPos, currentNode, g, h);
openList.Add(neighborNode);
}
}
return null;
}
private static int Heuristic((int, int) a, (int, int) b)
{
return Math.Abs(a.Item1 - b.Item1) + Math.Abs(a.Item2 - b.Item2); // 맨해튼 거리 사용
}
private static List<(int, int)> ReconstructPath(Node node)
{
var path = new List<(int, int)>();
while (node != null)
{
path.Add(node.Position);
node = node.Parent;
}
path.Reverse();
return path;
}
private static bool IsValid(int[,] grid, (int, int) position)
{
int x = position.Item1, y = position.Item2;
return x >= 0 && x < grid.GetLength(0) && y >= 0 && y < grid.GetLength(1) && grid[x, y] == 0;
}
}
활용 사례
- 게임 AI (예: 캐릭터 이동 경로 찾기)
- 지도 탐색 (예: Google Maps 길찾기)
- 로봇 경로 계획 (예: 자율주행 차량)
- 네트워크 라우팅 (최적 경로 탐색)
A* 알고리즘은 다양한 분야에서 강력한 탐색 알고리즘으로 사용됩니다.
Q&A
Q: A* 알고리즘은 어떤 문제에 적합한가요?
A: A* 알고리즘은 최단 경로 탐색이 필요한 다양한 문제에 적용됩니다. 예를 들어, 게임 AI, 지도 탐색, 로봇 경로 계획, 네트워크 라우팅 등에 유용합니다.
Q: A* 알고리즘과 다익스트라 알고리즘의 차이점은 무엇인가요?
A: 다익스트라 알고리즘은 모든 경로의 비용을 고려하지만, A* 알고리즘은 휴리스틱 함수를 추가로 사용하여 탐색을 최적화합니다.