I’m hoping a search algorithm exists for what I want to do, but I just don’t know what it is…
Say I’ve got a tree made from a single root A. I have a bunch of ‘rules’ which can attach little sub-trees to certain existing nodes. Eg. rule 1 might attach to an A node and add children B and C, and rule 2 might attach to C and add E (via D).
My start state is an initial tree (eg. A at root and B, C, D as children) and a bunch of nodes that need to be in the tree (eg. W, X, Y, Z). The required nodes don’t have to be leaves, just in the tree somewhere. I ‘just’ need to figure out the rules needed to expand the first tree into one that satisfies the conditions of the second.
I thought I could use STRIPS ( http://en.wikipedia.org/wiki/STRIPS ) but unfortunately that seems to require some kind of heuristic to drive the internal A* routine, and I don’t think I can actually come up with a workable heuristic in this case. So at the moment my only idea is a brute force approach, which is obviously going to be really slow.
Anyone any suggestions? Thanks.