Open Mobile Map

Heuristic

The heuristic function h(n) tells A* an estimate of the minimum cost from any vertex n to the goal. It’s important to choose a good heuristic function.

A*’s Use of the Heuristic

The heuristic can be used to control A*’s behavior.

• At one extreme, if h(n) is 0, then only g(n) plays a role, and A* turns into Dijkstra’s algorithm, which is guaranteed to find a shortest path.
• If h(n) is always lower than (or equal to) the cost of moving from n to the goal, then A* is guaranteed to find a shortest path. The lower h(n) is, the more node A* expands, making it slower.
• If h(n) is exactly equal to the cost of moving from n to the goal, then A* will only follow the best path and never expand anything else, making it very fast. Although you can’t make this happen in all cases, you can make it exact in some special cases. It’s nice to know that given perfect information, A* will behave perfectly.
• If h(n) is sometimes greater than the cost of moving from n to the goal, then A* is not guaranteed to find a shortest path, but it can run faster.
• At the other extreme, if h(n) is very high relative to g(n), then only h(n) plays a role, and A* turns into BFS.

So we have an interesting situation in that we can decide what we want to get out of A*. At exactly the right point, we’ll get shortest paths really quickly. If we’re too low, then we’ll continue to get shortest paths, but it’ll slow down. If we’re too high, then we give up shortest paths, but A* will run faster.

In a mobile map application, this property of A* can be very useful. For example, you may find that in some situations, you would rather have a “good” path than a “perfect” path. To shift the balance between g(n) and h(n), you can modify either one.

Note:
Technically, the A* algorithm should be called simply A if the heuristic is an underestimate of the actual cost. However, we will continue to call it A* because the implementation is the same and the programming community does not distinguish A from A*.

Speed or accuracy?

A*’s ability to vary its behavior based on the heuristic and cost functions can be very useful in a mobile map application. The tradeoff between speed and accuracy can be exploited to make your application faster. For most mobile map applications, you don’t really need the best path between two points. You just need something that’s close. What you need may depend on how density of the map and how fast the mobile phone is.

The choice between speed and accuracy does not have to be global. You can choose some things dynamically based on the importance of having accuracy in some region of the map. For example, it may be more important to choose a good path near the current location, on the assumption that we might end up recalculating the path or changing direction at some point, so why bother being accurate about the faraway part of the path?

Scale