![](/i/fill.gif) |
![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Invisible <voi### [at] dev null> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Warp wrote:
> Invisible <voi### [at] dev null> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
> 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/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
>> 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/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Invisible <voi### [at] dev null> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
>> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |