The original algorithm for generating a meta-scan (see
http://xrl.us/beuigz )
is:
{{{{
# First we record the number of iterations (= states scanned) it took the
scans' to solve a given board for each of a large set of boards. (in our case
the Microsoft 32,000).
# Then, we allocate a certain number of iterations, and assign this quota to
the scan that solves the most boards within this quota.
# Repeat.
}}}}
So if we have _at_Quotas = [350, 500, 600, 200...] we will assign 350 iterations
to the first scan, and then 500 to the second one and then 600 to the third
one, 200 to the fourh, etc.
Question is: what is the optimal _at_Quotas-as-a-function-of-$quota_index
allocation?
For a long time, I couldn't really think of a good way to do that, but
recently, after experimenting with a more specific problem, I came up with
this method:
1. Calculate the results of assigning quotas when picking up _at_Quotas[0] (where
the first scan is 0) from a range of iterations (say anywhere from 100 to
1,000) where Quotas[1 .. $Inf] is being guessed (to say [350,350,350...] till
infinity). Record it as the temporary optimal result.
2. Calculate the results of assigning quotas for a variable _at_Quotas[1] with
_at_Quotas[0] as calculated from Step #1, and the guessed _at_Quotas[2 .. $Inf] .
Record it as the temporary optimal result.
3. Calculate a variables _at_Quotas[2] based on _at_Quotas[0,1] and the guesses.
And so forth.
This will yield _at_Temp_Optimal_Quotas[0 .. $Num_Quotas] that we can use as a
better starting point.
After that I've been thinking that we can repeat this algorithm only this time
while using _at_Temp_Optimal_Quotas as the guessed iterations (and so forth until
we become saturated).
It's not a very time-efficient method, and I'm not sure it guarantees good
results, but it should be easy to code, and so I'd like to see if it works,
and how well it improves upon the existing heuristics.
Regards,
Shlomi Fish
--
-----------------------------------------------------------------
Shlomi Fish http://www.shlomifish.org/
My Aphorisms - http://www.shlomifish.org/humour.html
Bzr is slower than Subversion in combination with Sourceforge.
( By: http://dazjorz.com/ )
Received on Thu Dec 24 2009 - 10:24:28 IST