Heuristic Search: A*
The A* algorithm uses both actual distance (as in Dijkstra's algorithm) and a heuristic estimate of the remaining distance. It is both very efficient and able to overcome local maxima.
A* chooses the next node based on lowest estimated total cost of a path through the node.
Estimated Total Cost f(n) = g(n) + h(n)
g(n) = Cost from Start to n [known]
h(n) = Cost from n to Goal [estimated]
g(n) h(n)? Start -------> n -------> Goal
The heuristic function, h , estimates the cost of getting from a given node n to the goal. If h is good, the search will be highly directed and efficient; for example, airline distance is an excellent heuristic distance estimator for route finding. If h is not so good or has pathologies, inclusion of the known cost g keeps the search from getting stuck or going too far astray.