- h1 and h2 are both admissible. Is one better
than the other ?
- Better means that fewer nodes will be expanded in searches
- h2(n) dominates (or is more informed than)
h1(n) if h2(n) >= h1(n) for every node
- Intuitively, if both are underestimates then h2(n)
is a more accurate estimate then h1(n)
- Using f = g + h1 expands every state expanded by
f = g + h2 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.