= Shortest-path pursuit distance bound
{title2=$d_{t+1}\le d_t-a+b$}
Suppose two pieces occupy a common <connected component of a graph> in an unweighted <undirected graph>. For <integers> $a>b\ge0$, 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$, giving
$$
1\le d_{t+1}\le d_t-(a-b).
$$
Hence 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.
Back to article page
