On Sat, 16 Aug 2003, Ron wrote:
> Hi Shlomi,
>
> I was just wondering what the heuristic function of the A* algorithm
> is and, more importantly, how you came up with it?
Freecell Solver does not use A*. It uses either Depth-First Search or
Best-First Search. The heuristic for the BeFS search can be found in the
function freecell_solver_a_star_rate_state (yes - it's badly name as a
relic of a confusion I had):
http://cvs.berlios.de/cgi-bin/viewcvs.cgi/fc-solve/fc-solve/source/scans.c?rev=1.45&content-type=text/vnd.viewcvs-markup
This function makes 5 measurements and processes them using 5 relative
weights:
1. The number of cards out.
2. The maximal sequence move possible.
3. The number of cards under sequences.
4. The length of the sequences which are found over renegade cards.
5. The depth of the board in the solution.
Note that in the meta-scans that were constructed out of multi-tasking
scans, mainly DFS and randomized DFS scans were used.
Tom Holroyd's patsolve has an even more sophisticated weighting function
and also its own specialized scan.
> In other words,
> how do you measure the distance to the goal for a given state?
>
> (As an aside, is it just me, or is using a "pathfinding" algorithm, a
> search, kinda weird for a problem that has no unknown elements in it?
> I dunno. Just food for thought.)
>
What do you mean by that? Please explain more if you can.
Regards,
Shlomi Fish
> Thanks,
> - Ron
>
>
>
>
> To unsubscribe from this group, send an email to:
> fc-solve-discuss-unsubscribe_at_yahoogroups.com
>
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>
----------------------------------------------------------------------
Shlomi Fish shlomif_at_vipe.technion.ac.il
Home Page:
http://t2.technion.ac.il/~shlomif/
An apple a day will keep a doctor away. Two apples a day will keep two
doctors away.
Falk Fish
Received on Sun Aug 17 2003 - 00:16:37 IDT