A* (pronounced like "a-star") is a best-first search algorithm that uses the evaluation function
where
is the path cost from the initial state to node
(referring to the path we took to get to
which would be the estimated shortest path from the initial state to
), and
(heuristic function) is the estimated cost of the shortest path from
to a goal state, so we have
represents the past knowledge acquired while searching.