Subj : Re: Implementing A* algorithm
To   : comp.programming
From : websnarf
Date : Wed Jul 20 2005 02:37 pm

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.

Of course, whether or not Dijkstra is the correct algorithm for you is
not 100% clear.  You might allow/require the revisiting of some nodes
more than once for example.  This will require some care in dealing
with properly.  For example, growing a (path,start,end) kind of partial
result might be the right way to go.

> For 15 nodes, both should take about a microsecond, so it doesn't
> matter which you use.

Yeah, clearly this problem is too small.  But presumably the OP might
want to scale the solution in the future.
 
-- 
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

.