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 ...