A* 알고리즘 은 휴리스틱 기반 최단 경로 탐색 알고리즘. f(n)=g(n)+h(n) 을 평가 함수로 사용해 시작점에서 목표까지의 최단 경로를 찾는다. 1968년 Hart, Nilsson, Raphael이 제안.
Dijkstra의 일반화로, 휴리스틱 h(n) 이 admissible(목표까지 실제 비용 이하) 이면 최적해 보장.
문제 상황과 동기
가중치가 있는 그래프에서 s에서 t까지 최단 경로.
Dijkstra: 모든 방향 동등하게 확장. h(n)=0 인 A* 와 동일.
A*: “목표 방향” 정보를 h(n) 으로 주입. 불필요한 방향 확장 억제.
핵심 통찰: 남은 거리 예측치 h(n) 을 비용에 더하면 목표 방향으로 먼저 탐색. g(n) 은 이미 지나온 비용, h(n) 은 앞으로 남은 예측.
시각화
핵심 아이디어
open set 과 closed set 을 유지. open 에서 f(n)=g(n)+h(n) 이 가장 작은 노드를 꺼내 확장.
openSet = {start}g[start] = 0, h[start] = heuristic(start, goal)f[start] = g[start] + h[start]while openSet not empty: current = node in openSet with smallest f if current == goal: 복원 후 반환 openSet.remove(current) for each neighbor v of current: tentative_g = g[current] + w(current, v) if tentative_g < g[v]: g[v] = tentative_g f[v] = g[v] + heuristic(v, goal) openSet.insert(v)
h(n) 이 admissible(과대추정 안 함) 이면 A* 는 항상 최적 경로를 찾는다.
구현
// A*, priority queue + Manhattan heuristic (grid 예제)#include <bits/stdc++.h>using namespace std;using pii = pair<int,int>;int heuristic(pii a, pii b) { return abs(a.first - b.first) + abs(a.second - b.second);}int dx[] = {0,0,1,-1};int dy[] = {1,-1,0,0};int astar(vector<string>& grid, pii start, pii goal) { int n = grid.size(), m = grid[0].size(); vector<vector<int>> g(n, vector<int>(m, 1e9)); priority_queue<pair<int,pii>, vector<pair<int,pii>>, greater<pair<int,pii>>> pq; g[start.first][start.second] = 0; int h_start = heuristic(start, goal); pq.push({h_start, start}); while (!pq.empty()) { auto [f, cur] = pq.top(); pq.pop(); auto [x, y] = cur; if (cur == goal) return g[x][y]; for (int d = 0; d < 4; d++) { int nx = x + dx[d], ny = y + dy[d]; if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; if (grid[nx][ny] == '#') continue; int ng = g[x][y] + 1; if (ng < g[nx][ny]) { g[nx][ny] = ng; int f = ng + heuristic({nx, ny}, goal); pq.push({f, {nx, ny}}); } } } return -1;}int main() { vector<string> grid = { ".....", ".#.#.", ".#.#.", ".#...", "....." }; pii start = {0,0}, goal = {4,4}; cout << astar(grid, start, goal); return 0;}
# A*, heapq + Manhattan heuristicimport heapqdef heuristic(a, b): return abs(a[0] - b[0]) + abs(a[1] - b[1])def astar(grid, start, goal): n, m = len(grid), len(grid[0]) INF = 10**9 g = [[INF]*m for _ in range(n)] g[start[0]][start[1]] = 0 pq = [(heuristic(start, goal), start)] dirs = [(0,1),(0,-1),(1,0),(-1,0)] while pq: f, (x, y) = heapq.heappop(pq) if (x, y) == goal: return g[x][y] for dx, dy in dirs: nx, ny = x + dx, y + dy if not (0 <= nx < n and 0 <= ny < m): continue if grid[nx][ny] == '#': continue ng = g[x][y] + 1 if ng < g[nx][ny]: g[nx][ny] = ng f = ng + heuristic((nx, ny), goal) heapq.heappush(pq, (f, (nx, ny))) return -1grid = [".....", ".#.#.", ".#.#.", ".#...", "....."]print(astar(grid, (0,0), (4,4)))
💬 댓글