The A* algorithm is a heuristic search most often used for finding shortest-path routes. If the heuristic guarantees a lower bound on the costs of any node below, then this can be used to prune whole branches where the heuristic exceeds the current best solution. That is it can be seen as heuristic version of branch and bound. Often the raw heuristic is about the path beyond the node, for example the Euclidean distance (as the crow flies) to the target location in geographic shortest path search, in which case the distance along the path to the node has to be added to the raw heuristic to create a total path lower bound. The heuristic can also be used to guide the next node to explore in a variant of hill climbing.
Used in Chap. 4: pages 49, 50, 55; Chap. 15: page 224
Also known as A* algorithm
Using the A* algorithm to find shortest distance between Applethwaite and Gilby The straight-line disance between Cardale to Gilby is 50 miles, so any routes found must be longer than this. Therefore the Applethwaite–Barton –Gilby route is shorter than any route via Cardale, hence Cardale can be pruned.