A* 알고리즘

개요

A* 알고리즘은 주어진 출발 꼭짓점에서부터 목표 꼭짓점까지 가는 최단 경로를 찾아내는 알고리즘 중 하나이다. 이 알고리즘은 다익스트라 알고리즘과 유사하나 차이점은 각 꼭짓점 [math]x[/math]에 대해 그 꼭짓점을 통과하는 최상의 경로를 추정하는 순위값인 "휴리스틱 추정값 " [math]h(x)[/math] 을 매기는 방법을 이용한다는 것이다. 이 알고리즘은 이 휴리스틱 추정값의 순서로 꼭짓점을 방문한다. 그러므로 A* 알고리즘을 너비 우선 탐색의 한 예로 분류할 수 있다.

특징

1. A* 는 Complete (답이 있으면 찾는다)
2. 하지만, Optimal (최적의 경로를 찾는다.)한 결과는 보장하지 않는다.
3. 그러나 적절한 휴리스틱을 가지고 이 알고리즘을 사용하면 최적(optimal)이 된다. 또한 최적이 아니더라도 납득할 만한 결과를 빠른 시간에 제공한다.

그렇다면 Admissible한(최적의 값을 가져올 수 있는) 휴리스틱 함수는 어떻게 구하느냐의 문제가 남는다. 이는 각각의 노드 n에서 진짜 gloal state로 가는 cost function보다 항상 작은 값을 가지고 있음이 보장된다면 그 h(n)은 Admissible하다고 볼 수 있다.

알고리즘

기본적으로 A* 알고리즘은 너비우선 알고리즘이다. 현재 노드에서 갈수 있는 노드들을 순차적으로 탐색하는 BFS알고리즘은 당연히 필요없는 부분도 길을 찾으며 매우 효율이 떨어진다는 문제가 있다. 이러한 문제를 해결하기 위해서 다음 노드를 선택하는 과정에서 휴리스틱하게 넘어가는 함수를 이용하여 너비 우선 탐색을 효율적으로 만드는 것이 바로 A* 알고리즘이다. 그러나 BFS와는 다르게 A*는 휴리스틱 함수를 사용하여 무조건 최적의 방법을 제공하지는 않지만, 적당히 괜찮은 답을 빠르게 제공한다는 장점이 있다.

A* 알고리즘은 출발 꼭짓점으로부터 목표 꼭짓점까지의 최적 경로를 탐색하기 위한 것이다. 이를 위해서는 각각의 꼭짓점에 대한 평가 함수를 정의해야 한다. 이를 위한 평가 함수 [math]f(n)[/math]은 다음과 같다. 여기서 g(n)은 시작점에서 n까지 가는 실제 비용이며, h(n)은 n에서 end로 가는 예측값이다. 이때 h(n)은 진짜값보다 항상 작도록 설정되기 때문에 f(n)은 항상 진짜보다는 작은 값을 가지게 된다.

[math]f(n) = g(n) + h(n)[/math]

• [math]g(n)[/math] : 출발 꼭짓점으로부터 꼭짓점 [math]n[/math]까지의 경로 가중치
• [math]h(n)[/math] : 꼭짓점 [math]n[/math]으로부터 목표 꼭짓점까지의 추정 경로 가중치

이러한 가중치를 바탕으로 제일 작은 가중치를 따라가다보면 목적지로 향하는 방향성을 가지고 경로를 찾게 된다.

Heuristic Function

아래의 함수는 Simple Grid World에서 Over Estimation을 하지 않는다. 따라서 납득할 만한 결과를 준다고 믿을 수 있다.

1. 유클리디안 거리: 루트(가로^2 + 세로^2)
2. 맨헤탄 거리: 가로 + 세로

의사코드

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       // 시작 노드에서 목표 노드까지의 거리를 출력한다.

참고

https://qiao.github.io/PathFinding.js/visual/

https://www.redblobgames.com/pathfinding/a-star/introduction.html