From: Axel Etzold <AEtzold@...>
Date: 2009-09-18T18:07:06+09:00
Subject: Re: Best-First Algorithm in Ruby?


-------- Original-Nachricht --------
> Datum: Fri, 18 Sep 2009 14:10:27 +0900
> Von: Mason Kelsey <masonkelsey@gmail.com>
> An: ruby-talk@ruby-lang.org
> 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 
-- 
GRATIS f�r alle GMX-Mitglieder: Die maxdome Movie-FLAT!
Jetzt freischalten unter http://portal.gmx.net/de/go/maxdome01