A* Search

A best-first graph search algorithm that orders node expansion by a cost function f(n)=g(n)+h(n), where g(n) is the cost from the start to node n and h(n) is a heuristic estimate of the cost from n to a goal; with an admissible (and preferably consistent) heuristic, A* finds least-cost paths efficiently.