Module Sasacore.LocalSearch

A generic module to implement local searches https://en.wikipedia.org/wiki/Local_search_(optimization)

type ('n, 'tv, 'v) t = {
  1. init : 'n * 'tv * 'v;
  2. succ : 'n -> 'n list;
  3. is_goal : 'n -> bool;
  4. stop : 'n -> 'n -> bool;
  5. cut : 'n -> 'n -> bool;
  6. push : 'tv -> 'n -> 'tv;
  7. pop : 'tv -> ('n * 'tv) option;
  8. visiting : 'n -> 'v -> 'v;
  9. visited : 'n -> 'v -> bool;
}

Parameterized by node, nodes to visit later, already visited (+ to visit) nodes

  • 'tv: nodes to visit late can be implemented by lists, or priority queues
  • 'v: visited nodes can be implemented by lists, or sets
type 'n sol =
  1. | Stopped
  2. | NoMore
  3. | Sol of 'n * 'n moresol
and 'n moresol = 'n option -> 'n sol
val run : ('n, 'tv, 'v) t -> 'n moresol

explore g the graph induced by g.succ until either

  • pop tv~>None, then it returns NoMore
  • stop 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.

val stat : Stdlib.out_channel -> unit