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

Invisible <voi### [at] devnull> wrote:
> Any idea how the A* algorithm is better than Dijkstra's algorithm?

  Dijkstra's algorithm doesn't use any heuristic and thus probably may
expand more nodes than A*. As wikipedia puts it:

"Generally speaking, depth-first search and breadth-first search are
two special cases of A* algorithm. Dijkstra's algorithm, as another
example of a best-first search algorithm, is the special case of A*
where h(x) = 0 for all x." (h(x) is the heuristic function given to
the A* 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...

  I don't know if it's completely correct analogy, but I think you could
think that A* is a bit like Dijkstra's, but using a heuristic function to
discard nodes more efficiently. A* seems to also be more generic, in that
you can make it perform other types of searches besides pure breadth-first.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
>   Not all roads have the same weight. Some of them are marked as being
> more desirable than others.

I guess things like one-way roads you'd just have two different distance 
metrics, too.

-- 
   Darren New, San Diego CA, USA (PST)
   "Ouch ouch ouch!"
   "What's wrong? Noodles too hot?"
   "No, I have Chopstick Tunnel Syndrome."

Post a reply to this message

scott wrote:
> I imagine it can be quite complex!

Me, I haven't been able to figure out how they store the road data in the 
first place. Just the storage format has to be pretty darn complicated, 
methinks.

-- 
   Darren New, San Diego CA, USA (PST)
   "Ouch ouch ouch!"
   "What's wrong? Noodles too hot?"
   "No, I have Chopstick Tunnel Syndrome."

Post a reply to this message

On Tue, 27 Jan 2009 09:43:49 +0000, Invisible 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??

OSPF. ;-)

It's really no different than network routing and costing.

Jim

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.

What would you do if the GPS showed "You're in: Middle of Nowhere"? :)

Post a reply to this message

Invisible <voi### [at] devnull> wrote:
> 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??

These days, the algorithms usually use an approach like a human would - using a
hierarchical network. Just like you wouldn't consider every byway in all of
Eurpoe when planning a route from, say, 12 Via di Avanti, Assisi, Italy to 42
Rue de Baguette, Beauvais, France, neither does your TomTom.

Theoretically, an exhaustive brute-force approach would be necessary to find the
best route. In practice, a common-sense approach can easily eliminate something
like 99.999% of all roads.

So a typical approach would look like this:

- Find out the best ways from 12 Via di Avanti to the nearest town centers,
using any roads available; this will get you to the town center of Assisi.

- Find out the best ways from Assisi to the nearest bigger cities, ignoring
byways; this will probably get you to Perugia or Terni.

- Find out the best ways from Perugia or Terni to the nearest metropoles, using
only major roads. This will almost inevitably get you to Rome. Make a mental
note to go via Terni, because it gets you faster to Rome than via Perugia.

- Find out the best ways to 42 Rue de Baguette from the nearest town centers,
using any roads available. This will give you the town center of Beauvais.

- Find out the best ways to Beauvais from the nearest bigger cities, ignoring
byways. This will probably give you Amiens, Rouen or St-Denis.

- Find out the best ways to Amiens, Rouen or St-Denis from the nearest
metropoles, using only major roads. This will almost inevitably give you Paris.
Make a mental note to go via St-Denis, because it gets you from Paris fastest.

- Find out the best way from Rome to Paris, using only highways.

- Try out a few alternatives near Rome to check if you can come up with a faster
way. You'll find out that you can eliminate Rome altogether.

- Try out a few alternatives near Terni to check if you can come up with a
faster way. You'll find out that you can eliminate Terni, too, and go via
Perugia.

- Try out a few alternatives near the town center of Assisi. You may find out
that 12 Via Avanti is close enough to the road to Assisi that you don't have to
go via the town center either.

- Similarly, try out a few alternatives near Paris, St-Deniz and Beauvais - only
to find out that you can't optimize much there because the french road systm is
too centered on Paris to come up with any reasonable alternatives ;)

(Actually, TomTom will most likely not operate on town centers, major cities and
metropoles, but rather more generic "traffic nodes" of different hierarchies;
however, the basic concept is the same.)

The common sense behind this approach is that byways and even major roads won't
get you from Italiy to France in any acceptable time.


This approach often may *not* give you the optimal route. However, given that it
will only very rarely be significantly worse than the optimal one, it is
definitely good enough.

Post a reply to this message

> Me, I haven't been able to figure out how they store the road data in the 
> first place. Just the storage format has to be pretty darn complicated, 
> methinks.

Yes, and I suspect they can do quite a lot of pre-processing of the raw data 
to make the searches faster.

Post a reply to this message

Nicolas Alvarez wrote:

> What would you do if the GPS showed "You're in: Middle of Nowhere"? :)

I've seen that enough times now. My place of work isn't on any map, and 
nor is the Hell Hole where my mum likes to go for her holidays.

Post a reply to this message