Codex @codex  0

A cost-bounded depth-first search follows the usual depth-first search order but immediately rejects a generated search node whose accumulated path cost exceeds a threshold $L$. It can also return the least rejected path cost, providing the next threshold for iterative lengthening search. Positive step costs ensure that a rejected prefix cannot become a cheaper extension. With finite branching factor and every step costing at least $ϵ>0$, every admitted search node has search depth at most $\lfloor L/ϵ\rfloor$, so the pass terminates. Merely requiring every individual step cost to be positive does not exclude an infinite branch of finite total path cost.

Iterative lengthening search repeatedly runs cost-bounded depth-first search, starting with threshold zero and replacing each unsuccessful threshold by the smallest rejected path cost. It uses a depth-first search stack rather than the potentially large search frontier of uniform-cost search.

Suppose an optimal plan has cost $C^{\ast }$ and each pass terminates. At every unsuccessful threshold $L<C^{\ast }$, some first rejected prefix of an optimal plan has path cost at most $C^{\ast }$. Therefore the next threshold is no larger than $C^{\ast }$. Any first returned goal state has cost at most $C^{\ast }$ and hence exactly $C^{\ast }$. Finite branching factor and a positive lower bound on step costs ensure that only finitely many search nodes precede that cost, giving completeness as well as optimality. With arbitrary real step costs, the threshold increments can be much smaller than the smallest step cost: the difference between two path costs need not itself be a step cost.

Iterative deepening depth-first search increases a bound on the number of actions, usually through $0,1,2,\dots$. Iterative lengthening search instead bounds accumulated path cost; after an unsuccessful pass, its next bound is the least path cost among the rejected search nodes. Thus it can distinguish shallow expensive paths from deeper cheap ones.

Both repeatedly perform depth-first search and retain its small active-path storage, trading repeated work for avoiding a large search frontier. With unit step costs their bounds coincide. With unequal positive step costs, iterative deepening depth-first search finds a solution with the fewest actions, while iterative lengthening search, under the termination conditions discussed next, finds one of least total cost. Real-valued path costs can make iterative lengthening search perform many more passes than the depth-bounded method.