[erlang-questions] A* algorithm

ok <>
Wed Aug 1 03:30:52 CEST 2007


Someone asked about implementations of A* in Erlang or any other
functional language.  One important thing to understand about A*
is that it is not a complicated algorithm at all; the Haskell
version someone pointed to is harder to read than need be.  Here's
the pseudo-code from the Wikipedia page:

function A*(start,goal)
     var closed := the empty set
     var q := make_queue(path(start))
     while q is not empty
         var p := remove_first(q)
         var x := the last node of p
         if x in closed
             continue
         if x = goal
             return p
         add x to closed
         foreach y in successors(x)
             enqueue(q, p, y)
     return failure

 From that we can easily see that there are two key data structures:
a "closed" set and a min-priority-queue (q).  Suitable data structures
are available for Erlang, meaning that finishing the job is about
a page of code.  (My Prolog version is 307 lines including blank lines
and comments, 159 SLOC including implementations of all data structures,
61 lines excluding data structures.)

However, we can also see the second important thing about A*, which is
that *every* state it has ever heard of is *stored* in one of those two
data structures.  If (number of nodes) * (new space required per node)
is high, that is, if it is a non-trivial problem, you probably don't
want A*.  You want IDA*.  I note that there was a paper about  
parallel IDA*:

  Efficient Parallel Execution of IDA on Shared and Distributed  
Memory Multiprocessors
Saletore, V.A.   Kale, L.V.
Oregon State University;

This paper appears in: Distributed Memory Computing Conference, 1991.  
Proceedings., The Sixth
Publication Date: 28 Apr-1 May 1991
On page(s): 355-361
ISBN: 0-8186-2290-3

I haven't actually seen that paper myself.




More information about the erlang-questions mailing list