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

Alan Burlison alan.burlison at gmail.com
Wed Nov 25 13:55:57 UTC 2015


On 25/11/2015 12:12, Ian Broster wrote:

> You can remove rotations of the same touch from the search space by
> using the path from the root to the current node as your starting point
> for the next recursion.
>
> For example, if your path from root to node is ppppppb (because you have
> already found that ppppppp is false (or actually, comes round and makes
> any longer touch containing it false - awkward corner case!) then you do
> not need to try (ever) the sequence ppppppp in your search space. You do
> this by using the path ppppppb to prune direct the next recursive call.
>
> Sorry that's not explained very well! It was years ago I last coded
> something like that.

Actually, that's perfectly clear. The rotations point is interesting as 
well, although checking if one path is a rotation of another might be 
fairly expensive, especially as the paths get longer.

> As you get further through the search space, the gains from this get
> much greater. i.e. if your path starts pbbb... then you never need to
> look at anything with more than one consecutive p.

> Obviously, an easy optimization is to do this in a loop rather than a
> recursive call. That more than doubles the speed, but that optimization
> is clearly secondary to reducing the search space!

Thanks for the insights!

-- 
Alan Burlison
--




More information about the ringing-theory mailing list