From: James Edward Gray II <james@...>
Date: 2006-10-14T01:28:16+09:00
Subject: Re: [QUIZ] A* (#98)

On Oct 13, 2006, at 11:15 AM, Jacob Fugal wrote:

> Hoping it's not a spoiler, here's how you really do A*:
>
> 1) use a priority queue (prioritized by estimated cost)
> 2) initialize the queue with the start state(s)
> 3) while the queue is not empty
>   a) shift the head off the queue (cheapest state found so far)
>   b) return the path to the current state if the state is a goal state
>   b) expand that state by finding neighbors and calculating their  
> costs
>   c) push each neighbor onto the queue
> 4) if the queue emptied without finding a solution, there is no  
> solution

The priority queue is the major aspect not really touched on by the  
quiz, yes.  If you need help with this, a past Ruby Quiz about heaps  
had code you could borrow:

http://www.rubyquiz.com/quiz40.html

Just be sure to read the summary where I fix a couple of bugs in the  
code.

James Edward Gray II