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


On Mon, 18 Jul 2005, Huub wrote:
>
>> You have automatically excluded [...]

   By the way, make sure to include attributions for material you quote 
from other people's posts. It makes it a lot easier for your readers (that 
is, *us*) to keep track of who said what.

> And yes, I'm trying to figure out how to represent a node or an entire 
> graph. BTW, by the answers from all of you I'm trying to figure out 
> whether to use A*, Dijkstra or breadth-first. I thougt I had figured it 
> out, but now I'm in doubt again. In any case I want the simplest 
> algorithm for a 15 nodes graph.

   Dijkstra's algorithm is /the/ algorithm. It just plain works, as long as 
you don't have any edges with negative weights. The idea is that you start 
by exploring the cheapest (partial) path you haven't yet explored; and 
therefore the first complete path you find will be the absolute cheapest
possible.

   Breadth-first search is a special case of Dijkstra's algorithm that you 
can use when all the edges have the same weight. It just involves a change 
of data structures; no big deal. I advise you to use the complete version 
of Dijkstra's algorithm, so that you get practice implementing it and so 
that you have the code if you ever need it again for more complicated 
graphs.

   A* is a heuristic algorithm based on Dijkstra's. The idea here is that 
instead of greedily taking the partial path that is cheapest at the 
moment, you should "look ahead" to the finish and take the partial path 
that seems to advance you the farthest. Operative phrase: "seems to."
In other words, you need to make up a /heuristic/ that will tell you 
roughly how far it is from any given node to the finish /without your 
having to compute it exactly/. So A* makes sense only when you have a
graph embedded in some kind of space, such as the Euclidean plane.
Read the Wikipedia article for plenty of information. In any event, I
don't advise you to use A* unless you know what you're doing --- and you 
admit you don't! :)

HTH,
-Arthur

.