After 20 years of a relatively short and simple commute, I now have to drive 45 minutes each way to get to work. There are many ways to get there, since there are no direct routes.
For the first six months, I just stuck to the most heavily traveled route, because that is what I had always used in the past when going that way. Later on, I started experimenting with other ways to get back and forth, prompted in part by road construction that blocked my way.
After trying several different alternatives, I decided to get out the map and see if there were some roads I was missing. There were more ways than I could easily enumerate, leading me to (what else) write a program to discover the shortest route. I am sharing this because you might also find it useful.
First I got a map and identified all the roads that might be possible. I used Maptech's Terrain Navigator to measure each of these roads. Here is the map that resulted from this first step.
I used the software to measure the length of each segment, for instance from E to M, from E to B, from B to M, and so forth. The resulting distances are shown below.
Next I wrote a program to take this list of distances and find the shortest paths. There are 13 points, so at first I began to worry that it would require 13! possibilities to be considered. Then I remembered back to my algorithms course many years ago, and recalled that these kinds of graph algorithms almost all had quadratic solutions. So I thought about it overnight, and realized I only had to deal with the points that were connected. Since there are only 19 links, this is much more reasonable.
I wound up implementing a recursive function that enumerated all paths starting and ending at given points. At each step I gave it the set of links (minus the ones that had already been used). On reaching the end point, it records the path and the total cost. At the end the list of possible paths is sorted according to cost.
The resulting program is 80% data structure and 20% algorithm, and makes use of STL lists to store its nodes and links. When run on the data set given, it results in 132 paths from 11.77 to 26.93 miles. The program source, a compiled version for Windows, and the input and output files is included in the accompanying zip file.
Later on I realized this would have been easier in scheme. Just to keep in shape, I implemented it that way too. Much more natural. The result is an a different zip file. By the way, this uses DrScheme, available from Rice's PLT group.
One insight I have gained is how effective our visual system is as measuring and choosing the shortest path, almost beneath the level of our consciousness. I wonder if this is through learning, or is somehow inherent in the way we see. Although it feels "wrong" on the ground when going from E to M, and again from F to L to go south when I ultimately need to get north, on the paper it seems more obvious. And the program bears it out.
e b 2.19
b m 2.39
e m 4.32
b h 4.68
m v 0.74
v k 1.1
v g 1.06
g h 1.24
g j 0.83
k f 0.71
k j 1.06
f s 1.85
j s 1.35
h s 1.35
s c 0.6
f l 2.98
c l 1.64
l r 1.92
c r 3.26
(define (search from to links)
(letrec ((result '())
(first (lambda (ls) (car ls)))
(second (lambda (ls) (cadr ls)))
(third (lambda (ls) (caddr ls)))
(compare (lambda (x y) (< (first x) (first y))))
(accumulate-result (lambda (cost path)
(set! result (cons
(list cost (reverse (cons to path))) result))))
(search-step (lambda (from path cost links)
(iter from path cost links '())))
(iter (lambda (from path cost unprocessed processed)
(if (equal? from to)
(accumulate-result cost path)
(if (not (null? unprocessed))
(let* ((item (car unprocessed))
(links (append (cdr unprocessed) processed))
(new-cost (+ cost (third item))))
(cond ((equal? (first item) from)
(search-step (second item) (cons from path) new-cost links ))
((equal? (second item) from)
(search-step (first item) (cons from path) new-cost links )))
(iter from path cost(cdr unprocessed) (cons item processed))))))))
(search-step from '() 0.0 links)
(quicksort result compare)))
Return to Home Page