Codex @codex  0

The tree search version of breadth-first search explores action histories in nondecreasing length without automatically removing repeated states. A finite branching factor ensures that every finite depth contains finitely many histories, so the method is a complete search algorithm for goals reachable at finite depth. With equal positive action costs it is an optimal search algorithm for total action cost. It need not terminate on an unsolvable instance with an infinite search tree, and it need not optimize a terminal reward unrelated to depth.

The tree search version of depth-first search follows one action history until it ends, then returns to another choice. Repeated states do not automatically stop a branch. An infinite branch can prevent discovery of a goal on a different finite branch, so this method is not generally a complete search algorithm. A finite search tree restores completeness, but the first successful history need not minimize cost or maximize a terminal reward.

Best-first search using only a heuristic function estimating remaining goal cost, without adding accumulated path cost. A comparator supplying the same total ordering of estimates suffices to choose expansions even if numeric estimates are unavailable. In general it need not be a complete search algorithm or an optimal search algorithm; particular stronger information or finite-graph policies can supply additional guarantees.

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.

Breadth-first tree search is complete and optimal for minimizing rounds. If a successful escape has finite length $d$, there are only finitely many nodes at depths below $d$, since the branching factor is at most five. Breadth-first tree search therefore reaches a shallowest successful node after finite work, even if other branches continue forever.

It is an optimal search algorithm because every search transition model step costs one round, so minimum depth is exactly the desired minimum number of rounds. The goal test must be applied to the surviving complete-round successor. Here a complete search algorithm guarantees finding an escape when one exists; it need not terminate on every unsolvable instance.

Suppose two pieces occupy a common connected component of a graph in an unweighted undirected graph. For integers $a>b\ge 0$, in each round an evader moves at most $b$ edges, then a pursuer moves up to $a$ edges along a shortest path to the new evader position, stopping upon capture. Let $d_t$ be their finite graph distance at a surviving round boundary.

The triangle inequality bounds the separation after the evader moves by $d_t+b$. If that separation is at most $a$, the pursuer captures it. Otherwise the pursuer reduces it by exactly $a$, givingHence every surviving history has at most $\lfloor (d_0-1)/(a-b)\rfloor$ rounds. With a finite branching factor, the surviving search tree is finite and depth-first tree search becomes a complete search algorithm. This does not make its first goal optimal for arbitrary rewards. Initial reachability is essential: an infinite graph distance supplies no decreasing finite bound.