= Solution
Start the threshold at zero and let $C^*$ be the least solution cost. Suppose an unsuccessful pass has threshold $L<C^*$. Along an optimal action <sequence>, take the first prefix whose <path cost> exceeds $L$. Its preceding prefix is explored, so that rejected prefix contributes to the next-threshold calculation. Positive <step costs> imply that its cost is at most $C^*$. Therefore the next threshold is also at most $C^*$.
By <induction>, no threshold used before the first solution exceeds $C^*$. A returned <goal state> therefore has cost at most $C^*$; by the definition of $C^*$ it cannot cost less. \b[The first returned solution is optimal.]
The termination qualification matters. In a finitely branching problem with <step costs> at least $\epsilon>0$, a threshold $L$ admits only depths up to $\lfloor L/\epsilon\rfloor$, so each pass is finite and only finitely many <path costs> precede $C^*$. These conditions establish completeness as well. Strict positivity alone on an arbitrary infinite tree is insufficient: an infinite branch with costs $1/2,1/4,1/8,\ldots$ can remain below a finite threshold and trap <depth-first search>. The optimality argument above is valid whenever the required passes terminate; a finite graph with finitely many strictly positive action costs supplies a uniform positive lower bound.
Back to article page
