5.3 Evaluation Functions

• The following modification of the basic search algorithm gives informed (Best First) searches:

• An evaluation function can be applied to any node (f(n))

• Nodes on OPEN are sorted by value of the evaluation function

• The node with the smallest evaluation value is expanded next.

• Different choices for f(n) give different kinds of searches

• Setting f(n) = h(n) gives "greedy search"

• h(n) is the estimated cost of the cheapest path from node n to the goal state (a heuristic function)

• For the 8-puzzle h₁(n) or h₂(n) could be used