Path: utzoo!attcan!uunet!lll-winken!elroy.jpl.nasa.gov!ucla-cs!makaha!coleman
From: coleman@makaha.cs.ucla.edu (Michael Coleman)
Newsgroups: comp.lang.prolog
Subject: Re: 8-tile puzzle
Message-ID: <36714@shemp.CS.UCLA.EDU>
Date: 3 Jul 90 03:54:42 GMT
References: <12398@sun.udel.edu> <3343@goanna.cs.rmit.oz.au>
Sender: news@CS.UCLA.EDU
Lines: 29

ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes:

>In article <12398@sun.udel.edu>, jms@sun.udel.edu (John Milbury-Steen) writes:
>> [the 8-puzzle, any heuristics?  how about a Prolog program?]

>[How about A*? ]

An improvement on A*, particularly for this problem is IDA*, which stands for
iterative-deepening A*.  Rich Korf used this algorithm to solve the 15-puzzle,
which is difficult or impossible using A* (or was at the time), because of
memory use.

The algorithm is basically iterative depth-first search where cutoff is chosen
in an A* manner.  Quickly, you cut off search when the estimated length of the
shortest completion path from the current node is greater than the bound.  The
bound for each iteration is the smallest estimate seen in the previous
interation which is greater than the bound of the previous iteration.  See
Korf's paper for more details.

The most surprising (to me) feature of this algorithm is that it is faster
and uses less memory than A* for the 8-puzzle.  The reason is that there is no
"OPEN" list to manage; the action is all DFS-like.

I've implemented this in C.  Average solution time for random initial
configurations is 0.2 seconds on a SS1+.
--
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
try.            %% "When at first you 
try :- try.     %%  don't succeed, ..."                  (coleman@cs.ucla.edu)