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

##
More Information

*Back to Glossary Index*