On 10/13/06, Sander Land <sander.land / gmail.com> wrote:
> On 10/13/06, Jacob Fugal <lukfugl / gmail.com> wrote:
> > Actually, the basic algorithm he explained isn't quite A-star (I'm
> > guessing on purpose). There's lots of room for improvement in both
> > algorithm and heuristic. I'm guessing that's where the fun and variety
> > of this quiz will be. :)
> >
> > Jacob Fugal
>
> Isn't he just explaining a greedy search without backtracking?
> Also, this algorithm seems to go wrong even on the small map:

Pretty much, yes. 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

For the sake of both brevity and challenge, I've left some details out, such as:

* How do you prevent cycles and backtracking?
* How do you calculate costs for a new state?
* How do you manage your priority queue?
* How do you keep track of the path so you can return it when you hit a goal?

Happy hacking!