[r-t] Big searches
dfm at ringing.org
Sun Jan 6 19:37:54 UTC 2008
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
> 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
More information about the ringing-theory