Greedy best-first search ($f(n)=h(n)$)

Best-first search using only a heuristic function estimating remaining goal cost, without adding accumulated path cost. A comparator supplying the same total ordering of estimates suffices to choose expansions even if numeric estimates are unavailable. In general it need not be a complete search algorithm or an optimal search algorithm; particular stronger information or finite-graph policies can supply additional guarantees.

In a finite reachable search problem with strictly positive step costs and a reachable goal, greedy best-first search using a perfect heuristic selects one parent–child chain until it reaches a goal state. At a selected nonterminal state $s$, an optimal first transition has $h^{\ast }(s^{\prime })=h^{\ast }(s)-c(s,s^{\prime })<h^{\ast }(s)$. Every older search frontier entry has estimate at least $h^{\ast }(s)$, so the next selected entry must be a newly generated child with smaller estimate. Repeating proves the chain property. In an infinite finitely branching problem, a positive uniform lower bound on costs also bounds the chain length by the initial remaining cost divided by that lower bound. Zero-cost ties can break the chain property; the lemma does not establish least accumulated path cost.