[r-t] Big searches

[Don Morrison]

Mark Davies wrote:
> How do you avoid finding the "trivial variations" (shunts moved) in the fast 
> search, then? It sounded something like that.

Remember, unlike you I'm mod'ing out by the course ends. Thus a shunt is when I 
have two edges between the same two nodes, so it can be picked up statically, 
during setup. Only one of those edges remains in the graph I'm searching, but 
note is made of the multiple permutations it might represent. After finding a 
solution, as part of recording/reporting it, I work back through actually doing 
the necessary permutations, to make sure I get an appropriate part end -- even 
if there are no shunts present, that needs to be done anyway, since there are 
cases where you get mutually true parts that can't be joined up with the calls 
you're using.

> Sounds a bit like the music pruning that Elf does, although it doesn't do a 
> BFS - instead it just uses N*(value of highest-scoring node) to estimate the 
> remaining possible music (for spliced, it can do the same thing for COM and 
> method balance). It's definitely a big win, even in this simplified version. 
> It is the most useful optimisation as yet unprogrammed in SMC32!

It's particularly a big win in the toy example being discussed (either Yorkshire 
or Rutland ;-) as bobs only, all 24 56s means there are some nodes each of which 
*must* be included, so during the setup it notes the required nodes and deletes 
all the nodes false against those. In more complicated cases you end up 
iterating a few times during setup as the repercussions of some things being 
required may allow other things to become required, and so on, and it can do 
some useful pruning of the search before you ever start.

If we only wanted 18 56s, say, or if we allowed out of course courses that also 
included 56s, it would only be able to prune stuff dynamically. While still a 
win, it is less so, and also makes node visitation slightly more expensive.

Your mention of guessing remaining possible music and so on -- I've tried 
playing with heuristics like that do direct the search, but never got it to do 
anything terribly helpful for me. Maybe I just wasn't approaching it right.

-- 
Don Morrison <dfm at ringing.org>
"A peal is just a load of sweat and blisters, but a Sotherans memorial
peal card is a comfort in your old age."
                                 -- Old Bailey, change-ringers archives