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
Greetings, Stephan
--
People in cars cause accidents. Accidents in cars cause people.
Received on Wed Feb 28 2001 - 05:50:29 IST