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

[Alan Burlison]

On 25/11/2015 12:20, Don Morrison wrote:

> Leaving aside for a moment the massive savings you get from pruning false
> branches as you go, going at it breadth first you'd be storing something
> like 2^839 intermediate results. That's a little over 10^252. The universe
> is only 10^185 Planck volumes big.

That's only true if you explore and store all the intermediate steps, 
and that's clearly infeasible.

> Will aggressive pruning as you go make this tractable? I don't know, but I
> doubt it.

I believe that unless there is a good way of pruning the tree then it's 
pointless even attempting the exercise. As for what that pruning might 
be, I'm not sure. It might be better to come up with a simpler case 
first where the tree can be fully expanded and then use that as a 
testbed for different pruning approaches.

If the aim is to just find *one* valid composition rather than *all* of 
them then it becomes possible to avoid expanding the entire tree. 
However it just gives you a different problem, which is finding good 
pruning and cost functions to direct the search ;-)

> On the other hand, I'm confident there are clever ways to do things other
> than the most brute force depth first search. What they are, I don't know.

If there aren't then any attempt is doomed by the vastness of the search 
space, as you pointed out.

> BTW, for other compositional problems I often use a partial breadth first
> search. I go breadth first backwards from the final state, limiting the
> depth of that search so I can have a reasonable number of candidates. For
> surprise major this is usually about a quarter peal's length. Then my
> forward, depth first search only needs to go to a shallower depth, aiming
> to join up with one of these appropriate final states. My experience with
> such problems, though, leads me to suspect such a scheme will not be any
> help for an extent of Erin. It tends to be most helpful if there are
> properties besides truth that I desire, properties that are more likely to
> clump locally, typically musical properties. A large part of the reason, I
> believe, is that doing this backwards breadth first caching of possible
> final paths adds a lot more nodes to the graph being searched, each of
> which then must be accounted for when keeping track of the inter-node
> falseness. You only win when that extra cost is less than the savings you
> get by early pruning.

I did think about that approach but couldn't see how in this case it 
would help. As you say, it probably helps most in the cases where you 
have other properties to restrict the search space.

-- 
Alan Burlison
--