Routing

A routing engine calculates the optimum path between an origin and destination, subject to certain criteria. Common criteria include “use freeways,” “avoid freeways,” or “fewest turns.” The most common algorithm for calculating routes is based on the A* (pronounced A-star) algorithm developed in the artificial intelligence (AI) community.

The algorithm works by extending each known possible path to the destination by adding an intelligent guess (a heuristic estimate) and computing the total cost of the real traversed path plus the heuristic estimate.

Understanding routing requires understanding the basics of problem solving using AI techniques. The effectiveness of a combinatorial and problem-solving technology is significantly dependent ...

Get Mobile Location Services: The Definitive Guide now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.