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.

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.

With the conventional strictly positive step costs, the five answers in printed order are false, false, true, true, true. The third answer needs that positivity convention: it is false in general if zero-cost edges and unrestricted ties are admitted. Take the goal test on selection from the search frontier, and assume a finite reachable problem with a reachable goal state; finite branching factor and a positive lower bound on step costs give the corresponding tree search guarantees on an infinite problem. These assumptions make the usual A-star search guarantees precise.^[ref]

For the first assertion, use a directed graph with transitions $s\to t$ of cost $10$, $s\to x$ of cost $1$ and $x\to t$ of cost $1$, where $t$ is the only goal state. The perfect heuristic is $h^{\ast }(s)=2$, $h^{\ast }(x)=1$, $h^{\ast }(t)=0$. Greedy best-first search selects the direct goal of cost $10$ because its priority is zero. The least path cost is $2$. Knowing the exact remaining distance does not account for an expensive transition already taken.

The same counterexample settles the second assertion. Greedy best-first search selects $s,t$, while A-star search selects $s,x,t$: after expanding $s$, the A-star search priorities are $2$ for $x$ and $10$ for the direct copy of $t$. Thus even the expanded state sets differ.

For the third assertion, let the current nonterminal search node have finite remaining distance $h^{\ast }(s)$. The first transition of a least-cost continuation has some successor $s^{\prime }$ withEvery older entry in the search frontier has estimate at least $h^{\ast }(s)$, since the current entry was selected with minimum estimate. A newly generated successor with strictly smaller estimate therefore wins over every older entry. Whichever new successor is selected has smaller remaining distance than the current search node, so the argument repeats. Consequently the selected search nodes form one parent–child chain; include the selected goal, or append it if “expanded” excludes goal processing. This greedy perfect-heuristic descent does not imply least path cost, as the first counterexample demonstrates.

The zero-cost qualification is substantive. Give $s$ two successors $a,b$ of cost $1$, add $a\to x$ of cost $0$, and add $x\to t$ and $b\to t$ of cost $1$. The perfect heuristic has values $2$ at $s$, $1$ at $a,b,x$ and $0$ at $t$. Alphabetical priority ties let greedy best-first search select $s,a,b,t$, which is not one graph path. Thus the unqualified third assertion requires a cost or tie convention absent from the printed text.

For the fourth assertion, a least remaining distance satisfieson every edge, by taking that edge and then a least-cost continuation. Thus $h^{\ast }$ is a consistent heuristic. The usual A-star search graph search finalizes each expanded state's least path cost and returns a least-cost goal.

For the fifth assertion, write $C^{\ast }=h^{\ast }(s_0)$. Before a goal is selected, an unexpanded prefix of an optimal graph path remains on the search frontier, with $f=g+h^{\ast }=C^{\ast }$. A-star search therefore selects only search nodes with $f\le C^{\ast }$. Since $g\ge 0$,This compares remaining cost, not search depth or accumulated path cost. The statement can fail with negative costs; those are outside the convention used here.

Let the input words be $s,t$, let $L$ be their common length, let $\Sigma$ be the finite alphabet, and let $D_L$ contain the dictionary words of length $L$. Unequal input lengths immediately make the puzzle impossible because a mutation preserves length. A word ladder search problem can use the state space $S=D_L\cup \{s\}$, with initial state $s$; including $s$ handles an input word not itself in the dictionary.

At word $w$, an action is a position–letter pair $(i,\ell )$ with $1\le i\le L$, $\ell \in \Sigma$ and $\ell \ne w_i$, permitted precisely when replacing $w_i$ by $\ell$ gives $w^{\prime }\in D_L$. The search transition model returns that $w^{\prime }$, and the goal test is $w=t$. If $s=t$, the empty sequence is accepted; if $t\notin D_L$ and $s\ne t$, no transition can reach $t$.

Assign each permitted transition cost $1$. A search node at search depth $k$ hasThus minimizing path cost is exactly minimizing the number of mutations. Uniform-cost search, with repeated states handled by graph search and the goal test on selection, finds a shortest word ladder if one exists. Because all costs are equal, breadth-first search gives the same optimal-length guarantee.

Depth-first search computes minimax search values with much less live storage and naturally supports alpha-beta pruning. A parent's value needs only its current best child value and the next child to visit. Once a child subtree has been evaluated, its internal search nodes can be discarded; a final value cannot usually be computed from a nonterminal frontier alone.

With branching factor $b$ and horizon $d$, breadth-first search stores a frontier of order $b^d$. A depth-first search implementation storing sibling lists uses $O(bd)$ space complexity; lazy successor generation can reduce this to $O(d)$ frames plus game-state storage. Both unpruned traversals have $O(b^d)$ time complexity for $b>1$. Depth-first search also supplies a completed sibling outcome early, allowing alpha-beta pruning to reject later subtrees before generating them.

With excellent move ordering, the new horizon is approximately $2d$; without a move ordering assumption, no doubling is guaranteed. For $b>1$, a full minimax search to depth $d$ visits $\Theta (b^d)$ search nodes, so the budget $n$ has $d\approx {\log }_{b}n$. Perfectly ordered alpha-beta pruning evaluates only about $\Theta (b^{d^{\prime }/2})$ leaves at depth $d^{\prime }$. More precisely, for a complete uniform game tree, the best leaf count is $b^{\lceil d^{\prime }/2\rceil }+b^{\lfloor d^{\prime }/2\rfloor }-1$. Equating the dominant costs givesConstant factors and rounding affect the exact horizon. Poor move ordering can leave the cost at $\Theta (b^{d^{\prime }})$, giving no asymptotic depth improvement. For $b=1$, there is no branching to prune and the doubling argument does not apply.^[ref]

All three variants are complete search algorithms under the usual finite-branching factor, nonnegative-heuristic function assumptions. Here $0\le h\le h^{\ast }$, with zero at goals; the supplied positive lower bound on step costs is also essential. The root is processed once before a parent-dependent priority is needed.^[ref] Completeness means finding a solution if one exists, not necessarily terminating when none exists.

Fix a finite solution path. Every search node on that path has a finite priority, so let $K$ bound all of its relevant priorities. For ordinary A-star search and the second variant, the priority is at least $g(n)$. Thus any search node with priority at most $K$ has depth at most $\lfloor K/ϵ\rfloor$. In the third variant the priority is at least $g(n^{\prime })$, so its depth is at most $\lfloor K/ϵ\rfloor +1$. A finitely branching search tree has finitely many search nodes at these depths. Therefore finitely many earlier search nodes can delay each successive search node on the chosen solution path; eventually its goal is generated or selected, as appropriate.

Moving the goal test to generation cannot destroy that existence guarantee, although it can destroy optimality. Likewise the altered parent-dependent priorities remain bounded below by the accumulated cost to the search node or its parent, which is enough for this completeness argument. If “admissible” were interpreted to allow arbitrarily negative estimates, the lower-bound argument would need an additional hypothesis; the conventional nonnegative interpretation is being used explicitly. For the literal upper-bound-only interpretation, all three can fail completeness: attach an infinite unit-cost dead-end chain with $g(n_d)=d$ and $h(n_d)=-2d$ beside a finite goal branch beginning with a cost-$3$ edge and estimate zero. Its successive low priorities can starve the finite branch. Every negative chain estimate is still at most its infinite true remaining cost.

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, updateRun 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, ifThis 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^{\ast }(n)=\infty$ forces $u(n)=\infty$ too. Every finite quantity $g(n)+u(n)$ is consequently at least the global optimum $C^{\ast }$.

On an optimal solution path, admissible heuristic estimates ensure $f(n)\le C^{\ast }\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^{\ast }$, 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.

Yes. Greedy best-first search needs only the ordering of remaining-cost estimates. Store generated but unexpanded search nodes in a search frontier. To choose the next search node, compare candidates with $\kappa$ and retain the one it returns; a linear scan suffices, or a priority queue can use the comparison rule. Remove that search node, apply the goal test, and otherwise generate its children.

This implements best-first search ordered by $h^{\ast }$ without ever evaluating $h^{\ast }$. If stable tie handling is wanted, comparing both argument orders distinguishes equality, after which insertion order can break ties. No estimate of accumulated-plus-remaining cost is required for this greedy ordering.

The sum of step costs along the action history represented by a search node. Positive costs give lower bounds on search depth, and the same physical state can have different path costs when reached along different histories. Uniform-cost search orders by accumulated cost; A-star search adds an estimate of remaining cost.

The number of action edges between a search node and the root of its search tree. It is zero at the root. When every step costs more than $ϵ>0$, a positive-depth node satisfies $g(n)>d(n)ϵ$, connecting depth finiteness to path cost bounds.

The generated but unexpanded search nodes maintained by a search algorithm. Best-first search selects the next expansion from this frontier using a priority queue or an equivalent ordering operation. A lower-bound argument about a frontier node on an optimal path is central to A-star search correctness.

An entry in a search tree representing a particular action history. It normally stores the current state, its parent, its last action and accumulated path cost $g$. Distinct search nodes can represent the same state; identifying them changes tree search into a form of graph search and requires an appropriate repeated-state policy.