A* 알고리즘(A Star Algorithm)

1. 개념
2. 시각화
3. 코드

---

1. 개념

최단경로를 찾는 그래프 탐색 알고리즘 중 하나입니다. 다익스트라 알고리즘과 유사하나 차이점은 각 꼭지점 x에 대해 그 꼭지점을 통과하는 최상의 경로를 추정하는 순위값인 "휴리스틱 추정값" h(x)를 매기는 방법을 이용한다는 점에서 차이가 있습니다. (h(x) 값을 정확하게 구할 수 없어도 괜찮습니다)

 

시작노드와 목적지 노드를 분명하게 정해 놓고, 이 두 노드간의 최단 경로를 파악합니다. 휴리스틱 추정값을 어떤 방식으로 제공하느냐에 따라 최단경로 파악 성능이 결정됩니다.

 

A* 알고리즘은 출발 꼭지점으로 부터 목표 꼭지점까지의 최적 경로를 탐색하기 위한 것입니다. 이를 위해서는 각각의 꼭지점에 대한 평가 함수 f(n)를 정의해야 합니다.

$ f(x) = g(x) + h(x) $ 

- $g(x)$: 출발 꼭지점으로부터 꼭지점 x까지의 경로 가중치

- $h(x)$: 꼭지점 x으로 부터 목표 꼭지점까지의 추정 경로 가중치

 

출처: A* 알고리즘 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

A* 알고리즘 - 위키백과, 우리 모두의 백과사전

 

※ 네비게이션을 예로 들면, 현재 지점 GPS 값과 도착 지점 GPS 값을 알고 있으니 A* 알고리즘을 사용하는 것이 유리하고, 그래프 가중치는 인접 노드의 교통 상황과,  h(x) 값은 중간지점과 도착지점의 GPS L2 거리 값을 이용할 수 있습니다.

---

2. 시각화

출처: 최단 경로 탐색 – A* 알고리즘 – GIS Developer

---

3. 코드

유사 코드를 보면, BFS 알고리즘과 매우 유사한 구조입니다. 다만, 큐 대신에 우선순위 큐를 사용하여 F Score(G Score + H Score)가 작은 노드가 다음번 조사 순서가 됩니다.

pq.enqueue(start_node, g(start_node) + h(start_node)) // 우선순위 큐에 시작 노드를 삽입한다.

while pq is not empty       // 우선순위 큐가 비어있지 않은 동안
    node = pq.dequeue       // 우선순위 큐에서 pop한다.

    if node == goal_node    // 만약 해당 노드가 목표 노드이면 반복문을 빠져나온다.
        break
        
    for next_node in (next_node_begin...next_node_end)
    	// 해당 노드에서 이동할 수 있는 다음 노드들을 보는 동안
        pq.enqueue(next_node, g(node) + cost + h(next_node)) // 우선순위 큐에 다음 노드를 삽입한다.

return goal_node_dist       // 시작 노드에서 목표 노드까지의 거리를 출력한다.

 

// 이 소스 코드의 그래프는 인접 리스트 방식으로 그래프를 표현하였다.
using ii = pair<int, int>;

priority_queue<ii, greater<ii>, vector<ii> > pq;

/// N_VER은 그래프의 정점의 개수를 의미한다.
int dist[N_VER], cost[N_VER][N_VER]; /// dist[i]는 i번째 정점까지 가는 최단 거리를 의미한다. G(i) 값.
vector<ii> edges[N_VER]; /// edges[i]는 i와 연결된 정점과 가중치를 묶어 저장하는 벡터이다.

int minDist(int src, int dst) {
	pq.push({0, src});
    bool success = false;
	while(!pq.empty()) {
		int v = pq.top(); pq.pop();
        if(v == dst) {
            success = true;
            break;       	
        }
        for (ii adj: edges[v]) 
        {      
            if(dist[adj.first] < g(v) + adj.second + h(adj.first))
            {
            	dist[adj.first] = g(v) + adj.second + h(adj.first);
                pq.push({dist[adj], adj});
            }
        }
    }
    if (!success) return -1;
    else return dist[dst];
}