Best-First Algorithm in Ruby?

[Mason Kelsey]

[Note: parts of this message were removed to make it a legal post.]

I am writing a Best-First Search program in Ruby but I have never done tree
searches before and so am a bit lost. This routine is being applied to the
8-puzzle problem of moving 8 tiles plus a blank space in an 3 x 3 grid.
Since I am new to both Ruby and search algorithms in general, I a looking
for a template or actual code as a Ruby program. I've already written the
Manhattan move method to determine the heuristic value of each state, and
the move function for making a move, and a third method for determining what
moves are possible. But writing the first-best routine without some
template to use is beyond my current capabilities. I'm trying to move
beyond that limitation.

I've done a Google search and referenced five books on Ruby and not found
any good template, pseudo code, or even a Ruby routine that would do the
searches. Does anyone know of a coded example in Ruby of the Best-First
search algorithm? It it is applied to the 8-puzzle that is even better, but
if I can find a template I should be able to apply it to my problem.

Thanks in advance for being pointed in the right direction.

Always something new to learn.

No Sam

 

[Axel Etzold]

-------- Original-Nachricht --------

Datum: Fri, 18 Sep 2009 14:10:27 +0900
Von: Mason Kelsey <[email protected]>
An: (e-mail address removed)
Betreff: Best-First Algorithm in Ruby?

I am writing a Best-First Search program in Ruby but I have never done
tree
searches before and so am a bit lost. This routine is being applied to
the
8-puzzle problem of moving 8 tiles plus a blank space in an 3 x 3 grid.

Dear Mason,

Since I am new to both Ruby

welcome!
If you are looking for a nice and short introduction to Ruby, you can have
a look at this tutorial :

http://pine.fm/LearnToProgram/?Chapter=00

It's an introduction that will take you all the way from no computing knowledge at all to coding object-orientedly ... so maybe it is a good idea to go through this first.

With respect to search algorithms, your problem can be solved using the
A* algorithm, which is a best-first search algorithm. You can
find a description of how to apply it here:

http://www.redfish.com/dkunkle/mypapers/EightPuzzle.pdf ,

In the Ruby community, there is a collection of problems and Ruby solutions called Ruby quiz, whose solutions are thoughtfully commented by the maintainers of the quiz.
A*-search is here:

http://rubyquiz.com/quiz98.html

And of course, you can adapt the pseudocode on the Wikipedia A* search page.


Best regards,

Axel