Subj : Re: Implementing A* algorithm
To   : comp.programming
From : Arthur J. O'Dwyer
Date : Wed Jul 20 2005 03:39 am


On Mon, 18 Jul 2005, CBFalconer wrote:
>
> Christer Ericson wrote:
>> cbfalconer@yahoo.com says...
>>
>>> You have automatically excluded all replies from those not familiar
>>> with A* (whatever that may be) and/or Dijkstra's (who was a
>>> remarkably able programmer and probably published thousands of
>>> algorithms during his lifetime).

   (That's a good thing.  However, I think you're wrong, in that he did 
/not/ apparently manage to exclude replies from you.)

>> There's nothing wrong with the OP's question.  There is only
>> one algorithm of Dijkstra's known as "Dijkstra's algorithm"
>> and it is taught in many computer science programs. See:
>>
>> http://en.wikipedia.org/wiki/Dijkstra's_algorithm
>
> Well, on casual examination of my books here, I immediately find
> Dijkstras algorithm as an extension to N processes of Dekkers
> algorithm for mutual exclusion.  I can also find his solution to
> the Dining Philosophers problem.

   So what? Newton developed hundreds of methods, Fermat wrote down dozens 
of little theorems, and Duff probably invented several different devices. 
Does that mean that we should flaunt our ignorance every time someone 
mentions Newton's method, Fermat's Little Theorem, or Duff's device?
(I say not.)

>> The A* algorithm is taught in just about every introductory
>> AI class in the world:
>>
>> http://en.wikipedia.org/wiki/A-star_algorithm
>>
>> I don't see how you think that anyone unfamiliar with either
>> or both algorithms would be able to meaningfully comment on the
>> merits of the one algorithm over the other.
>
> I never took an introductory AI class, and I gravely doubt that I
> ever will.  Since the original problem (IIRC, you snipped any
> evidence of it) showed similarities to traveling salesmen, I
> suspect it requires some sort of exhaustive search.

   Come on!  The OP wrote, and I quote: "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."
   That's exactly correct --- Dijkstra's algorithm is /the/ algorithm
for finding the shortest route through a maze (i.e., along the edges
of a directed graph from node START to node FINISH). A* is a heuristic
"lossy optimization" of Dijkstra's algorithm; as Christer says, it's
taught in every computer science curriculum in the world and is well
known to every AI programmer to boot.
   Googling "Dijkstra's" will get you tons of information on Dijkstra's
algorithm. To find information on A* you have to be more clever: you
have to visit
http://en.wikipedia.org/wiki/A*


   The OP's problem obviously has /nothing/ to do with "traveling 
salesmen," whatever that means.

-Arthur,
penny wise

.