A*

This article introduces the A* search algorithm.

A* search algorithm (the A* search algorithm; A* is pronounced A-star), or simply the A* algorithm, is an algorithm for finding the shortest path between a given start point and endpoint in a weighted directed graph. It belongs to graph traversal and best-first search algorithms, and is also an improvement over BFS.

Process

The goal of the A* algorithm is to find the shortest path from start point $s$ to endpoint $t$ in a directed graph. Let $d(x,y)$ be the distance between vertices $x$ and $y$, that is, the length of their shortest path. Let $g(x)=d(s,x)$ be the distance function from start point $s$ to vertex $x$, and let $h^*(x)$ be the distance function from vertex $x$ to endpoint $t$. Let $h(x)$ be an estimate of $h^*(x)$¹. Finally, let the estimated shortest-path length from $s$ to $t$ through $x$ be

During the search, the A* algorithm takes a vertex with minimum $f$ from the priority queue each time. It then pushes all of its successor vertices $x$ into the priority queue and updates $f(x)$ using the actually recorded $g(x)$ and estimated $h(x)$.

Properties

Because the actual value of $h^*(x)$ is unknown during the search, an easily computed $h(x)$ must be used as its estimate. The actual complexity of A* search depends on the properties of this estimate function $h(x)$. It is easy to imagine that if $h\equiv h^*$, meaning the estimate is exact, the search will proceed strictly along the shortest path. If $h\equiv 0$, the A* algorithm degenerates into Dijkstra's algorithm; when $h\equiv 0$ and all edge weights are $1$, it is BFS.

Assume the graph has no negative-weight edges. If the estimate $h(x)$ never exceeds the actual distance $h^*(x)$, that is, $0\le h\le h^*$, the A* algorithm is guaranteed to find an optimal solution. An estimate function $h(x)$ satisfying this condition is called admissible. As discussed above, the closer $h$ is to $h^*$, the more efficient the corresponding A* algorithm is. Generally, in the worst case, the algorithm visits all vertices satisfying

where $C^*$ is the shortest distance between start point $s$ and endpoint $t$. Intuitively, the closer $h$ is to $h^*$, the fewer successor vertices satisfy this condition at each expansion, so the fewer branches the algorithm searches. Thus, the A* algorithm can be regarded as a “pruning” optimization for search algorithms.

If $h$ is not only admissible but also consistent, that is,

then the A* algorithm will not add a vertex that has already been popped from the queue back into the queue. The consistency condition can be understood as the triangle inequality among vertices $x,y,t$.

Examples

A classic application of the A* algorithm is solving the k-th shortest path problem. For a description of the problem, the A* approach, and a persistent leftist-heap approach with better complexity, see the k-th shortest path problem page.

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

#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 standard matrix
  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 whether it matches the standard 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 square (vertex 0)
    for (int i = 0; i < 4; i++) {  // Search in each of the four movement directions
      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});  // Put the new state into the search queue
        swap(x.a.a[fx][fy], x.a.a[xx][yy]);  // The case without this move
      }
    }
  }
  return 0;
}

References and notes

• A* search algorithm - Wikipedia