package knights_tour

  1. Overview
  2. Docs
Solves the 'Knights Tour' and various 'Poyomino' puzzles

Install 

dune-project
 Dependency

github.com Readme Edit opam file Versions (6)

Authors

  1. K
    Kris De Volder

Maintainers

  1. K
    kris.de.volder@gmail.com

Sources

knights_tour-0.0.6.tbz
sha256=770624ae4e35d5a58188a1f25e16730d186df8bc4397827fe9a798ea5ca574e3
sha512=b6c7b2473ddf321afaac6b668f9c6820fb8cc872abc494b69edfdff4101c6b660645837b04801e2917c38dd9f19f79bb0a7b029d59a58ddf1e3a235659bab099

doc/knights_tour.searchspace/Stochastic_estimator/index.html

Module Stochastic_estimatorSource

Interface for stochastic estimation functions

Sourcetype decision = {
  1. chosen : int;
    (*

    A number between 0 inclusive and choices exclusive, indicating which choice was made

    *)
  2. choices : int;
    (*

    A number >= 2 indicating the number of available choices at a decision point.

    *)
}

a decision represents a choice that has been made at a decision point

Sourcetype rng = int -> int

A rng is a function that accepts a positive integer as an argument and returns a random integer between 0 (inclusive) and that integer (exclusive)

Sourceval random_walk : rng -> 'a Searchspace.t -> decision List.t * 'a option

random_walk searchspace walks a random path in the search space. Every time a decision point is reached, a random choice is made among the available options. The decisions are recorded and returned along with the final result.

Sourcetype 'a child_selector

Selector functions for choosing among children at a fork.

Sourceval uniform_selector : 'a child_selector

Uses a uniform random choice among available children.

Sourceval undersampled_selector : 'a child_selector

Prefers to select children that have been sampled less often.

Sourceval weighted_selector : 'a child_selector

Prefers to select children that have a higher number of descendants.

Sourcetype estimates = {
  1. nodes : float;
    (*

    The estimated number of nodes in the search space.

    *)
  2. fails : float;
    (*

    The estimated number of leaf nodes in the search space that represent failures.

    *)
  3. solutions : float;
    (*

    The estimated number of leaf nodes in the search space that represent solutions.

    *)
  4. materialized_nodes : int;
    (*

    The number of nodes that were actually materialized during the estimation process.

    *)
}
Sourceval estimate : ?selector:'a child_selector -> int -> 'a Searchspace.t -> estimates

estimate n searchspace performs n random walks in the given search space and uses the results to produce an estimate of the total number of nodes, fails and solutions in the search space. The estimate is returned as a record of type estimates. The number of materialized nodes is also reported.

The optional selector argument can be used to influence how choices are made at decision points. By default, the undersampled_selector is used. Other strategies are available in this module.

Sourcetype stats = {
  1. nodes : int;
    (*

    The exact number of nodes in the search space.

    *)
  2. forks : int;
    (*

    The exact number of fork nodes in the search space.

    *)
  3. fails : int;
    (*

    The exact number of leaf nodes in the search space that represent failures.

    *)
  4. solutions : int;
    (*

    The exact number of leaf nodes in the search space that represent solutions.

    *)
}
Sourceval calculate_true_values : 'a Searchspace.t -> stats

calculate_true_values searchspace fully explores the given search space and returns the exact counts of nodes, fails and solutions as an estimates record.

This function is useful for validating the accuracy of estimates produced by the estimate function. It should only be used on small search spaces where a full exploration is feasible.

Sourcetype 'a t

An incremental estimator for a search space.

Sourceval create : ?selector:'a child_selector -> 'a Searchspace.t -> 'a t

create ?selector searchspace creates a new incremental estimator for the given search space, optionally using a custom selector.

Sourceval sample : int -> 'a t -> unit

sample n est performs n additional samples, updating the estimator's statistics.

Sourceval estimates : 'a t -> estimates

estimates est returns the current estimates from the estimator.