Home - Sun hat

Conditions of Use
###
Grid Speed

A puzzle in the March 2004 issue of
Scientific American
that piqued my fancy.
The problem is to visit all the intersections in the minimum time.
My first thought was to find a minimal path of 35 edges (roads between
intersections) to visit all 36 intersections while minimizing the slower
edges and maximizing the faster edges. That results in the solution you
see here in red lines. But I also had the thought that I might save time
by using faster edges to bypass some of the slower edges. Investigation
of the 6x6 puzzle proved that this could indeed be done as indicated by
the blue lines. To get there faster one does a U-turn onto the blue trail
instead of following the slowest red trail. At the end of the blue trail
one does another U-turn back onto the red trail. The trick is to know
how far to go back. It was these blue trails that piqued my interest to
see what happened if the grid were made larger.

Another thing that I noticed as I added up my times is that each
addition of a loop to the route added 1 + 2(n-1)/n "hours" to the
travel time, where n the road number (starting with 1, as in counting,
not addressing). That is what the plot at the bottom is all about. The
plot is color coded - the red plot is for the red route, and the blue
plot is for the red route as modified in blue. Notice how much time is
saved. On very large grids you get there in only little more than two
thirds the time.

The Java source.

It's Perl ancestor.
When I first placed this page on the web the programs were finding
the depth of the backtracking on the loops by trial in a loop. Since
then I found a way to calculate it.

For the nth loop of depth m-1, m being the speed of the crossover road,
the time required to backtrack is

t = (m-1)(1/(n - 1) + 1/n) + 1/m

Since we want to find the m which minimizes t we differentiate t with
respect to m, set dt/dm to 0 and solve for m to get:

m = sqrt(n*(n - 1)/(2*n - 1)))

since m is an integer and the above formula yields an exact answer we
need to truncate m, and calculate the times using both m and m + 1,
then take the smallest one.

This speeds up the calculation significantly, especially for large grids.

The new Java source.

The difference.

It's Perl ancestor modified.

The difference.

Home - Sun hat

Conditions of Use