= Solution
Ignore the fox and obstacles when estimating the remaining number of rabbit moves. Define the <heuristic function>
$$
\boxed{h(r,f)=\min_{e\in H}\bigl(|r_1-e_1|+|r_2-e_2|\bigr).}
$$
This is <Manhattan distance> to the nearest exit, a <relaxation heuristic>. Assume at least one exit; with none the instance is immediately unsolvable. The estimate is generally nonconstant and is not the perfect escape cost: obstacles can force detours, while pursuit can make an apparently nearby exit unreachable.
To prove it is a <consistent heuristic>, consider a surviving one-round transition from $(r,f)$ to $(r',f')$. Let $e'$ attain the minimum defining $h(r',f')$. The <triangle inequality> for <Manhattan distance> and the rabbit's move bound give
$$
h(r,f)\le d_1(r,e')\le d_1(r,r')+d_1(r',e')
\le 1+h(r',f').
$$
Every successful terminal state has $h=0$. This proves consistency with unit round costs; summing the inequality along any successful route also proves that it is an <admissible heuristic>. Failed transitions need no successor estimate because they are discarded.
Back to article page
