Tree-minimization heuristics

First, the boilerplate that takes a heuristic [[h]], candidate splittings, and a set of fields, and returns the set of fields with the largest score on [[h]]. «*»= procedure findmaxima(h, candidates, fields) local max S := [] every f := !fields do score := h(candidates[f], f) write(,"Field ", f.name, " scores ", score, " on ", image(h)) /max := score - 1 if score > max then max := score S := [f] else if score = max then put(S, f) return set(S) end @ Here's a big pile of heuristics. I'm not sure I've ever needed more than the first two, but they're amusing and easy enough to write. «*»= # leafarms: prefer candidate with most arms that appear at leaf # nodes. Each original arm counted only once. # Not matching is also counted as an arm. procedure leafarms(children, f) arms := set() every n := (!children).node & *n.cs.arms > 0 do if not needs_splitting(n) then insert(arms, n.cs.arms[1].original) return *arms + if *(!children).node.cs.arms = 0 then 1 else 0 end # childarms: prefer the candidate with the fewest arms in children procedure childarms(children, f) sum := 0 every sum -:= *(!children).node.cs.arms return sum end # nomatch: if tied on leafarms and childarms, take candidate # with real leaf in preference to nomatch leaf procedure nomatch(children, f) return if *(!children).node.cs.arms = 0 then -1 else 0 end # childdisjuncts: prefer the candidate with the fewest disjuncts in children procedure childdisjuncts(children, f) sum := 0 every sum -:= *(!(!children).node.cs.arms).pattern.disjuncts return sum end # branchfactor: prefer the candidate with the fewest children procedure branchfactor(children, f) return - *children end @