= A-star search
{c}
{title2=$f(s)=g(s)+h(s)$}
= A\* search
{c}
{synonym}
<Best-first search> prioritizing the estimated total solution cost $f=g+h$, with $g$ the cost already incurred and $h$ a <heuristic function> for the remaining cost. With nonnegative estimates, goal estimates zero, finite <branching factor> and step costs bounded below by a positive constant, the <tree search> version using an <admissible heuristic> returns a minimum-cost goal when it removes one for expansion. An optimal solution path always has a frontier node with $f\le C^*$; a more costly goal cannot be removed before it. The stated finiteness and lower-cost assumptions ensure finitely many earlier nodes when a finite solution exists. Repeated-state handling in <graph search> needs reopening when a better path is found, unless a <consistent heuristic> justifies finalizing expanded states.
Back to article page
