[r-t] Bobs only Erin Triples (was: Composition search)

[Don Morrison]

On Wed, Nov 25, 2015 at 6:26 AM Alan Burlison <alan.burlison at gmail.com>
wrote:
> I was wondering if there was any benefit in doing a breadth-first search
> rather than depth-first and using the intermediate results to more
> aggressively prune the search tree but I'm not sure if that will help or
> not. Thanks for all the food for thought!

Leaving aside for a moment the massive savings you get from pruning false
branches as you go, going at it breadth first you'd be storing something
like 2^839 intermediate results. That's a little over 10^252. The universe
is only 10^185 Planck volumes big.

Will aggressive pruning as you go make this tractable? I don't know, but I
doubt it.

On the other hand, I'm confident there are clever ways to do things other
than the most brute force depth first search. What they are, I don't know.

BTW, for other compositional problems I often use a partial breadth first
search. I go breadth first backwards from the final state, limiting the
depth of that search so I can have a reasonable number of candidates. For
surprise major this is usually about a quarter peal's length. Then my
forward, depth first search only needs to go to a shallower depth, aiming
to join up with one of these appropriate final states. My experience with
such problems, though, leads me to suspect such a scheme will not be any
help for an extent of Erin. It tends to be most helpful if there are
properties besides truth that I desire, properties that are more likely to
clump locally, typically musical properties. A large part of the reason, I
believe, is that doing this backwards breadth first caching of possible
final paths adds a lot more nodes to the graph being searched, each of
which then must be accounted for when keeping track of the inter-node
falseness. You only win when that extra cost is less than the savings you
get by early pruning.


-- 
Don Morrison <dfm at ringing.org>
"The improvements of ages have had but little influence
on the essential laws of man's existence."
          -- Henry David Thoreau, _Walden_
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://bellringers.net/pipermail/ringing-theory/attachments/20151125/6319c3d4/attachment-0003.html>