Here's something to stop and think about...

I have a TomTom One. It's a small, hand-held device with a set of road 
maps of the whole of the UK stored in flash RAM.

I have no idea what kind of CPU powers this device, but what I can tell 
you is this: When I ask it to plot a route, it can seemingly analyst 
tens of thousands of roads and quickly find a suitable route. (Typically 
takes less than 10 seconds.)

That doesn't *sound* very impressive... until you sit down and try to 
think of a way to program such a thing yourself. How would you do that??

Post a reply to this message

> That doesn't *sound* very impressive... until you sit down and try to 
> think of a way to program such a thing yourself. How would you do that??

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Post a reply to this message

Invisible <voi### [at] devnull> wrote:
> That doesn't *sound* very impressive... until you sit down and try to 
> think of a way to program such a thing yourself. How would you do that??

  Not all roads have the same weight. Some of them are marked as being
more desirable than others. After that it's just a question of running
an algorithm like http://en.wikipedia.org/wiki/Dijkstra's_algorithm

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
> Invisible <voi### [at] devnull> wrote:
>> That doesn't *sound* very impressive... until you sit down and try to 
>> think of a way to program such a thing yourself. How would you do that??
> 
>   Not all roads have the same weight. Some of them are marked as being
> more desirable than others. After that it's just a question of running
> an algorithm like http://en.wikipedia.org/wiki/Dijkstra's_algorithm

As far as I can tell, Dijkstra's algorithm appears to visit *all* the 
nodes of the graph. You can then read off the optimal path from the 
initial node to any desired node - but surely computing the distance 
function for every road in the country would be infeasible?

I guess if you know "approximately" what the optimal distance ought to 
be, you can just ignore any node that's further away then that or 
something... You're still computing quite a lot of data though.

Post a reply to this message

> As far as I can tell, Dijkstra's algorithm appears to visit *all* the 
> nodes of the graph. You can then read off the optimal path from the 
> initial node to any desired node - but surely computing the distance 
> function for every road in the country would be infeasible?
>
> I guess if you know "approximately" what the optimal distance ought to be, 
> you can just ignore any node that's further away then that or something... 
> You're still computing quite a lot of data though.

You're beginning to invent the A* algorithm there ;-)

http://en.wikipedia.org/wiki/A*

I assume in real life applications there is some custom algorithm with many 
additions and hacks based on knowledge of the road system (as opposed to 
applying this to say a computer network).  Also I assume that roads are 
classified into speed ratings, so first it checks for any nearby motorways 
at either end and then checks a route based on that, before fiddling with 
the end sections etc, I imagine it can be quite complex!

Post a reply to this message

>> I guess if you know "approximately" what the optimal distance ought to 
>> be, you can just ignore any node that's further away then that or 
>> something... You're still computing quite a lot of data though.
> 
> You're beginning to invent the A* algorithm there ;-)
> 
> http://en.wikipedia.org/wiki/A*
> 
> I assume in real life applications there is some custom algorithm with 
> many additions and hacks based on knowledge of the road system (as 
> opposed to applying this to say a computer network).  Also I assume that 
> roads are classified into speed ratings, so first it checks for any 
> nearby motorways at either end and then checks a route based on that, 
> before fiddling with the end sections etc, I imagine it can be quite 
> complex!

I imagine it regards the road network as a "network of networks", 
similar to the way the high-level Internet routing protocols work.

As in, it probably attempts to construct a route on main roads only with 
endpoints "near" to the desired endpoints, and then attempts to augment 
that with the minor roads needed at each end. (Probably builds several 
possible motorway routes so it can find a reasonably optimal one.)

The selections like "prefer motorways" and "avoid motorways" probably 
adjust the internal cost function driving the algorithm. Of course, in 
terms of distance, Euclid straight-line distance is a pretty good 
estimate until you compute the actual road distances.

I wonder: Does it cost more to design a better routing algorithm, or fit 
a faster CPU? ;-)

Post a reply to this message

> I wonder: Does it cost more to design a better routing algorithm, or fit a 
> faster CPU? ;-)

More often than not the speed it limited by the read speed from the medium 
that the map data is stored on.  In my car for example it is on DVD, which 
means that is often takes up to 30 seconds to calculate the route - which is 
a bit pants.  Some cars have hard drive systems which are way faster, and of 
course the portable navigation systems have flash based memory.

But still I find it amazing how I can be in the middle of nowhere in 
southern Germany, and then just type in my mum's address 1200 km away and in 
under a minute it tells me exactly which roads to go on to get there and 
exactly how many km it is.  Surely just knowing every single street name in 
Europe is quite a lot of data, let alone the routing information plus the 
road geometry information.

Post a reply to this message

scott wrote:

> But still I find it amazing how I can be in the middle of nowhere in 
> southern Germany, and then just type in my mum's address 1200 km away 
> and in under a minute it tells me exactly which roads to go on to get 
> there and exactly how many km it is.  Surely just knowing every single 
> street name in Europe is quite a lot of data, let alone the routing 
> information plus the road geometry information.

It *is* pretty mental, eh?

Mind you, I saw a guy with an illegal 186 laptop (you know, the ones 
with the blue and purple LCD screens?) that could compute routes around 
the UK given only a few seconds or so. And that was back in 1989. I 

Post a reply to this message

Invisible <voi### [at] devnull> wrote:
> >   Not all roads have the same weight. Some of them are marked as being
> > more desirable than others. After that it's just a question of running
> > an algorithm like http://en.wikipedia.org/wiki/Dijkstra's_algorithm

> As far as I can tell, Dijkstra's algorithm appears to visit *all* the 
> nodes of the graph.

  No, it doesn't. It starts advancing from the starting node towards all
possible directions, and then follows those paths which are most promising
(according to the sum of weights of those paths).

  In a way it's a kind of breadth-first search, where the weight of the
paths searched so far is kept as equal as possible. It stops immediately
when it reaches the end node (because it would, rather obviously, not make
any sense to continue because the optimal path has already been found). It
actually works even if all the arcs between nodes have the same weight, but
of course then there's no "most promising" path which would take priority.
However, even in this case it will not search through *all* nodes: It will
perform a pure breadth-first search and stop when it has found the shortest
path to the end node.

> I guess if you know "approximately" what the optimal distance ought to 
> be, you can just ignore any node that's further away then that or 
> something... You're still computing quite a lot of data though.

  Dijkstra's algorithm doesn't need any cutoff. It starts advancing in a
breadth-first order (according to the sum of weights of the paths) and
when it reaches the end node, it has found the optimal path.

-- 
                                                          - Warp

Post a reply to this message

>> As far as I can tell, Dijkstra's algorithm appears to visit *all* the 
>> nodes of the graph.
> 
>   No, it doesn't. It starts advancing from the starting node towards all
> possible directions, and then follows those paths which are most promising
> (according to the sum of weights of those paths).
> 
>   In a way it's a kind of breadth-first search, where the weight of the
> paths searched so far is kept as equal as possible. It stops immediately
> when it reaches the end node (because it would, rather obviously, not make
> any sense to continue because the optimal path has already been found).

Ah. Wikipedia's article doesn't seem to mention a stopping condition 
other than "all nodes have been visited".

Also, I ran the algorithm by hand with pencil and paper and it appeared 
to give me a suboptimal route. I ran it for a bit longer and it became 
optimal. I don't know if I misunderstood the algorithm or just made a 
trivial mistake in running it.

>   Dijkstra's algorithm doesn't need any cutoff. It starts advancing in a
> breadth-first order (according to the sum of weights of the paths) and
> when it reaches the end node, it has found the optimal path.

Any idea how the A* algorithm is better than Dijkstra's algorithm?

I was working under the assumption that Dijkstra's algorithm visits all 
the nodes of the graph and A* doesn't need to - but if that isn't the 
case, I'm left wondering how A* is actually better...

Post a reply to this message