5.5 A* Search

• Intuition: Try to expand a node that is on the least code path to the goal.
  f(n) = g(n) + h(n)
  g(n) is the (estimated) cost to node n

  f(n) is the estimated cost of the cheapest solution through n

  If h(n) is an underestimate of the true cost to goal then:

  • A* is complete
  • A* is optimal
  • A* is Optimally Efficient, no other algorithm using h(n) is guaranteed to expand fewer states