= Numerical upper-bound pruning without a solution witness
{title2=$B\leftarrow\min\{B,g(n)+u(n)\},\qquad \text{prune if }g(n)+h(n)>B$}
Suppose $0\le h(n)\le h^*(n)\le u(n)$ in a <search problem>, with $h^*=\infty$ at dead ends. Every finite $g(n)+u(n)$ bounds some reachable solution cost from above, so their running minimum $B$ is at least the global optimum $C^*$. Every node of an optimal path has $g+h\le C^*\le B$, and therefore survives the displayed strict pruning rule. Ordinary <A-star search> can continue to a selected goal without receiving a path witnessing $u$.
Equality pruning is unsafe without a stored incumbent solution: when $B=C^*$, it could delete every optimal continuation. A numerical upper bound does not by itself provide a <plan> to return. This distinguishes an upper-bound certificate from a constructed solution in <branch and bound>.
Back to article page
