= Perfect heuristic
{title2=$h^*(s)$}
The exact minimum remaining <path cost> from a state to a <goal state>, with value $\infty$ when no goal is reachable. For nonnegative step costs, $h^*(g)=0$ at goals and $h^*(s)\le c(s,s')+h^*(s')$ on every transition. Thus a <perfect heuristic> is a <consistent heuristic> and an <admissible heuristic>. It measures remaining cost; a <greedy best-first search> decision using only this number can still take an excessively costly incoming <edge>.
Back to article page
