Subj : Re: Implementing A* algorithm
To   : comp.programming
From : Gerry Quinn
Date : Thu Jul 21 2005 01:25 am

In article <1121891837.104677.264740@f14g2000cwb.googlegroups.com>, 
websnarf@gmail.com says...
> Gerry Quinn wrote:
> > Huub says...

> > > I'm not a real good programmer, and I have a route problem. I have a
> > > robot that has to find the shortest route through a maze. Options for
> > > doing this are either the A* or Dijkstra's algorithm. My maze consists
> > > of 15 nodes, with each node only connected to at least 1 of it's direct
> > > neighbours. All distances between the nodes are the same. Since
> > > wikipedia tells me that A* is faster than Dijkstra, I would like to know
> > > how the weights work out for either a linked list or an array?
> >
> > A* is faster than Dijkstra only when the overhead of the more
> > complicated calculation is balanced out by the usefulness of the
> > distance heuristic.
> 
> In this case since we have the additional problem that there is no
> interesting "heuristic" to encode.  Usually you have a way of
> "estimating" the distance between one node to the end via, say, a
> cartesian metric.
> 
> But in this case, the traversal cost is always 1.  So the cost can at
> best be estimated by the number of nodes not yet visited.

I don't think he ruled out the existence of a heuristic, except 
indirectly by referring to the problem as a maze.  One definition of a 
maze is a map with no heuristic for distance to the destination.

The common case of a grid of square or hexagonal tiles has a constant 
distance between nodes, but is perfectly amenable to A*.  It's possible 
that his nodes contain information relating to a Cartesian or other 
metric.

- Gerry Quinn

.