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.

The first assertion is false. Give the root a first child that is a goal state of cost ten and another child leading to many cheaper non-goal search nodes. Depth-first search can take the first child and stop immediately. A-star search with the admissible heuristic $h=0$ behaves as uniform-cost search and expands the cheaper non-goal search nodes before selecting that goal. Thus an admissible heuristic does not make A-star search expand fewer nodes than every possible depth-first search ordering. The latter need not return an optimal solution.

The second assertion is true under the usual finite-branching factor assumption. Breadth-first search orders by search depth, not path cost. Every finite depth contains finitely many search nodes, so a goal at finite depth is eventually reached even if some steps cost zero. Zero-cost steps can affect cost optimality, but do not obstruct this completeness argument. An infinite branching factor would invalidate the argument irrespective of step costs.

The third assertion is true as a worst-case black-box requirement, with a finite optimum assumed. If outgoing actions are known only by expanding a state, an unexamined reachable branch can conceal a sufficiently negative-cost action followed by a route to a goal. Its total cost can beat the current solution by an arbitrarily large amount. Without additional lower bounds or structural information, finding one cheap solution cannot justify stopping; exhaustive examination can be necessary. This does not assert that every already-described irrelevant state must be visited on every input. Moreover, a reachable negative-cost cycle in a graph that can still reach a goal can make costs unbounded below, in which case no finite-cost optimal solution exists at all.

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.

Start the threshold at zero and let $C^{\ast }$ be the least solution cost. Suppose an unsuccessful pass has threshold $L<C^{\ast }$. 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^{\ast }$. Therefore the next threshold is also at most $C^{\ast }$.

By induction, no threshold used before the first solution exceeds $C^{\ast }$. A returned goal state therefore has cost at most $C^{\ast }$; by the definition of $C^{\ast }$ it cannot cost less. The first returned solution is optimal.

The termination qualification matters. In a finitely branching problem with step costs at least $ϵ>0$, a threshold $L$ admits only depths up to $\lfloor L/ϵ\rfloor$, so each pass is finite and only finitely many path costs precede $C^{\ast }$. 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,\dots$ 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.

With initial threshold zero and unit step costs, the thresholds are $0,1,\dots ,d$, so there are $d+1$ passes. Starting the first pass at one instead omits the zero-threshold pass when the root is not a goal.

At depth $i$, at most $b^i$ search nodes are admitted in each pass with threshold at least $i$. Across all passes, the full-to-cutoff visit bound isThis is attained when the only depth-$d$ goal is visited last. If a goal test occurs before expansion, the goal is visited but not expanded, giving the corresponding worst-case expansion countFor $b\ne 1$, the visit bound is $V(b,d)=[b^{d+2}-(d+2)b+d+1]/(b-1{)}^2$, hence the worst-case number expanded is $\Theta (b^d)$ for fixed $b>1$. For $b=1$, it is $\Theta (d^2)$. An earlier goal reduces the final pass, so its exact count cannot be inferred from $b,d$ alone. Children generated and immediately rejected above a threshold are not counted as expanded; counting those generated nodes adds the corresponding branching overhead.

A lower bound on individual step costs does not bound the difference between consecutive path cost thresholds. Two different paths can have costs differing by an arbitrarily small amount, even though every edge costs at least $ϵ$.

Let $C^{\ast }$ be the optimal solution cost. Every unsuccessful threshold is the path cost of some search node below $C^{\ast }$. Such a node has depth strictly less than $C^{\ast }/ϵ$. For a uniform branching factor $b>1$, the number of passes is therefore bounded byIf a solution of depth $d$ exists, each of its edges costs at most one, so $C^{\ast }\le d$ and an associated bound is $O(b^{\lceil d/ϵ\rceil })$ passes. If $d$ denotes the optimal solution's depth, the same inequality applies. With no solution-cost or solution-depth bound, $b$ and $ϵ$ alone give no finite uniform iteration bound.

The exponential behavior is possible. Put a depth-$d$ goal on a branch with unit costs and let a large competing subtree use costs just above $ϵ$. Choose tiny distinct perturbations so that its many search nodes below cost $d$ have distinct path costs. The threshold can advance through those costs one at a time. Thus a bound such as $\lceil d/ϵ\rceil$ on the number of passes is unjustified: it bounds admitted depth, not the number of distinct costs. For $b=1$ there is only one path, so the corresponding count is linear in the admitted depth rather than exponential.

A step cost is the cost of one action or transition in a search problem. The accumulated path cost is the sum of the step costs along its action history. A uniform positive lower bound on step costs makes every bounded-cost action history have bounded search depth; positivity of each individual term alone does not establish such a bound.