There's some ambiguity around the endpoints of these paths. It looks like you've defined them as being in the centers of the street intersections at the initial and final endpoints (which is pretty extreme jaywalking). I had thought of each endpoint as being at one of the 4 corners of an intersection, which affects the path length, as well as the optimal path choices. In this case, the specific start and finish corners would need to be specified in order for the problem to be well-defined. In either case, you can think of these distances as the result of running a string along the segments of the path, then pulling it taught (assuming each block has buildings at its corners to stop the string). Tom Gareth McCaughan writes:
On 18/10/2020 21:39, Marc LeBrun wrote:
=Keith F. Lynch Envision the roads having, not zero width, but infinitesimal width.
It sounds fascinating, but I'm really having trouble picturing this. Are the grid points at the intersections of these narrow-most roads? Are the jays walking "diagonally" along them or across them or what? You imply the shortest path from 0,0 to 2,2 goes thru 1,1. But why? Given some arbitrary path from A to B, how do we compute its length? Can you help by providing some worked examples or the like? Thanks!
A shortest path from (0,0) to (2,2) goes (0,0) (1-h,h) (1+h,1-h) (2-h,1+h) (2,2) where h is half the width of the roads. The total distance is some unpleasant thing involving square roots of quadratics in h, but e.g. with h=0.001 it's about 3.994 whereas the path that goes (0,0) - (2-h,h) - (2,2) has length about 3.998.
Taking a route that stays nearer to a straight line lets you cut the corners slightly more effectively.
I'm not sure it's actually correct to say that this rewards staying closer to the straight line, though, because I think really all it's doing is rewarding _alternation_ between going north and going east, and in general there will be lots of equally-good paths, some of which will stay much closer than others to the straight-line path.
-- g