A*search

Idea: avoid expanding paths that are already expensive Evaluation function f (n) = g(n) + h(n) g(n) = cost so far to reach n h(n) = estimated cost to goal from n f (n) = estimated total cost of path through n to goal