Generating Heuristics

Some useful ways to think about good heuristics:

• If h₁ and h₂ are admissible heuristics, then $h(v) = \max(h_1(v), h_2(v))$ is admissible (and of no lesser quality).
• ``Relaxations'' often produce good heuristics: if cost is a function of some constraints on nodes, then constraint-free distance is admissible (Manhattan distance in 8 puzzle).