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
@