Skip to content

A*

This article introduces the A* search algorithm.

The A search algorithm (pronounced A-star), abbreviated as A algorithm, is an algorithm for finding the shortest path between a given start and end node in a weighted directed graph. It belongs to graph traversal and best-first search algorithms, and is an improvement over BFS.

Process

The goal of the A* algorithm is to find the shortest path from the start node \(s\) to the end node \(t\) in a directed graph. Let \(d(x,y)\) be the distance between nodes \(x\) and \(y\), i.e., the length of the shortest path between them. Denote \(g(x)=d(s,x)\) as the distance function from the start node \(s\) to node \(x\), \(h^*(x)\) as the distance function from node \(x\) to the end node \(t\), and \(h(x)\) as an estimate of \(h^*(x)\)1. Finally, denote the estimated shortest path length from \(s\) to \(t\) via \(x\) as

\[ f(x) = g(x) + h(x). \]

During the search, the A* algorithm each time extracts a node with the smallest \(f\) from the priority queue. Then, it pushes all its successor nodes \(x\) into the priority queue and updates \(f(x)\) using the actual recorded \(g(x)\) and the estimated \(h(x)\).

Properties

Since the actual value of \(h^*(x)\) is unknown during the search, an easily computable \(h(x)\) must be used as its estimate. The actual complexity of the A search depends on the properties of this estimation function \(h(x)\). It is easy to imagine that if \(h\equiv h^*\), i.e., the estimate is exact, then the search process will strictly follow the shortest path. If \(h\equiv 0\), then the A algorithm degenerates to Dijkstra's algorithm; when \(h\equiv 0\) and edge weights are \(1\), this becomes BFS.

Assume the graph has no negative-weight edges. If the estimate \(h(x)\) never exceeds the actual distance \(h^*(x)\), i.e., \(0\le h\le h^*\), then the A algorithm is guaranteed to find the optimal solution. An estimation function \(h(x)\) satisfying this condition is called admissible. According to the previous discussion, the closer \(h\) is to \(h^*\), the more efficient the corresponding A algorithm is. Generally, in the worst case, the algorithm will traverse all nodes satisfying

\[ f(x) = g(x) + h(x) \le C^* \]

where \(C^*\) is the shortest distance between the start node \(s\) and the end node \(t\). Intuitively, the closer \(h\) is to \(h^*\), the fewer successor nodes satisfy this condition each time an expansion is performed, and thus the fewer branches the algorithm searches. Therefore, the A* algorithm can be seen as a "pruning" optimization of the search algorithm.

If \(h\) is not only admissible but also consistent, i.e.,

\[ h(x) \le h(y) + d(x, y), \]

then the A* algorithm will not re-add nodes that have already been popped from the queue to the queue. The consistency condition can be understood as the triangle inequality among nodes \(x\), \(y\), and \(t\).

Example Problems

A classic application of the A algorithm is solving the k-th shortest path problem. For the description of this problem, the A approach, and the more complexity-efficient persistent mergeable heap approach, please refer to the k-th shortest path problem page.

This section introduces a classic problem that can be solved using the A* algorithm.

Eight Puzzle

On a \(3\times 3\) board, there are eight tiles, each marked with a number from \(1\) to \(8\). There is one empty space on the board, represented by \(0\). Tiles adjacent to the empty space can be moved into it, making the original position become the empty space. Given an initial layout and a target layout (to simplify the problem, the target state is set as follows), find a method to move from the initial layout to the target layout with the minimum number of steps.

\[ \begin{aligned} 123\\ 804\\ 765 \end{aligned} \]
Solution Idea

The \(h\) function can be defined as the number of tiles not in their correct positions. It is easy to see that \(h\) is both admissible and consistent. This problem can be solved using the A* algorithm.

Reference Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#include <set>
using namespace std;
constexpr int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
int fx, fy;
char ch;

struct matrix {
  int a[5][5];

  bool operator<(matrix x) const {
    for (int i = 1; i <= 3; i++)
      for (int j = 1; j <= 3; j++)
        if (a[i][j] != x.a[i][j]) return a[i][j] < x.a[i][j];
    return false;
  }
} f, st;

int h(matrix a) {
  int ret = 0;
  for (int i = 1; i <= 3; i++)
    for (int j = 1; j <= 3; j++)
      if (a.a[i][j] != st.a[i][j] && a.a[i][j] != 0) ret++;
  return ret;
}

struct node {
  matrix a;
  int t;

  bool operator<(node x) const { return t + h(a) > x.t + h(x.a); }
} x;

priority_queue<node> q;  // Search queue
set<matrix> s;           // Prevent duplicate states in the search queue

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  st.a[1][1] = 1;  // Define the target state
  st.a[1][2] = 2;
  st.a[1][3] = 3;
  st.a[2][1] = 8;
  st.a[2][2] = 0;
  st.a[2][3] = 4;
  st.a[3][1] = 7;
  st.a[3][2] = 6;
  st.a[3][3] = 5;
  for (int i = 1; i <= 3; i++)  // Input
    for (int j = 1; j <= 3; j++) {
      cin >> ch;
      f.a[i][j] = ch - '0';
    }
  s.insert(f);
  q.push({f, 0});
  while (!q.empty()) {
    x = q.top();
    q.pop();
    if (!h(x.a)) {  // Check if it matches the target matrix
      cout << x.t << '\n';
      return 0;
    }
    for (int i = 1; i <= 3; i++)
      for (int j = 1; j <= 3; j++)
        if (!x.a.a[i][j]) fx = i, fy = j;  // Find the position of the empty cell (0)
    for (int i = 0; i < 4; i++) {  // Search for each of the four possible moves
      int xx = fx + dx[i], yy = fy + dy[i];
      if (1 <= xx && xx <= 3 && 1 <= yy && yy <= 3) {
        swap(x.a.a[fx][fy], x.a.a[xx][yy]);
        if (!s.count(x.a))
          s.insert(x.a),
              q.push({x.a, x.t + 1});  // After moving, push the new state into the search queue
        swap(x.a.a[fx][fy], x.a.a[xx][yy]);  // Restore to the state before moving
      }
    }
  }
  return 0;
}

References and Notes

  1. Here \(h\) stands for heuristic. See Heuristic search - Wikipedia and the Bounded relaxation section of A* search algorithm - Wikipedia. ↩

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用