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

Darren New wrote:
> 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.

I have a 1 GB flash drive in my pocket. It cost me £2. How much space do 
you think they have to play with in a satnav device?

Post a reply to this message

> 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.

Depends on your definition of "optimal". (E.g., total distance, verses 
estimated travel time, any tolls that have to be paid for certain 
routes, traffic volume, etc.)

Did anybody see the one where Google Maps gave a route from something 
like Bristol to Norfolk via Ireland? :-D

Post a reply to this message