= Solution
\b[<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.
Back to article page
