[r-t] 147 TDMM with singles?

Alexander Holroyd holroyd at math.ubc.ca
Tue Oct 19 20:49:15 UTC 2010

Having thought a bit more about this, I suspect that with a suitable tweak 
the search could be done very efficiently, probably in seconds.  All it 
needs is someone to code it (Richard?) :)

The algorithm for the search for plans is almost the same as before. 
Start with all 120 in-course and out-of-course le/lhs.  As before, if some 
leads of methods are given, one can determine, for any le, the methods 
that are "possible" there.  The main difference is that if there are zero 
possible methods for some le, it does not mean that the current branch of 
the search tree can be abandoned.  That only happens if there are no more 
methods that can be added, and there are less than 30 leads in place. 
(Or, marginally better, if the total of [existing leads] + [les with some 
possible methods] is less than 30).  So the algorithm is a tree search as 
before, again trying the le with fewest possible leads first, but with the 
modification that when a le is exhausted (no more possible methods), we 
record that fact and move on to the next le.  And with a different rule 
for when to backtrack.

Now here is a tweak that should speed it up alot.  Since we are only 
interested in extents with singles, we can insist on an out-of-course 
method.  So insist that the first method starts from rounds as before, and 
this by trying all the out-of-course les as usual, starting with the ones 
with fewest possibles.  If one of them has no possibles, we go to another 
out-of-course le, etc.  As before, we can still insist that all methods 
after the first are greater than or equal to the first method.

It will probably be very fast, because there will be very few possible 
choices for the first two methods, and once they are chosen the 
possibilities will typically be very restricted.

The joining-together search should also be quick, I suspect.  We will have 
a single allowed as an additional possible lead end change, but of course 
a particular lead end change should only be permitted if it joins up to 
one of the other leads (one that is not already in use).  This means that 
the average number of available lead end changes will usually be no more 
than in the bobs-only search, and the large amount of falseness may well 
make actually the search much quicker than the bobs only case.


More information about the ringing-theory mailing list