How to calculate heuristic value in a* algorithm?

A* and heuristic

A* always requires a heuristic, it is defined using heuristic values for distances. A* in principle is just the ordinary Dijkstra algorithm using heuristic guesses for the distances.

The heuristic function should run fast, in O(1) at query time. Otherwise you won't have much benefit from it. As heuristic you can select every function h for which:

• h is admissible: h(u) <= dist(u, t) (never overestimate)
• h is monotone: h(u) <= cost(u, v) + h(v) (triangle inequality)

There are however some heuristics that are frequently used in practice like:

• Straight-line distance (as-the-crow-flies)
• Landmark heuristic (pre-compute distances for all nodes to a set of selected nodes (landmarks))

Dependent on your application you might also find other heuristic functions useful.

Straight-line heuristic

The straight-line distance (or as-the-crow-flies) is straightforward and easy to compute. For two nodes v, u you know the exact location, i.e. Longitude and Latitude.

You then compute the straight-line distance by defining h as the Euclidean distance or if you want more precise results you don't ignore the fact that the earth is a sphere and use the Great-circle distance. Both methods run in O(1).

Landmark heuristic

Here you pre-select some important nodes in your graph. Ideally you always choose a node that is part of frequently used shortest-paths.

However that knowledge is often not available so you can just select nodes that are farthest to the other selected landmarks. You can do so by using greedy farthest selection (pick node which maximizes min_l dist(l, u) where l are already selected landmarks). Therefore you can do a Dijkstra from set which is very easy to implement. Just add multiple nodes at once into your Dijkstra starting queue (all current landmarks). Then you run the Dijkstra until all distances have been computed and pick the node with greatest shortest-path distance as next landmark. By that your landmarks are equally spread around the whole graph.

After selecting landmarks you pre-compute the distance from all landmarks to all other nodes and vice versa (from all nodes to all landmarks) and store them. Therefore just run a Dijkstra starting at a landmark until all distances have been computed.

The heuristic h for any node u, where v is the target node, then is defined as follows

h(u) = max_l(max(dist(u, l) - dist(v, l), dist(l, v) - dist(l, u)))

or for undirected graphs just

h(u) = max_l|dist(l, u) - dist(l, v)|

where max_l is a landmark which maximizes the argument.

After pre-computing said distances the method will obviously also run in O(1). However the pre-computation might take a minute or more but that should be no problem since you only need to compute it once and then never again at query time.

Note that you can also select the landmarks randomly which is faster but the results may vary in quality.

Comparison

Some time ago I created an image which compares some shortest-path computation algorithms I've implemented (PathWeaver at GitHub). Here's the image:

You see a query from top left to bottom right (inside the city). Marked are all nodes that where visited by the used algorithm. The less marks the faster the algorithm found the shortest-path.

The compared algorithms are

• Ordinary Dijkstra (baseline, visits all nodes with that distance)
• A* with straight-line heuristic (not a good estimate for road networks)
• A* with landmarks (randomly computed) (good)
• A* with landmarks (greedy farthest selected) (good)
• Arc-Flags (okay)

Note that Arc-Flags is a different algorithm. It wants to have an area, like a rectangle around a city. It then selects all boundary nodes (nodes which are inside the rectangle but minimize distance to outside nodes). With those boundary nodes it performs a reversed Dijkstra (reverse all edges and then run Dijkstra). By that you efficiently pre-compute the shortest paths from all nodes to the boundary. Edges which are part of such a shortest path are then marked (arcs are flagged). At query time you run an ordinary Dijkstra but only consider marked edges. Therefore you follow shortest paths to the boundary.

This technique can be combined with others like A* and you can select many different rectangles, like all commonly searched cities.

There's also another algorithm I know (but never implemented though), it is called Contraction Hierarchies and it exploits the fact that you usually start at a small town road, then switch to a bigger road, then a highway and in the end vice versa until you reached your destination. Therefore it gives each edge a level and then first tries to as quickly as possible reach a high level and try to keep it as long as possible.

It therefore pre-computes shortcuts which are temporary edges that represent a shortest-path, like super-highways.

Bottom line

The right choice for a heuristic and also for an algorithm in general heavily depends on your model.

As seen for road networks, especially near smaller towns, the straight-line heuristic doesn't perform well since there often is no road that goes straight-line. Also for long distances you tend to first drive onto the highway which sometimes means driving into the opposite direction for some minutes.

However for games, where you often can move around where you like straight-line performs significantly better. But as soon as you introduce roads where you can travel faster (like by using a car) or if you have many obstacles like big mountains, it might get bad again.

Landmark heuristic performs well on most networks as it uses the true distance. However you have some pre-computation and trade some space since you need to hold all that pre-computed data.

Heuristic values are wholly domain-dependent, especially admissible ones (which A* requires). So, for example, finding the shortest path on a geographic map might involve a heuristic of the straight-line distance between two nodes, which could be pretty-well approximated by computing the Euclidean distance between the (latitude, longitude) of the two points.