= Solution
\b[Maintain a certified solution-cost ceiling and prune only <search nodes> whose lower bound strictly exceeds it.] Initially let $B=\infty$, or set $B=u(r)$ at the root $r$ when that value is finite. Whenever a <search node> $n$ is generated, update
$$
B\leftarrow\min\{B,\ g(n)+u(n)\}.
$$
Run ordinary <A-star search> with $f(n)=g(n)+h(n)$ and a <goal test> when removing a <search node> from the <search frontier>. Discard a generated <search node>, or a queued <search node> encountered after a later bound improvement, if
$$
\boxed{f(n)>B.}
$$
This is <branch and bound> using a lower bound $f$ and an upper bound $B$. A finite $u(n)$ certifies that some goal is reachable from $n$ within that remaining-cost ceiling; for a dead end, $h^*(n)=\infty$ forces $u(n)=\infty$ too. Every finite quantity $g(n)+u(n)$ is consequently at least the global optimum $C^*$.
On an optimal solution path, <admissible heuristic> estimates ensure $f(n)\le C^*\le B$. Hence no <search node> of that path is pruned. The finite-<branching factor> and positive step-cost hypotheses from (a) still ensure completeness, and the usual <A-star search> argument makes the first selected goal optimal. A smaller bound can remove branches earlier; it need not improve every instance.
The strict inequality matters: $u$ is only a numerical bound and need not provide an actual stored solution path. If $B=C^*$, pruning at $f(n)\ge B$ could remove every optimal continuation. Nor may the algorithm return a path merely because its lower bound meets $B$ when no witnessing path has been constructed. With an actual incumbent solution, the familiar equality-pruning variant can instead retain and return that incumbent.
Back to article page
