A* search algorithm

• 1. Introduction

  ›

  A* (pronounced "A-star") is a pathfinding algorithm that can find the shortest route between two points on any weighted graph - from a road map to a railway network to a fantasy video game world. It was first published in 1968 by Peter Hart, Nils Nilsson, and Bertram Raphael of Stanford Research Institute. Half a century later, it remains the best solution across a wide range of pathfinding problems.

  What makes A* remarkable is that it is simultaneously complete, optimal, and optimally efficient. It will always find the shortest path if one exists, and it will do so while expanding fewer nodes than any comparable algorithm. How does a search algorithm achieve all three properties at once? The answer lies in a surprisingly elegant idea called a heuristic, and in the distinct contributions each of those three researchers made to what became the A* paper.

• 2. Born From a Robot

  ›

  Shakey was a mobile robot developed at Stanford Research Institute with the goal of planning its own actions autonomously. Nils Nilsson originally proposed using an algorithm called the Graph Traverser to handle Shakey's path planning. Graph Traverser used a heuristic - an estimated distance from a given node to the goal - but it ignored one crucial piece of information: how far the robot had already traveled to get there.

  Bertram Raphael recognized the gap. He suggested combining both costs: the distance already traveled from the start, and the estimated distance still remaining. Peter Hart then contributed two foundational theoretical ideas - admissibility and consistency of heuristic functions - that would determine when the combined approach actually guarantees an optimal result.

  The resulting algorithm was more than just a practical tool for Shakey. It was later shown that A* can find optimal paths for any problem satisfying the conditions of a cost algebra, well beyond the least-cost path problems it was originally designed to solve.

• 3. The Heuristic Advantage

  ›

  At each step, A* selects the path that minimizes a score combining two values: g(n), the known cost of the path from the start to the current node, and h(n), a heuristic estimate of the remaining cost to the goal. That heuristic function is entirely problem-specific. When searching for the shortest route on a map, for example, h might represent the straight-line distance to the goal, since that is physically the smallest possible distance between any two points.

  For a grid map in a video game, the right heuristic depends on what moves are available. A grid with four-way movement calls for the Taxicab distance, while eight-way movement makes Chebyshev distance a better choice. The point in each case is the same: the heuristic guides the search toward the goal without wasting time on obviously unpromising paths.

  This is what separates A* from a greedy best-first search, which uses only the heuristic estimate and ignores the cost already paid. A keeps both terms in play, which is why it does not fall into traps that greedy approaches can stumble into. Dijkstra's algorithm sits at the other extreme: it uses no heuristic at all, effectively setting h to zero for every node, making it a special case of A.

• 4. Admissibility and Consistency

  ›

  A heuristic is called admissible if it never overestimates the true cost to the goal. When A* uses an admissible heuristic, it is guaranteed to return an optimal solution. The intuitive reason is that an admissible heuristic is always optimistic: when the algorithm closes the goal node, its f-score can be no greater than the true distance, yet it also equals the actual length of the path found.

  Consistency, sometimes called monotonicity, is a stricter condition. A heuristic is consistent if, for every edge in the graph, the estimated cost at a node is no greater than the edge length plus the estimated cost at the neighbor. With a consistent heuristic, A* processes every node at most once and is equivalent to running Dijkstra's algorithm on a graph with reduced edge weights.

  The difference matters enormously for performance. When the heuristic is admissible but not consistent, a single node can be expanded many times - in the worst case, an exponential number of times. Dijkstra's algorithm could then outperform A* by a large margin on those inputs. Research has since found that this pathological case only arises in contrived situations where edge weights grow exponentially with graph size, which rarely occurs in practice.

• 5. Optimal Efficiency Proven

  ›

  The original 1968 A paper included a theorem claiming that no A-like algorithm could expand fewer nodes than A*, given a consistent heuristic and the right tie-breaking rule. A correction was published a few years afterward claiming that consistency was unnecessary for this result.

  That correction was shown to be false in 1985. Rina Dechter and Judea Pearl published a definitive study of A*'s optimal efficiency that year. They produced a concrete counterexample: an A variant using an admissible but inconsistent heuristic that expanded arbitrarily more nodes than an alternative A-like algorithm on the same problem.

  Dechter and Pearl's positive result is equally sharp. They proved that A with a consistent heuristic is optimally efficient with respect to all admissible A-like search algorithms on all non-pathological search problems. Optimality here refers strictly to the set of nodes expanded, not the total number of expansion iterations: a node that gets expanded repeatedly counts as one node in the set, but the work of re-expanding it still costs time.

• 6. Speed vs. Optimality

  ›

  The admissibility criterion guarantees the shortest path, but it also forces A* to examine every path that might be equally meritorious. When a good-enough path is acceptable, relaxing admissibility can dramatically speed up the search.

  The most common form is Weighted A*, which multiplies the heuristic by a constant factor. The resulting path may cost up to a factor of (1 + epsilon) more than optimal, but far fewer nodes are expanded to find it. This guarantee is called epsilon-admissibility, and several variants have been developed around it.

  Dynamic Weighting adjusts the weighting factor based on the depth of the search and the anticipated solution length. The Convex Upward/Downward Parabola variants, known as XUP and XDP, push the tradeoff toward near-optimal paths close to the goal or close to the start respectively, depending on which variant is used. AlphA* takes a different approach by promoting depth-first exploitation, preferring recently expanded nodes by building the search depth into the cost function itself.

• 7. Memory and Practical Limits

  ›

  A* keeps every generated node in memory, which means its space complexity grows at the same rate as its time complexity in the worst case. In practice, this turns out to be the most significant drawback of the algorithm, because memory runs out long before time does on large graphs.

  That limitation drove the development of memory-bounded variants. Iterative deepening A, or IDA, repeatedly restarts the search with a deepening cost threshold, keeping no nodes in memory between passes. Memory-bounded A* and SMA* take a different approach, retaining as many nodes as memory allows and discarding the least promising ones when space runs short.

  For real-world travel-routing systems at large scale, A* is generally outperformed by algorithms that can pre-process the graph offline to attain better runtime performance. Even so, A* remains the best solution across a wide range of cases where pre-processing is not an option or where graph structure changes too frequently to exploit it. The Washington, D.C. to Los Angeles railway routing problem is one illustrative example where A* applies the great-circle distance as its heuristic.