A-Star 길찾기 알고리즘
A* 알고리즘 이해하기
A* 알고리즘(A-star)은 최단 경로 탐색 알고리즘 중 하나로, 그래프 또는 그리드 상에서 두 지점 사이의 최적 경로를 찾는 문제에 자주 사용됩니다. 이 알고리즘은 다익스트라 알고리즘과 탐욕 알고리즘(Greedy Algorithm)의 장점을 결합하여, 효율적으로 최단 경로를 탐색합니다. A*는 주로 게임 개발(예: 길 찾기)이나 로봇 공학, 네비게이션 시스템 등에서 활용됩니다.
이번 포스팅에서는 A* 알고리즘의 개념, 동작 방식, 코드 구현, 그리고 실제 사례를 통해 A* 알고리즘을 이해해 보겠습니다.
1. A* 알고리즘 개념
A* 알고리즘은 경로를 탐색할 때 휴리스틱(Heuristic)을 사용하여, 탐색할 다음 노드를 결정합니다.
A 알고리즘의 핵심은 비용 함수 f(n)f(n)을 기반으로 노드를 선택하는 것입니다.
이 비용 함수는 다음과 같이 정의됩니다.
f(n)=g(n)+h(n)f(n) = g(n) + h(n)
- g(n): 시작 노드에서 현재 노드 n까지의 실제 비용
- h(n): 현재 노드 n에서 목표 노드까지의 추정 비용(휴리스틱 함수)
1.1. 휴리스틱 함수
h(n)는 A 알고리즘의 탐색 효율성을 높이는 데 중요한 역할을 합니다.
이 함수는 현재 노드에서 목표 노드까지의 "추정 거리"를 계산하는 방법입니다.
일반적으로 다음 두 가지 방식이 많이 사용됩니다:
- 맨해튼 거리(Manhattan Distance): 격자형 지도에서 수평 및 수직 이동만 허용될 때 사용.
- 유클리드 거리(Euclidean Distance): 노드 간 직선 거리를 사용하여 추정.
2. A* 알고리즘 동작 방식
A* 알고리즘의 탐색 과정은 다음과 같습니다:
- 시작 노드를 Open 리스트에 추가합니다. 이 Open 리스트는 아직 탐색하지 않은 노드의 목록입니다.
- Open 리스트에서 f(n) 값이 가장 작은 노드를 선택하고, 이를 현재 노드로 설정합니다.
- 현재 노드를 Close 리스트에 추가하고, 이 노드는 탐색이 완료된 것으로 간주합니다.
- 현재 노드와 연결된 인접 노드들을 확인하고, 각각에 대해 f(n) 값을 계산합니다. 인접 노드들이 Open 리스트에 없으면 추가하고, 더 작은 f(n) 값이 있으면 갱신합니다.
- 목표 노드에 도달할 때까지 2-4 과정을 반복합니다.
- 목표 노드에 도달하면, 경로를 역추적하여 최단 경로를 도출합니다.
3. A* 알고리즘 코드 구현 (C# 예시)
다음은 C#으로 A 알고리즘을 구현한 예시입니다.
public class Node
{
public int X { get; }
public int Y { get; }
public int G { get; set; } // 시작점부터 현재 노드까지의 거리
public int H { get; set; } // 휴리스틱 값 (현재 노드에서 목표 노드까지의 추정 거리)
public int F => G + H; // f(n) = g(n) + h(n)
public Node Parent { get; set; }
public Node(int x, int y)
{
X = x;
Y = y;
}
}
public class AStar
{
private static int Heuristic(Node a, Node b)
{
// 맨해튼 거리 사용
return Math.Abs(a.X - b.X) + Math.Abs(a.Y - b.Y);
}
public static List<Node> FindPath(Node start, Node goal, List<Node> allNodes)
{
var openList = new List<Node> { start };
var closedList = new HashSet<Node>();
start.G = 0;
start.H = Heuristic(start, goal);
while (openList.Count > 0)
{
var current = openList.OrderBy(node => node.F).First();
if (current.X == goal.X && current.Y == goal.Y)
{
return ReconstructPath(current);
}
openList.Remove(current);
closedList.Add(current);
foreach (var neighbor in GetNeighbors(current, allNodes))
{
if (closedList.Contains(neighbor)) continue;
int tentativeG = current.G + 1;
if (!openList.Contains(neighbor))
{
openList.Add(neighbor);
}
else if (tentativeG >= neighbor.G)
{
continue;
}
neighbor.Parent = current;
neighbor.G = tentativeG;
neighbor.H = Heuristic(neighbor, goal);
}
}
return null; // 목표 노드에 도달할 수 없는 경우
}
private static List<Node> ReconstructPath(Node current)
{
var path = new List<Node>();
while (current != null)
{
path.Add(current);
current = current.Parent;
}
path.Reverse();
return path;
}
private static List<Node> GetNeighbors(Node node, List<Node> allNodes)
{
// 인접 노드 찾기 (상하좌우)
var neighbors = new List<Node>();
var directions = new (int, int)[] { (0, 1), (1, 0), (0, -1), (-1, 0) };
foreach (var (dx, dy) in directions)
{
var neighbor = allNodes.FirstOrDefault(n => n.X == node.X + dx && n.Y == node.Y + dy);
if (neighbor != null)
{
neighbors.Add(neighbor);
}
}
return neighbors;
}
}3.1. 코드 설명
- Node 클래스: 그래프에서 각각의 노드를 표현하며, G(시작점까지의 거리), H(목표까지의 추정 거리), F(전체 비용) 등을 가지고 있습니다.
- AStar 클래스: A* 알고리즘을 수행하는 클래스입니다. 시작 노드에서 목표 노드까지의 경로를 찾고, 그 경로를 반환합니다.
- Heuristic 함수: 맨해튼 거리 기반으로 휴리스틱 값을 계산합니다.
- ReconstructPath 함수: 목표 노드에 도달한 후, 경로를 역추적하여 반환합니다.
4. A* 알고리즘 사용 사례
- 게임 개발: A* 알고리즘은 게임에서 적 AI나 플레이어의 이동 경로를 계산하는 데 사용됩니다. 특히 격자형 타일 맵에서 가장 흔하게 쓰입니다.
- 로봇 경로 계획: 로봇이 장애물을 피하면서 특정 목표 지점까지 이동하는 데 A*가 사용됩니다.
- 지도 및 네비게이션: 도시 내에서 차량의 최단 경로를 찾는 GPS 시스템에서도 활용됩니다.
5. A* 알고리즘의 성능 및 최적화
A* 알고리즘의 성능은 휴리스틱 함수의 정확성에 크게 의존합니다. 잘 설계된 휴리스틱 함수는 탐색의 효율성을 극대화하며, 너무 느슨하거나 부정확한 휴리스틱은 불필요한 노드 탐색을 야기할 수 있습니다. 따라서, 문제의 특성에 맞는 휴리스틱 함수를 사용하는 것이 중요합니다.
- 최적화: 휴리스틱 함수가 실제 최단 경로의 비용보다 과소 추정되는 경우(A*가 애드미시블(Admissible)), 최적의 경로를 보장할 수 있습니다. 맨해튼 거리나 유클리드 거리는 일반적인 격자형 맵에서 자주 쓰이는 방법입니다.
A* 알고리즘은 다양한 문제에서 최단 경로를 효율적으로 찾는 강력한 도구입니다.
다익스트라 알고리즘과 탐욕 알고리즘을 결합하여, 경로 탐색과 최적화를 동시에 고려하는 A*는 성능과 정확성 측면에서 뛰어난 결과를 제공합니다.
특히 게임 개발, 로봇 공학, 네비게이션 등 여러 분야에서 필수적으로 사용되는 알고리즘으로, 그 구현과 원리를 잘 이해하면 더 복잡한 문제에도 응용할 수 있습니다.