Heuristic function ($h(s)$)

A function estimating the remaining cost from a state $s$ to a goal in a search problem. The estimate is an admissible heuristic when it never exceeds the true minimum remaining cost. A consistent heuristic satisfies an additional local inequality along each permitted transition.

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^{\ast }(g)=0$ at goals and $h^{\ast }(s)\le c(s,s^{\prime })+h^{\ast }(s^{\prime })$ 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.

A comparison oracle revealing the ordering of remaining optimal costs without returning their magnitudes. It supplies enough information for greedy best-first search. Its ordering alone does not provide the numerical differences needed to compare sums with independently varying accumulated costs. For $g(n)=5$, $g(m)=1$, remaining costs $(1,2)$ and $(1,10)$ have the same pairwise order but give opposite orderings of $g+h^{\ast }$.

A heuristic function $h_2$ dominates $h_1$ if $h_2(s)\ge h_1(s)$ everywhere. When both are admissible heuristics, the larger estimate is at least as informative for A-star search: for a fixed accumulated path cost $g$ and optimal solution cost $C^{\ast }$, $g+h_2<C^{\ast }$ implies $g+h_1<C^{\ast }$. This compares the compulsory search region, not arbitrary tie handling at $C^{\ast }$, evaluation overhead or wall-clock time.