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.