CMPS140, Winter 2012, Section 01: Lecture 8

A* search framework:  f=g^ + h:
         g^ is how far to the node seen so far, h is how far estimted to the goal.
  We always expand node with lowest f-value! (If tie choose arbitrarily).
    Breadth First Search:  f = g^  (i.e.)     (h= 0).
    Depth First Search:    f =  g^ - 2g^.    (i.e. h=-2g^.

     Best First Search     f=h
     A* admissible/consistent f=g^+h   and h<=h*    (h* is the optimal solution)
         we will show that A* admissible is complete and finds optimal.

Manhattan distance for the tile puzzles sums the distance each tile is from
the goal and is <= h*. So is an admissible heuristic.