Sasacore.LocalSearch
A generic module to implement local searches https://en.wikipedia.org/wiki/Local_search_(optimization)
type ('n, 'tv, 'v) t = {
init : 'n * 'tv * 'v;
succ : 'n -> 'n list;
is_goal : 'n -> bool;
stop : 'n -> 'n -> bool;
cut : 'n -> 'n -> bool;
push : 'tv -> 'n -> 'tv;
pop : 'tv -> ('n * 'tv) option;
visiting : 'n -> 'v -> 'v;
visited : 'n -> 'v -> bool;
}
Parameterized by node, nodes to visit later, already visited (+ to visit) nodes
and 'n moresol = 'n option -> 'n sol
explore g
the graph induced by g.succ
until either
pop tv
~>None, then it returns NoMorestop pre_s s
~> true and is_goal s~>false, then it returns Stopped
is_goal s
~>true, then it returns Sol(sol, cont)
When a valid node (a.k.a., a solution) is found, run
returns it plus a continuation to carry on the search.
The optional argument of 'n moresol
ought to contain a previously obtained solution (i.e., a node n for which is_goal n=true
) that can be used by cut
to cut branches.
nb: no cost function is required. But of course, the push
or the cut
functions might use one.