5.7 More Informed Heuristics

• h₁ and h₂ are both admissible. Is one better than the other ?

• Better means that fewer nodes will be expanded in searches

• h₂(n) dominates (or is more informed than) h₁(n) if h₂(n) >= h₁(n) for every node n

• Intuitively, if both are underestimates then h₂(n) is a more accurate estimate then h₁(n)

• Using f = g + h₁ expands every state expanded by f = g + h₂ and a few more as well.

• Using a more informed heuristic is guaranteed to expand fewer nodes of the search space (ie. be more computationally efficient)

• Show that Manhattan distance (also known as City Block) dominates tiles out of place.