# A* Search

Problem: Given a network of nodes such that the links between nodes have costs associated with them, find the least expensive path from a starting node to a goal node.  (For example, nodes could be cities and links distances.)  A* search is an optimal algorithm in that it is guaranteed to find a shortest path if one exists.  In addition, A* will be optimally efficient. That is, no other optimal algorithm is guaranteed to expand fewer nodes than A* search.

In A* search, node n is expanded with a priority equal to f(n), such that in each cycle of the algorithm, the node with the lowest f(n) value is first expanded, then removed from the queue.  The function f(n) is

f(n) = g(n) + h(n)

where g(n) is the distance from the start node to the node n, and h(n) is a heuristic estimate of the distance from node n to a goal node. If h(n) is always an underestimate of the actual distance from node n to the nearest goal node, then the function h is said to be an admissible heuristic function, and A*’s guarantee of optimal efficiency will hold.

In a nutshell, the algorithm for A* search is a best first search that uses the sum of the distance from the start node and a lower bound on the distance to the goal node to sort its queue of open nodes.  The queue of open nodes being “nodes under consideration for further expansion,” which initially contains only the start node.