A*

From Republic Square to the Green Bazaar it is 3.79 km by the streets and 2.90 in a straight line. Dijkstra does not know this and grows its wave equally in all directions: by the time it reaches the bazaar it has covered half the centre, including the blocks behind the start. A* knows where the finish is and adds a hint to the distance travelled: how much is left at least in a straight line. Below, the two searches go step by step over the real streets of Almaty: Dijkstra on the left, A* on the right. Click either map to move the finish, and switch the hints.

Both found the same path, but Dijkstra looked at 1422 crossroads and A* at 209, 6.8 times fewer. The waves have different shapes, too: Dijkstra's is a blot around the start, A*'s a spindle stretched towards the finish. The dashed line around each wave is a border it cannot cross whatever the streets are like: a circle for Dijkstra and an ellipse for A*. Why an ellipse will become clear in a section, and the same reasoning will tell how many times A* should win.

The idea

Dijkstra takes from the heap the vertex with the smallest g(v), the length of the path found from the start. A* takes the vertex with the smallest f(v) = g(v) + h(v), where h(v) is an estimate of how far is left from v to the finish. Vertices leading away from the finish get a large h and wait; vertices on the way to the finish come forward. If the estimate never overestimates, then when the finish is taken from the heap, the path to it is shortest.

The estimate is called a heuristic. For a map it suggests itself: a road is never shorter than a straight line, so the straight-line distance to the finish is an honest lower estimate. Exactly this example, cities, roads between them and the distance “as the crow flies”, was given by the authors of A* in their 1968 paper. With h = 0 it is plain Dijkstra, so A* is not a different algorithm but Dijkstra with a hint: the code differs by one term in the heap key.

The hint changes only the order in which vertices are taken from the heap. Everything else, the relaxation of edges, the heap, skipping stale entries, stopping when the finish is taken, stays the same. Look at the caption under the first scene: at every step A* reports g, h and f of the vertex it took. The key f grows slowly and evenly, although g and h jump about separately.

Why the wave is an ellipse

Let the shortest path from A to B have length D. Dijkstra takes vertices in increasing order of g and stops when it has taken B, so all its vertices are at most D from the start by road. By road is never closer than in a straight line, so they all lie inside the circle of radius D centred at A.

Now the gain can be computed in advance. The ellipse has semi-axes D/2 and ½√(D² − |AB|²), the circle has radius D. The ratio of the areas is 4/√(1 − 1/r²), where r = D/|AB| is how many times the road path is longer than the straight line. For Republic Square and the bazaar r = 3786/2904 ≈ 1.30: the circle is 45.0 km², the ellipse 7.22 km², a ratio of 6.2. The waves hold 1422 and 209 crossroads, a ratio of 6.8. The estimate used only areas, without running a single search, and nearly got it right.

The formula shows when A* wins more. The straighter the road between start and finish, the closer r is to one and the narrower the ellipse: along a straight highway it stretches into a needle. If the road winds twice as long as the straight line, the ellipse is almost round and the gain drops to 4.6 times. There is a worse conclusion too: the areas of both the circle and the ellipse grow as D². The straight-line hint wins a constant factor but does not change the order of growth. The measurement will show it.

Why the path is shortest

The hint does not have to be the straight-line distance; it has to be honest. And “honest” needs to be made precise, in two ways.

A hint is called admissible if it never overestimates the distance to the finish: h(v) ≤ d(v, B). And consistent if h(B) = 0 and for every edge u → v of length w the triangle inequality h(u) ≤ w + h(v) holds. Consistency is stronger: add the inequalities along the shortest path from v to B and you get admissibility. The straight-line distance is consistent if every road is no shorter than the segment between its ends: that is the school inequality |uB| ≤ |uv| + |vB|.

The same trick, adding to an edge's length the difference of the “potentials” of its ends, works the other way round too: Johnson's algorithm picks potentials so that negative edges become non-negative.

If the hint is admissible but not consistent, w′ can be negative, and a vertex may be taken before the shortest path to it has been found. For this case the 1968 paper “reopened” a vertex, putting it back into the heap if the path to it improved. The code of this article, like Dijkstra's code, does not reopen vertices and relies on consistency. Telling one property from the other on real data is the first problem at the end of the article.

Step by step: a game level

In games A* usually searches over cells. Below is the level from this article's listing: walls, a swamp where a step costs 5, and grass where a step costs 1. The hint is the Manhattan distance to B, the number of horizontal and vertical steps if the field were empty. It is consistent: a step changes it by exactly one and costs at least one. The numbers in the cells are f; under the field is the content of the heap in increasing order of f.

A* takes 77 cells, Dijkstra on the same field 159, and the path costs 31 for both. Step through the search from the beginning. First A* heads straight for B and runs into the wall of a “bowl” open towards the start. While the f of cells inside the bowl is smaller than that of cells on the detour, it fills the bowl completely, and only then goes round. This is the main weakness of a hint that knows nothing about walls: a concave obstacle on the way to the goal. The deeper the bowl, the more wasted work. Choose “Maze”: there the walls take almost all of A*'s gain away, 123 cells against Dijkstra's 136.

Turn on “Manhattan × 3”: the hint overestimates, A* rushes to the goal barely looking around, and on “Swamp” lays its path right through the bog. It costs 41 instead of 31. More on this in the section on good and bad hints.

Code

The same level in a program. The heap holds pairs (f, cell), the dictionary g the best known cost of a path, the set settled the cells already taken. The program prints the field: commas where the search has been, asterisks the path found.

This code differs from Dijkstra's in one line, the one that puts things into the heap. A cell found along a stale path is handled the same way: the entry stays in the heap and is skipped when it surfaces.

And this is the city. The program reads the street graph of Almaty, finds a path from Republic Square to the Green Bazaar with seven hints, and then runs six of them on 40 random routes. The eight landmarks are crossroads chosen one at a time: each next one is the farthest by road from those already chosen. What kind of hint that is, the next section explains.

  hint                  settled  route, m
  zero (Dijkstra)          1422      3786
  straight line             209      3786
  straight line x1.5         50      3796
  straight line x2           38      3794
  manhattan                 123      3792
  8 landmarks                93      3786
  exact distance             40      3786

The last line is a hint that knows the exact distance to the finish: for it the program ran Dijkstra from the bazaar in advance. With it A* takes 40 crossroads, exactly those the path goes through and not one more. That is the limit of what a hint can give, and everything between 1422 and 40 is a question of how well the hint knows the city.

Good and bad hints

One route is not enough to compare hints. Below are the same 40 random routes as in the listing, and for each hint two figures: how many crossroads it takes from the heap on average, and how much longer than the shortest its worst route turned out. A good hint is at the bottom left: little work, not one extra metre.

Straight line: 1080 crossroads on average against Dijkstra's 4038, 3.7 times fewer, and not one wrong route. This is the floor below which you cannot go without knowing the city.

Manhattan. The centre of Almaty is laid out almost along the cardinal directions, and the sum of horizontal and vertical steps seems more natural than a straight line. The hint is indeed stronger, 443 crossroads, but it is no smaller than the straight line, and on diagonal streets it exceeds the real distance. With the Green Bazaar as the finish it overestimates at 4515 crossroads out of 7909. The result: 38 routes out of 40 are longer than the shortest, the worst by 10.9 %. Speed is bought with wrong answers, and you cannot know in advance where.

Weighted straight line. Sometimes wrongness can be bought deliberately, with a guarantee. Ira Pohl studied in 1970 what happens if the hint is given more weight: f = g + w · h with w > 1. The search pulls towards the goal more greedily and takes fewer vertices, and the error is bounded.

On the 40 routes the weight 1.5 gives 156 crossroads instead of 1080 and a worst error of 10.3 % against a guarantee of 50 %; the weight 2 gives 110 crossroads and 21.1 % against a guarantee of 100 %. Almost all routes are a little longer than the shortest, but you know how much worse they cannot be. This is what you do when the answer is needed fast and a few extra percent do not matter: in games, in robots, in planners.

Landmarks. The straight-line hint knows geometry but not roads. Knowledge of the roads can be prepared in advance. Choose a few landmark crossroads L and once compute with Dijkstra the distances from each of them to all crossroads. By the triangle inequality d(L, B) ≤ d(L, v) + d(v, B) and d(L, v) ≤ d(L, B) + d(B, v), so d(v, B) ≥ |d(L, B) − d(L, v)|. This is a lower estimate, and it is consistent: along an edge of length c the distance from a landmark changes by at most c. The maximum of such estimates over all landmarks is a consistent hint as well. It works especially well when a landmark stands “behind” the finish: then the estimate is almost exact. In 2005 Andrew Goldberg and Chris Harrelson named this trick ALT: A*, landmarks and the triangle inequality. Eight landmarks along the edges of Almaty give 342 crossroads on average, a third of the straight line's, and all routes are shortest. The price is eight arrays of distances for the whole city and eight runs of Dijkstra in advance.

Switch the scene and the chart to “Seconds”, where the minutes on the way add up at nominal street speeds. The straight-line hint here divides the distance by the speed of the fastest road, 80 km/h, otherwise it could overestimate. But almost all streets are slower, and the hint becomes weak: 2372 crossroads out of 4030, a gain of only 1.7 times. The landmarks are computed in seconds and know where it is slow: 372 crossroads, 10.8 times fewer than Dijkstra. A navigator needs exactly time, and that is why in navigators the geometric hint loses to hints built from the graph itself.

What it costs

In the worst case A* is no better than Dijkstra: the hint may hint at nothing (h = 0), and then it is just Dijkstra, O((V + E) log V) time. With a consistent hint every vertex is taken at most once, so it does not get worse than Dijkstra either, apart from the time to compute the hint itself. Memory is O(V): distances and a heap for all vertices the wave has reached.

In practice the hint decides everything, and the gain is a constant factor: the ellipse is so many times smaller than the circle, but both grow as the square of the distance. A measurement on the same streets: the start in the city centre, finishes from 1 to 8 km away by road, six for each distance.

Dijkstra grows with a slope of about 2: a finish twice as far means four times the work, like the area of a circle. A* has a smaller slope and more scatter: the shape of the ellipse depends on how much a particular route winds. In time A* most often wins 3–6 times, and on the shortest route, a kilometre, it even loses in Go: the gain is smaller than in the number of vertices, because for every neighbour A* also computes a hint with a square root, and on short routes there are so few vertices that there is almost nothing to win.

Memory becomes the main trouble where vertices number not thousands but trillions, in puzzles and planning. A* stores everything it has reached, and on the 4 × 4 fifteen puzzle that is hundreds of thousands of positions even for medium instances. Richard Korf proposed IDA* in 1985: a depth-first search that cuts off branches where g + h exceeds a threshold, and raises the threshold until it finds a solution. It needs memory for one branch and finds the same as A*. Both ideas will come in handy in the second problem.

Where it is used

Games. Characters find paths not over cells but over a navigation mesh, a map of walkable polygons. The Unity manual describes it this way: start and finish are attached to the nearest polygons, the search goes from polygon to neighbours until the finish, and it searches with A*. The chain of polygons found is a corridor, and the character walks along it, each time turning towards the next visible corner.

Route planners. The straight-line hint is weak for a road network in minutes, as the scene shows. GraphHopper has a hybrid mode, A* with landmarks, the very ALT; its sample configuration uses 16 landmarks. It is slower than contraction hierarchies but lets road weights change from query to query. The fastest navigators combine precomputation and search: the wave is still Dijkstra or A*, but on a graph reworked in advance. Another way to narrow the wave is to send two towards each other: bidirectional search.

Puzzles and planning. The fifteen puzzle, the Rubik's cube, a robot's action plans are graphs nobody stores whole: neighbours are computed on the fly, as in the state space of breadth-first search. Here A* and IDA* with good hints are the main tool for finding optimal solutions.

A robot that needed a road

In 1966–1972 the SRI research institute built Shakey, the first mobile robot that reasoned about its own actions and planned them itself. It had to find paths around obstacles, and in 1968 Peter Hart, Nils Nilsson and Bertram Raphael published the paper “A Formal Basis for the Heuristic Determination of Minimum Cost Paths”. In retellings of the story, Nilsson first proposed searching by the hint alone, the estimate of the distance to the goal; Raphael proposed adding it to the path already travelled; and Hart came up with the notions now called admissibility and consistency and proved that with them the algorithm finds the shortest path and does no extra work.

In the paper itself the word “admissible” refers not to the hint but to the algorithm: an algorithm is called admissible if it is guaranteed to find an optimal path, and A* is proved admissible when the hint is a lower estimate. Consistency is called there the “consistency assumption” and written as a triangle inequality. Where the star in the name comes from was never properly recorded. In 2020 Jim Davis and Jeff Hachtel of Ohio State asked the authors, and Raphael answered that the name was “quick, easy, and rather arbitrary”: Nilsson's earlier version was called algorithm A.

Problems

In the first problem you check someone else's hint, whether it is consistent, admissible or overestimating, and among the tests are the streets of Almaty, where even a straight line rounded down lies by a metre once. In the second A* finds the shortest solution of the fifteen puzzle among the ten trillion positions that can be solved.