Next: Power of f Previous: Example

A*

Note that branch-and-bound (UCS) and best-first search both improve the search

Branch and bound makes sure that the solution path is low cost, and
Best-First helps to find a solution quickly

A* combines these approaches, using the evaluation function

f(n) = g(n) + h(n)

g(n) cost so far to reach n from initial state
h(n) estimated cost to nearest goal state from n
f(n) = estimated total cost of path through n to goal

The search is guided by the function f

queue-fn is sort-by-f