[r-t] Big searches
mike.ovenden at homecall.co.uk
Fri Dec 28 22:44:48 UTC 2007
MUG minor: I presume you didn't find anything either, which makes me a bit
more comfortable with the negative result. If I remember correctly, singles
didn't make any improvement in achievable length over what could be obtained
using bobs alone.
I used what MBD would describe as a rotationally sorted tree search, worked
in terms of the cosets of the group that forms MUG leads ([6.34] in Price's
catalogue) rather than individual rows, and pruned out the repetitive stuff
caused by the equivalences you describe. Without the latter it'd probably
still be running. The tree is ternary, but the constraint whereby a single
only follows a plain lead makes it more like a (1 + SQRT(2))-ary tree, which
is a LOT smaller!
----- Original Message -----
From: "Graham John" <graham at changeringing.co.uk>
To: <ringing-theory at bellringers.net>
Sent: Thursday, December 27, 2007 12:00 PM
Subject: Re: [r-t] Big searches
> Mike wrote:
>> Out of curiosity I subsequently ran a search for 720s
>> (of MUG Minor) with bob=14, single=1456, at the section
>> end. It took several months to complete, but sadly I
>> have no idea how many nodes.
> It would depend on the pruning algorithm and optimisation you used. I
> an assembler program to do this (in 1989!) to take advantage of the the
> that each division contains all the possible rows with an arrangement of
> three pairs of bells, resulting in an economic bit proving table. The most
> important optimisation is to avoid the massive repetition of effort caused
> by singles, by removing the following equivalences.
> --- -ss s-s ss-
> sss s-- -s- --s
> -s s-
> -- ss
> This is easy to do by only generating a single following a plain lead,
> after a bobbed or singled lead.
> I didn't count the nodes either!
> ringing-theory mailing list
> ringing-theory at bellringers.net
More information about the ringing-theory