CMP.5:5.2 - Use a relaxed answer as a search bound

A robot moves on the finite grid with coordinates 0≤x≤2, 0≤y≤1. It can move one horizontal or vertical step at unit cost. The task is to go from (0,0) to (2,0); cell (1,0) is blocked.

Ignore blocked cells in the relaxed problem. The distance is abs(dx)+abs(dy), here 2. Every permitted original route is also a relaxed route with the same cost, so 2 is a lower bound. The straight relaxed route is unusable. An admissible detour through (0,1),(1,1),(2,1) costs 4, giving an initial comparison 2≤optimum≤4.

CMP.4 can use the relaxed remaining distance at each partial route, together with the distance already traveled. Alternatively, the blocked direct row implies that a valid route must include an upward and a downward move in addition to two horizontal moves, proving a lower bound of 4. That stronger argument closes this small case. The relaxed result was useful without being mistaken for an executable original route.

Changed operations: allow diagonal moves at unit cost. The earlier Manhattan distance can overestimate: reaching (1,1) from (0,0) can cost 1 rather than 2. Relax the new movement problem instead. With unrestricted unit-cost horizontal, vertical and diagonal moves, max(abs(dx),abs(dy)) is the distance and supplies the corresponding lower bound. The algorithmic thinking consists in rebuilding the comparison after the operations change.