= Greedy perfect-heuristic descent
{title2=$h^*(s_{k+1})<h^*(s_k)$}
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^*(s')=h^*(s)-c(s,s')<h^*(s)$. Every older <search frontier> entry has estimate at least $h^*(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>.
Back to article page
