Hi all,
in another failed attempt to solve the 2-freecells deal No. 982, I have
implemented a scheme which I've called "Split-BrFS". It was implemented in the
main branch in the repository.
What it does is run a standard Breadth-First-Search
(
http://en.wikipedia.org/wiki/Breadth-first_search ) until a certain number of
positions accumulated in the queue, and then dump the queue it has so far to a
file, one position after the other in separate lines. After that, the dump file
is processed for duplicates, and then a different instance of the same solver
loads it again for processing the reached positions one by one, and infer
more BrFS derived positions for them.
The problem I found with this scheme (whose main file can be found at
scripts/982_dbm_total.bash in the distribution) is that it took too long and
built too many states.
However, now that I think about it, I think I can make it faster by making the
states from the previous scans in the current iteration of the solver run, be
kept in the cache so as to prevent them from being traversed again by the
solver when inspecting further boards. I'm going to try that out soon.
Meanwhile, I've began work on a queue implementation that offloads most of the
data to the hard disk in hope of conserving space. I've written a prototype
for it in Perl 5 and tested it and need to translate it to C.
Regards,
Shlomi Fish
--
-----------------------------------------------------------------
Shlomi Fish http://www.shlomifish.org/
Understand what Open Source is - http://shlom.in/oss-fs
If you have the same ideas as everybody else, but have them one week earlier
than everyone else — then you will be hailed as a visionary. But if you have
them five years earlier, you will be named a lunatic. ( Barry Jones )
Please reply to list if it's a mailing list post - http://shlom.in/reply .
Received on Wed May 16 2012 - 10:00:58 IDT