James Edward Gray II wrote:
> 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

My solution for last week's quiz used an A* search with a priority
queue if anybody wants to see some live code. The queue was, however,
designed for adding large numbers of new states in batches and would
need to be adapted.

By complete coincidence I've actually attempted something almost
identical to this before, attempting top move from any cell on the left
side to any cell on the right. I found that for larger grids an A*
search cell-by-cell becomes unacceptably slow.

I think the real challenge in this quiz will be forming intelligent
methods of reducing the number of states that must be searched. I never
actually did this for the left-to-right problem but have several ideas
for this quiz. Don't worry, they haven't given us the answers to the
real problems :)