6.034 Artificial Intelligence - Recitations, fall 2004 online slides on search

Next: Heuristics Previous: Informedness

Effect on Search Cost

If \(h_2(n) \geq h_1(n)\) for all $n$ (both are admissible)
then $h_2$ dominates $h_1$ and is better for search

Typical search costs 


d = 14, IDS = 3,473,941 nodes 


A*($h_1$) = 539 nodes 


A*($h_2$) = 113 nodes 





d = 24, 		IDS $\approx$ 54,000,000,000 nodes 


A*($h_1$) = 39,135 nodes 


A*($h_2$) = 1,641 nodes