= Solution
The <branching factor> of the <search tree> is at most five, so through depth $d$ it has at most
$$
1+5+\cdots+5^d=\frac{5^{d+1}-1}{4}=O(5^d)
$$
nodes in <Big O notation>. With no depth bound, \b[the <search tree> can be infinite], despite the finite <state space>: <tree search> retains different action histories even when they end at the same position pair.
For a concrete repeating history, use a two-row, three-column board, indexed from zero, with the sole obstacle $(0,1)$, rabbit at $(0,2)$ and fox at $(0,0)$. Repeated rabbit stays leave the fox blocked horizontally with no vertical separation to reduce. Hence the same live state can repeat forever. An exit at $(1,2)$ is nevertheless safely reachable in one round.
Back to article page
