= Solution
<A-star search> is <best-first search> with priority
$$
\boxed{f(u)=g(u)+h(s(u)),\qquad 0\le h(s)\le h^*(s),\qquad h(\text{goal})=0.}
$$
Here $u$ is a <search node>, $s(u)$ is its state, $g(u)$ is its accumulated <path cost>, and $h^*(s)$ is the minimum remaining cost to any <goal state>, interpreted as $\infty$ if no goal is reachable. The inequality defines an <admissible heuristic>. Thus $f(u)$ is a lower bound on the cost of any solution extending that particular action history.
Initialize the <search frontier> with the root. Repeatedly remove a <search node> of least $f$, apply the <goal test>, and, if it is not a goal, insert its applicable-action children with their updated $g$ and $f$. In <tree search>, different action histories remain distinct <search nodes> even when they reach the same state; there is no global visited-state <set>.
For the finite <branching factor> and unit costs here, an <admissible heuristic> ensures that any first goal removed is optimal. If a cheaper solution existed, the <search frontier> would contain an unexpanded prefix of it with $f$ at most that cheaper cost, contradicting selection of the more expensive goal. Nonnegative $h$ also means only finitely many <search nodes> can have $f$ below any fixed finite cost, so a finite solution will eventually be reached. This does not guarantee termination when no proof exists.
Back to article page
