searchtoy

The searchtoy is a python 3 library for solving combinatorial search problems.

It is currenty under development and its interface is not completely stable.

The searchtoy originated as a personal project, with an intent to experiment
with the characteristics of the python language while building a library that
could actually do something useful. Therefore the library can be used for solving practical combinatorial search problems, while its code can also act as a showcase for several python idioms such as generators, decorators and
metaclasses.

The searchtoy code is licensed under the
MIT License.

The code in this repository includes many well-documented examples of using
the library to solve typical combinatorial search problems. You can follow
them through to see how you can use the library to solve your own search
problems.

An overview of the searchtoy

The main classes

States

A state is a representation of the current condition of a search problem.

Classes derived from State hold all problem-specific information that may be
relevant during the search. This includes information that may be required by a
Generator for generating successor states, or by an Evaluator for computing
a state's heuristic value.

Generators

A generator is responsible for enumerating all the operations that can be
applied to a given search state. It thus determines the successor states
(or descendants) of a given search state.

Classes derived from Generator rely on the problem-specific information
stored in States in order to generate all applicable operations.

In problems where there is only a single obvious way to generate successor
states
(such as the knight's tour or
the sliding tile puzzle),
the Generator functionality can be embedded in State, as a mixin.
In other cases, different Generators can be attached to a State and be used
interchangeably.

Evaluators

An evaluation function assigns a heuristic value to each state, which is an
estimate of the cost required to reach a solution from that state.

Classes derived from Evaluator rely on the problem-specific information
stored in States in order to evaluate them. The values computed by
Evaluators are used by informed search methods in order to guide the search
towards the most promising parts of the search space.

Problems

All you need in order to define a particular Problem instance is an initial
starting state and a predicate function to recognize goal states.

Methods

A search method is a systematic procedure for generating and exploring the states
in a problem's search space, while searching for solutions.

The searchtoy provides a generic search Method with various different
components. Well-known blind and informed search methods provided
by the library are assembled from the different available components of this
generic search method. Programmatically, this is one of the most interesting
aspects of the library.

How to use searchtoy to solve a problem

When presented with a combinatorial search problem you need to solve with the
searchtoy, these are the steps involved:

1. Encapsulate the state representation in a class derived from State. Note
   that this also requires that you:

   • Implement the __str__ and __hash__ methods for the class.
   • Override the copy() method (which is not necessary but highly advisable).
   • Define the methods that modify the state and decorate them with
     @searchtoy.operator or @search.action, so that they
     can serve as operators during search.
2. • If there is only a single obvious way to generate successor states for
     a particular state representation, then
     use either ConsistentGenerator or InconsistentGenerator as mixins
     to the State subclass and implement the operations generator method.
   • If there are alternative ways to generate successor states for
     a particular state representation, then derive
     from ConsistentGenerator or InconsistentGenerator and implement
     the operations generator method for each one of the alternatives.
   • Different generators may require different state representations. Also,
     some generators may induce a search space that is tree-structured.
3. • Optionally, you can derive from the Evaluator class and implement one or
     more heuristic evaluation functions. This will allow you to employ
     informed search methods.
   • Different evaluators may require different state representations.

4. Define the Problem's initial state and goal predicate function.

5. Invoke a search method and search for solutions!

How to install searchtoy

Start by cloning this github repository or
simply download the .zip file
and extract it.

cd into the directory containing searchtoy's code and install it.

pip install .

If you like, you can install searchtoy in a virtual environment. Before installing,
create and activate the environment:

virtualenv ~/environments/searchtoy
source ~/environments/searchtoy/bin/activate

Here, ~/environments/searchtoy is the directory where the virtual environment
will be installed. You can modify this as you please. Play around and, when you 're
done, deactivate the virtual environment.

deactivate

The library will eventually be made available through the Python Package Index.