At 14:49 28/02/01 +0100, you wrote:
>Shlomi Fish wrote:
> >
> > Hi!
> >
> > Stephan Kulow suggested that instead of storing all the encountered states
> > in memory, Freecell Solver should use an LRU cache that will delete states
> > that were not used recently. It could be a good idea because it will enable
> > us to run longer while occupying the same amount of memory. Of course, some
> > dead end states will be checked again, but there are no free lunches in
> > programming.
> >
> > Each state may contain a counter for the number of times it was reached by
> > the algorithm. And eventually, some of the states with the lowest counters
> > will be removed.
> >
> > The problem is that some states cannot be removed from the cache. In the
> > case of DFS scans such states are those that are found in the current
> > solution path. In the case of A* they are all the states that are found in
> > the scan's priority queue (check out Justin HJ's page for more info) as
> > well as all their parents and forefathers.
> >
> > Remember that there can be more than one thread in action, so it means we
> > have to go over all the threads, and mark all of their important states as
> > un-removable. Then we can remove some of the other states, based on their
> > popularity with the different active scans.
> >
> > Naturally, assuming system threads are used, we will have to halt all the
> > threads before the cleanup is in gear.
> >
>You don't need to halt threads. You only mark the section you want to
>protect.
>You will have a lock for your queue anyway. I don't have a ready answer,
>but
>I would try to have a counter in the parent. If you find a dead end, you
>decrease
>the counter in the parent. If this comes 0, you mark it as dead too. And
>then
>you have nodes with 0 you can remove savely as soon as your memory limit
>is reached.
>If this is enough I can't tell you though
There's probably some literature hanging around about using an LRU cache
with several simultaneous DFS or A* scans. Luckily, I have the entire
Technion at
my disposal (well, not literally) and I can inquire people there. Somebody
should give me an answer or refer me to a knowledgeable source.
I'll let you know as soon as I find out or find a reference.
Cheers,
Shlomi Fish
>Greetings, Stephan
>
>--
>People in cars cause accidents. Accidents in cars cause people.
>
>
>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_techie.com
Home Page:
http://t2.technion.ac.il/~shlomif/
I don't believe in fairies. Oops! A fairy died.
I don't believe in fairies. Oops! Another fairy died.
Received on Wed Feb 28 2001 - 12:35:15 IST