Generated on Thu Apr 11 13:59:33 2019 for Gecode by doxygen 1.6.3

Search engines
[Programming models]

Classes

class  Gecode::Search::Statistics
 Search engine statistics More...
class  Gecode::Search::Cutoff
 Base class for cutoff generators for restart-based meta engine. More...
class  Gecode::Search::CutoffConstant
 Cutoff generator for constant sequence. More...
class  Gecode::Search::CutoffLinear
 Cutoff generator for linear sequence. More...
class  Gecode::Search::CutoffLuby
 Cutoff generator for the Luby sequence. More...
class  Gecode::Search::CutoffGeometric
 Cutoff generator for the geometric sequence. More...
class  Gecode::Search::CutoffRandom
 Cutoff generator for the random sequence. More...
class  Gecode::Search::CutoffAppend
 Cutoff generator appending two cutoff generators. More...
class  Gecode::Search::CutoffMerge
 Cutoff generator merging two cutoff generators. More...
class  Gecode::Search::CutoffRepeat
 Cutoff generator that repeats a cutoff from another cutoff generator. More...
class  Gecode::Search::Options
 Search engine options More...
class  Gecode::DFS< T >
 Depth-first search engine. More...
class  Gecode::BAB< T >
 Depth-first branch-and-bound search engine. More...
class  Gecode::LDS< T >
 Limited discrepancy search engine. More...
class  Gecode::RBS< T, E >
 Meta-engine performing restart-based search. More...
class  Gecode::PBS< T, E >
 Meta engine using a portfolio of search engines. More...

Namespaces

namespace  Gecode::Search::Config
 

Search configuration


Modules

 Stop-objects for stopping search

Functions

template<class T >
T * Gecode::bab (T *s, const Search::Options &o=Search::Options::def)
 Perform depth-first branch-and-bound search for subclass T of space s and options o.
template<class T >
T * Gecode::lds (T *s, const Search::Options &o=Search::Options::def)
 Invoke limited-discrepancy search for s as root node and optionso.
template<class T , template< class > class E>
T * Gecode::rbs (T *s, const Search::Options &o)
 Perform restart-based search.
template<class T , template< class > class E>
T * Gecode::pbs (T *s, const Search::Options &o=Search::Options::def)
 Run a portfolio of search engines.

Detailed Description

Defines search engines. All search engines (but Gecode::LDS, where it is not needed) support recomputation. The behaviour of recomputation is controlled by a passing a search option object (see the class Gecode::Search::Options).

Requires

 #include <gecode/search.hh> 

Function Documentation

template<class T >
T * Gecode::bab ( T *  s,
const Search::Options &  o = Search::Options::def 
) [inline]

Perform depth-first branch-and-bound search for subclass T of space s and options o.

Additionally, s must implement a member function

 virtual void constrain(const T& t) 

Whenever exploration requires to add a constraint to the space c currently being explored, the engine executes c.constrain(t) where t is the so-far best solution.

template<class T >
T * Gecode::lds ( T *  s,
const Search::Options &  o 
) [inline]

Invoke limited-discrepancy search for s as root node and optionso.

template<class T , template< class > class E>
T * Gecode::rbs ( T *  s,
const Search::Options &  o 
) [inline]

Perform restart-based search.

The engine uses the Cutoff sequence supplied in the options o to periodically restart the search of engine E.

The class T can implement member functions

 virtual bool master(const MetaInfo& mi) 

and

 virtual bool slave(const MetaInfo& mi) 

Whenever exploration restarts or a solution is found, the engine executes the functions on the master and slave space. For more details, consult "Modeling and Programming with Gecode".

template<class T , template< class > class E>
T * Gecode::pbs ( T *  s,
const Search::Options &  o = Search::Options::def 
) [inline]

Run a portfolio of search engines.

The engine will run a portfolio with a number of assets as defined by the options o. The engine supports parallel execution of assets by using the number of threads as defined by the options.

The class T can implement member functions

 virtual bool master(const MetaInfo& mi) 

and

 virtual bool slave(const MetaInfo& mi) 

When the assets are created, these functions are executed. For more details, consult "Modeling and Programming with Gecode".