[r-t] Composition search?

[Don Morrison]

On Mon, Nov 23, 2015 at 6:15 PM Alan Burlison <alan.burlison at gmail.com>
wrote:
> Hmm, interesting - thanks. I was thinking of just generating then
> proving but it sounds like that's unlikely to be a good approach

If you compute up front the falseness between nodes in the graph you are
searching you prune a *lot* of false possibilities early; without some such
pruning, I believe generating all the peal lengths, even tenors together,
of Cambridge Major is intractable* (in fact, that's why Cambridge is so
tractable, because it has so much falseness to trigger early pruning; doing
a full search of all possible tenors together peals of Bristol is a much
bigger job). And, while the exponential costs of the search dominate the
constant costs per candidate, even those constant costs will go up
significantly in your scheme. By generating only true touches the cost of
recording each true candidate you produce is near zero, while the cost of
generating and comparing 5,000 rows for all the candidates, true or false
(and nearly all, of course, are false), is non-trivial: even if you use an
appropriate, linear time scheme for comparing them, simply generating 5,000
rows is a relatively expensive thing to have in an inner loop that is run
billions+ times.

In my experience the most valuable thing you can do is find ways to prune
the search space. In addition to truth, I frequently use musical or other
properties I desire as a way to determine early that a path through the
graph will not be sufficiently fruitful.



* I'm not sure of the depth of the search for tenors together Cambridge.
It's less than the 157ish that you'd have were it tenors parted, since
chunks of leads between calling positions coalesce, though it gets slightly
complicated 'cause of Befores. Let's assume a depth of 50, which is
conservatively low. There are three transitions (plain, bob, single) out of
every node (really only two at Befores, but by using 50, we don't have to
worry about that, we're aiming for a lower bound on the cost), so we've got
3^50 candidates to inspect. Unless you're doing something clever, you need
to get to the end of even those that don't come round. 3^50 is a little
under 10^24. Figure, I think conservatively again, 1 microsecond for
generating each candidate and deciding whether or not it comes round and is
true. Single threaded that's 10^18 seconds, or over 10^13 years. Even if
your multi-threaded implementation could reduce that by a factor of a
thousand, that's still longer than the current age of the universe.



-- 
Don Morrison <dfm at ringing.org>
"The universe winds down. That's how it's made."
                -- John M Ford, "Against Entropy"
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://bellringers.net/pipermail/ringing-theory/attachments/20151124/34f764f6/attachment-0003.html>