I currently live in Chapel Hill, North Carolina. I grew up, however, in Cincinnati, Ohio and a couple of times a year I make the drive back there. The best route takes me through West Virginia on I-77 to Charleston, but after that it’s really up in the air as to what the best way to get to Cincinnati is. I’ve experimented with a number of routes, and after consulting my GPS unit, Google Maps, and AAA, I think I’ve come up with the best possible route. For those interested, it is OH-32 to US-35 to US-34 to I-64 to I-77 to I-74 to US-52 to US-421 to I-40 to NC-54.
Why was I able to find a better route than my GPS unit, into which probably went thousands of man-hours of labor? My guess is that the algorithm used by the GPS unit is not theoretically optimal. The reason for this is simple: the country is huge. There are about 6 million miles of paved highway in the US. Assume we have 10 intersections for every paved mile of road (a very conservation assumption): then we have 60 million intersections. A graph with 60 million vertices has at least 60 million edges, but probably closer to 120 million if it’s connected at all (60 million edges would just be a straight line, which is obviously wrong.) A very good shortest path algorithm running on a graph with E edges and V vertices takes runs in time roughly proportional to E * log V. Plugging in 120 million for E and 60 million for V, we get a number of computational operations on the order of 2 billion.
I have a Garmin c340, but I couldn’t find data on its microprocessor. Therefore well assume we are using a Tom-Tom 720, which has a 400 Mhz microprocessor inside. This means it undergoes one clock tick approximately (1 MHz = 1048576 Hz) 400 million times a second. Each operation probably takes on the order of 100 machine instructions. If we assume perfect pipelining in the microprocessor and 0 cache misses ever, we get 1 instruction per tick. That’s 200 billion instructions, at 400 Million instructions per second, for 500 seconds processing time on our GPS unit . 8 minutes would be a long time to wait for a route, and that’s with a number of conservative assumptions. Once you take memory latency into effect, you’re probably looking at 16-20 minutes to find a route.
Your little GPS unit inside your probably employs a heuristic that favors taking interstates over back roads, among others. It almost definitely also uses the fact that the graph of the roads embedded on the surface of a sphere. It sure would be interesting to figure out what kind of algorithms they use inside that little thing. Google Maps is an entirely different story- they have much faster processors and can probably find paths in parallel. What sort of parallel algorithms for finding shortest paths exist? Could you cache frequently used route portions? How would that work ? Just something to think about.