[Algorithm] A스타(A*) 알고리즘
A스타 알고리즘(A Star Algorithm) 이란?
A* 알고리즘은 시작 노드에서 목표 노드까지의 최단 경로를 찾기 위한 그래프 탐색 알고리즘입니다. 현재 노드에서 목표 노드까지의 “추정된” 최단 거리를 나타내는 휴리스틱 함수를 사용하여 탐색 방향을 결정합니다. 이 휴리스틱 덕분에 불필요한 탐색을 줄이고 목표 지점에 더 빠르게 도달할 수 있습니다.
(출처 : https://en.wikipedia.org/wiki/A*_search_algorithm)
핵심 개념
A* 알고리즘의 핵심은 평가 함수 f(n)입니다. 이 함수는 다음과 같이 정의됩니다.
- f(n) = g(n) + h(n)
각 부분은 다음과 같습니다.
- g(n): 시작 노드에서 현재 노드 n까지의 실제 비용 (경로 길이).
- h(n): 현재 노드 n에서 목표 노드까지의 추정 비용 (휴리스틱).
A* 알고리즘은 f(n) 값이 가장 작은 노드를 우선적으로 탐색합니다. 즉, 시작 지점으로부터의 실제 거리와 목표 지점까지의 추정 거리를 합쳐서 가장 유망한 노드를 선택하는 것입니다.
휴리스틱 함수 (h(n))
휴리스틱 함수는 A* 알고리즘의 성능에 큰 영향을 미칩니다. 좋은 휴리스틱 함수는 다음과 같은 특징을 가져야 합니다.
- 허용적(Admissible): 실제 비용보다 크지 않아야 합니다 (과대평가하지 않아야 함). 즉, 목표 지점까지의 실제 최단 거리보다 휴리스틱 값이 더 크면 안 됩니다. 이렇게 해야 최적의 해를 보장할 수 있습니다.
- 일관적(Consistent 또는 Monotonic): 삼각 부등식을 만족해야 합니다. 즉, 어떤 노드 a에서 인접 노드 b로 이동할 때, h(a) <= d(a, b) + h(b)를 만족해야 합니다. 여기서 d(a, b)는 노드 a에서 b까지의 실제 비용입니다. 일관적인 휴리스틱을 사용하면 이미 방문한 노드를 다시 방문하는 경우를 줄여 효율성을 높일 수 있습니다.
일반적으로 많이 사용되는 휴리스틱 함수는 다음과 같습니다.
-
맨해튼 거리 (Manhattan Distance): 격자 형태의 맵에서 가로/세로 방향으로만 이동 가능한 경우 사용합니다. h(n) = n.x - goal.x + n.y - goal.y - 유클리드 거리 (Euclidean Distance): 직선 거리를 사용합니다. h(n) = sqrt((n.x - goal.x)^2 + (n.y - goal.y)^2)
-
체비셰프 거리 (Chebyshev Distance): 8방향 이동이 가능한 경우 사용합니다. h(n) = max( n.x - goal.x , n.y - goal.y )
동작방식
- 시작 노드를 열린 목록(Open List)에 넣습니다.
- 열린 목록이 비어 있지 않은 동안 다음을 반복합니다.
- 열린 목록에서
f(n)값이 가장 작은 노드current를 꺼냅니다. current가 목표 노드이면 탐색을 종료합니다.current를 닫힌 목록(Closed List)에 넣습니다.current의 모든 인접 노드 neighbor에 대해 다음을 수행합니다.neighbor가 닫힌 목록에 있으면 건너뜁니다.- 새로운 경로의
g(neighbor)값을 계산합니다(g(neighbor) = g(current) + cost(current, neighbor)). - neighbor가 열린 목록에 없거나, 새로운
g(neighbor)값이 기존g(neighbor)값보다 작다면,- neighbor의 부모 노드를
current로 설정합니다. g(neighbor)와h(neighbor)를 계산하고f(neighbor)를 계산합니다.- neighbor를 열린 목록에 추가합니다 (기존에 있었다면 갱신).
- neighbor의 부모 노드를
- 열린 목록에서
다익스트라 알고리즘과의 비교
- 다익스트라: 시작점에서 모든 정점까지의 최단 경로를 구함, 휴리스틱 사용 X, 음수 가중치 X
- A:* 시작점에서 목표 지점까지의 최단 경로를 구함, 휴리스틱 사용 O, 음수 가중치 X
A*는 휴리스틱 함수를 사용하여 탐색 방향을 효율적으로 결정하기 때문에, 목표 지점이 명확한 경우 다익스트라보다 훨씬 빠르게 해를 찾을 수 있습니다.
하지만 휴리스틱 함수의 선택이 중요하며, 잘못된 휴리스틱 함수는 성능 저하를 초래할 수 있습니다.
시간 복잡도
A* 알고리즘의 시간 복잡도는 휴리스틱 함수의 정확도와 그래프의 특성에 따라 달라집니다.
- 최악의 경우: 모든 노드를 탐색해야 하는 경우, 다익스트라 알고리즘과 마찬가지로 O(E log V) (E는 간선의 수, V는 정점의 수)가 될 수 있습니다.
- 평균적인 경우: 적절한 휴리스틱 함수를 사용하는 경우, 다익스트라 알고리즘보다 훨씬 빠른 성능을 보입니다.
- 최상의 경우: 휴리스틱 함수가 매우 정확하여 목표 지점을 바로 찾을 수 있는 경우, O(V)에 가까운 성능을 보일 수 있습니다.
활용 예시
- 게임 AI: 게임 캐릭터의 이동 경로 탐색, 적의 추적 등
- 네비게이션 시스템: 자동차, 보행자 네비게이션에서 최단 경로 또는 최적 경로 안내
- 로봇 공학: 로봇의 경로 계획, 장애물 회피
- 물류 및 운송: 물류 최적화, 배송 경로 계획
- 지도 탐색: 온라인 지도 서비스에서 경로 검색
- 컴퓨터 네트워크: 네트워크 라우팅
장단점
장점
- 효율적인 최단 경로 탐색: 휴리스틱 함수를 사용하여 불필요한 탐색을 줄이므로, 다익스트라 알고리즘보다 훨씬 빠르게 목표 지점에 도달할 수 있습니다. 특히, 넓은 공간이나 복잡한 환경에서 그 효율성이 두드러집니다.
- 최적 해 보장 (조건부): 휴리스틱 함수가 허용적(admissible)이라면, 즉 목표 지점까지의 실제 비용을 과대평가하지 않는다면 최적의 해 (최단 경로)를 찾을 수 있음을 보장합니다.
- 직관적인 알고리즘: 시작점으로부터의 실제 거리(g(n))와 목표점까지의 추정 거리(h(n))를 함께 고려하여 탐색하므로,
단점
- 휴리스틱 함수에 대한 의존성: 알고리즘의 성능은 휴리스틱 함수의 정확도에 크게 의존합니다.
- 정확한 휴리스틱 함수를 설계하는 것이 어려울 수 있습니다.
- 휴리스틱 함수가 실제 비용을 너무 과대평가하면 최적의 해를 찾지 못할 수 있습니다.
- 반대로 휴리스틱 함수가 너무 작으면 (0에 가깝다면) 다익스트라 알고리즘과 유사하게 동작하여 효율성이 떨어질 수 있습니다.
- 메모리 사용량: 탐색해야 할 공간이 넓어질수록 열린 목록(Open List)에 저장해야 하는 노드의 수가 많아져 메모리 사용량이 증가할 수 있습니다.
- 환경 변화에 대한 대응: 탐색 도중 환경이 바뀌는 경우 (예: 장애물이 새로 생기는 경우) 기존 탐색 결과를 다시 계산해야 하는 경우가 발생할 수 있습니다. 즉, 동적인 환경에 유연하게 대처하기 어렵습니다.
예제
[격자 맵, 맨해튼 거리 사용]
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;
struct Node {
int x, y;
int g, h, f;
Node* parent;
Node(int x, int y) : x(x), y(y), g(0), h(0), f(0), parent(nullptr) {}
bool operator>(const Node& other) const {
return f > other.f; // 우선순위 큐에서 f 값이 작은 노드가 먼저 나오도록
}
};
int manhattanDistance(int x1, int y1, int x2, int y2) {
return abs(x1 - x2) + abs(y1 - y2);
}
int main() {
int mapWidth = 5;
int mapHeight = 5;
pair<int, int> start = {0, 0};
pair<int, int> goal = {4, 4};
vector<vector<bool>> grid(mapHeight, vector<bool>(mapWidth, true)); // 맵 (true: 이동 가능, false: 벽)
priority_queue<Node, vector<Node>, greater<Node>> openList;
vector<vector<Node*>> nodeMap(mapHeight, vector<Node*>(mapWidth, nullptr));
vector<vector<bool>> closedList(mapHeight, vector<bool>(mapWidth, false));
Node* startNode = new Node(start.first, start.second);
nodeMap[start.second][start.first] = startNode;
openList.push(*startNode);
while (!openList.empty()) {
Node current = openList.top();
openList.pop();
if (current.x == goal.first && current.y == goal.second) {
// 경로 찾음
vector<pair<int,int>> path;
Node* trace = nodeMap[current.y][current.x];
while(trace != nullptr){
path.push_back({trace->x, trace->y});
trace = trace->parent;
}
reverse(path.begin(), path.end());
cout << "Path found: " << endl;
for(auto& p : path){
cout << "(" << p.first << ", " << p.second << ") ";
}
cout << endl;
return 0;
}
closedList[current.y][current.x] = true;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
for (int i = 0; i < 4; i++) {
int nx = current.x + dx[i];
int ny = current.y + dy[i];
if (nx >= 0 && nx < mapWidth && ny >= 0 && ny < mapHeight && grid[ny][nx] && !closedList[ny][nx]) {
if(nodeMap[ny][nx] == nullptr){
nodeMap[ny][nx] = new Node(nx, ny);
}
Node* neighbor = nodeMap[ny][nx];
int newG = current.g + 1;
if (neighbor->parent == nullptr || newG < neighbor->g) {
neighbor->g = newG;
neighbor->h = manhattanDistance(nx, ny, goal.first, goal.second);
neighbor->f = neighbor->g + neighbor->h;
neighbor->parent = nodeMap[current.y][current.x];
openList.push(*neighbor);
}
}
}
}
cout << "No path found." << endl;
return 0;
}
[인접 리스트와 유클리드 거리를 사용]
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <limits>
using namespace std;
// ... (Node 구조체는 이전 예제와 유사)
double euclideanDistance(int x1, int y1, int x2, int y2) {
return sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
}
int main() {
// 인접 리스트로 그래프 표현 (예시)
vector<vector<pair<int, double>>> adj(5); // 각 정점에 연결된 (정점 번호, 가중치) 쌍 저장
// ... (간선 추가)
// ... (A* 알고리즘 구현, 휴리스틱 함수만 euclideanDistance로 변경)
// neighbor->h = euclideanDistance(nx, ny, goal.first, goal.second);
return 0;
}