[Algorithms] A* Algorithm | A* 알고리즘

A* Algorithm [A-Star Algorithm]

A* 알고리즘

- 그래프의 시작 정점에서 도착 정점에 이르는 최단 경로를 계산하는 알고리즘이자,
  상태 공간 트리의 탐색에도 사용되는 알고리즘이다.
- A* 알고리즘에서는
  Best-First Search(최적 우선 탐색) 방법과, 도착 정점까지 경로의 추정치를 사용하여 다음 정점을 선택한다.
  (장래의 탐색 정보를 활용하기 때문에, Dijkstra's 알고리즘과 같은 단순한 탐색 알고리즘에 비해 훨씬 효율적이다.)
- Dijkstra's 알고리즘에서는 모든 정점에 대해 최단 거리를 구하는 반면,
  A* 알고리즘에서는 특정 도착 정점에 대한 최단 거리를 비교적 빠르게 구할 수 있다.

* Best-First Search (최적 우선 탐색)
- 각 정점에는 각자의 매력 함수 값이 부여되어 있고,
  시작 정점에서부터 방문하지 않은 정점들 중 매력 함수 값이 가장 이상적인 정점부터 방문하는 탐색 알고리즘이다.
  (즉, 방문할 정점을 Greedy하게 선택한다.)
- 프림 알고리즘에서 매력 함숫값은 현재 상태에서 방문하지 않은 정점을 연결하는데 드는 최소 비용이다.
- 다익스트라 알고리즘에서 매력 함숫값은 현재까지 계산된, 시작 정점에서 방문하지 않은 정점까지의 최소 거리이다.

---

Mechanism (원리)

- A* 알고리즘에서는 진행할 다음 정점을 선택할 때, \(f(x) = g(x) + h(x)\) 값이 가장 작은 정점을 선택한다.



\(g(x)\) Function

- 시작 정점에서 정점 \(x\)까지 이르는 최단 거리이다.
- 즉, g(x)는 Greedy 알고리즘에서의 매력 함수이다. (의사코드상에서 \(\texttt{d[x]}\)에 해당)
- Greedy 알고리즘 범주에 속하는 Prim's 알고리즘, Dijkstra's 알고리즘과 같이,
  A* 알고리즘은 진행할 정점을 Greedy하게 선택해나가지만, 두 함수값을 복합적으로 사용하는 것이 특징이다.
- 즉, Dijkstra's 알고리즘은 항상 \(h(x) = 0\)인 경우의 A* 알고리즘이라 말할 수도 있다.



\(h(x)\) Function (Heuristic Estimate; 휴리스틱 추정값)

- 정점 \(x\)에서 도착 정점까지 경로의 추정된 잔여 길이이다.
- 이 추정 길이 \(h(x)\)는 정점 \(x\)에서 도착 정점까지의 실제 최단 거리보다 같거나 작다.
  (즉, (\(h(x)) \leq\) (\(x\)에서 도착 정점까지의 최단거리))
- \(h(x)\)값은 한 번 계산된 이후로, 알고리즘이 종료할 때 까지 변하지 않는다.
  (즉, \(f(x)\)값의 수정은 오로지 \(g(x)\)값의 변화로 인해 일어난다.)



Monotonicity (단조성)

\(h(x) \leq w(x, y) + h(y)\)

- \(h(x)\)가 \(x\)에서 도착 정점까지의 최단거리보다 같거나 작으며,
  그래프상의 모든 정점들의 Pair \((x, y)\)에 대해, \(h(x) \leq w(x, y) + h(y)\) 를 만족하면
  A* 알고리즘은 항상 Optimum(최적해)를 도출한다.
- 이러한 성질을 "단조성"이라 한다.



Example

- 각 정점들에서 도착 정점까지의 추정 거리 \(h(x)\)는 직선거리로 설정했다 가정하자.
  (아무리 경로를 잘 설정해도 실제 경로가 직선거리보다 짧을 수는 없으므로,
  A* 알고리즘의 규칙에 위배되지 않는 휴리스틱값이다.)
- 각 정점들 밖에 소괄호로 표기된 값은 \(f(x) = g(x) + h(x)\)이다.
  A* 알고리즘은 이 \(f(x)\)값이 가장 작은 정점부터 집합 \(S\)(청록색 영역)에 포함시킨다.
- 정점 \(x\)와 정점 \(y\) 사이의 직선 거리를 \(d(x, y)\)라 할 때,
  Euclidean Space에서는 \((x, y)\)에 대해 Triangle Inequality (삼각 부등식, URL) \(h(x) \leq d(x, y) + h(y)\) 를 만족한다.
  \(d(x, y) \leq w(x, y)\) 이므로, \(h(x) \leq w(x, y) + h(y)\) 이며,
  이를 통해 A* 알고리즘의 Monotonicity(단조성)를 만족함을 확인할 수 있다.

---

Implementation (구현)

* GitHub (URL)

* Pseudo Code

a_star(G, s, t)
// G = (V, E) : Given Graph
// s : Starting Vertex
// t : Destination Vertex
// Q : Priority Queue
{
    Q = V;
    for(u ∈ Q) {
        g[u] = ∞;
        f[u] = ∞;
        h[u] = Estimate distance from Vertex 'u' to 't';
    }
    
    g[s] = 0;
    f[s] = h[s];
    
    while(Q != empty_set()) {
        u = deleteMin(Q, f);
        if(u == t)
            return ;
        else {
            for(v ∈ L(u))
                if(v ∈ Q && g[u] + w(u, v) < g[v]) {
                    g[v] = g[u] + w(u, v);
                    prev[v] = u;
                    f[v] = g[v] + h[v];
                }
        }
    }
}

deleteMin(Q, f[])
{
    집합 Q에서 f값이 가장 작은 정점 u를 리턴한다
}

Examples of A* Algorithms (A* 알고리즘을 사용한 예시)

* Traveling Sales Person Problem (TSP) (방문 판매원 문제) (URL)

[Algorithms] Traveling Sales Person Problem (TSP) | 방문 판매원 문제

 

---

Performance (성능)

---

Reference: Introduction to Algorithms 3E (CLRS)
(Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein 저, MIT Press, 2018)

Reference: 쉽게 배우는 알고리즘
(문병로 저, 한빛아카데미, 2018)