[r-t] Big searches

[Mike Ovenden]

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!

Mike


----- 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 
> wrote
> an assembler program to do this (in 1989!) to take advantage of the the 
> fact
> 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, 
> never
> after a bobbed or singled lead.
>
> I didn't count the nodes either!
>
> Graham
>
>
> _______________________________________________
> ringing-theory mailing list
> ringing-theory at bellringers.net
> http://bellringers.net/mailman/listinfo/ringing-theory_bellringers.net