[r-t] 147 TDMM with singles?
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
then INSIST THAT THE SECOND METHOD STARTS FROM AN OUT-OF-COURSE LE. Do
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