40 #ifndef __GECODE_SEARCH_HH__ 41 #define __GECODE_SEARCH_HH__ 49 #if !defined(GECODE_STATIC_LIBS) && \ 50 (defined(__CYGWIN__) || defined(__MINGW32__) || defined(_MSC_VER)) 52 #ifdef GECODE_BUILD_SEARCH 53 #define GECODE_SEARCH_EXPORT __declspec( dllexport ) 55 #define GECODE_SEARCH_EXPORT __declspec( dllimport ) 60 #ifdef GECODE_GCC_HAS_CLASS_VISIBILITY 61 #define GECODE_SEARCH_EXPORT __attribute__ ((visibility("default"))) 63 #define GECODE_SEARCH_EXPORT 69 #ifndef GECODE_BUILD_SEARCH 70 #define GECODE_LIBRARY_NAME "Search" 75 namespace Gecode {
namespace Search {
78 namespace Sequential {}
89 namespace Sequential {}
109 const unsigned int c_d = 8;
111 const unsigned int a_d = 2;
119 const unsigned int d_l = 5;
134 namespace Gecode {
namespace Search {
166 namespace Gecode {
namespace Search {
179 virtual unsigned long int operator ()(
void)
const = 0;
181 virtual unsigned long int operator ++(
void) = 0;
206 rnd(
unsigned int seed,
207 unsigned long int min,
unsigned long int max,
208 unsigned long int n);
217 repeat(
Cutoff*
c,
unsigned long int n);
233 virtual unsigned long int operator ()(
void)
const;
235 virtual unsigned long int operator ++(
void);
252 virtual unsigned long int operator ()(
void)
const;
254 virtual unsigned long int operator ++(
void);
268 static const unsigned long int n_start = 63U;
270 static unsigned long int start[n_start];
272 static unsigned long int log(
unsigned long int i);
274 static unsigned long int luby(
unsigned long int i);
279 virtual unsigned long int operator ()(
void)
const;
281 virtual unsigned long int operator ++(
void);
300 virtual unsigned long int operator ()(
void)
const;
302 virtual unsigned long int operator ++(
void);
324 unsigned long int min,
unsigned long int max,
325 unsigned long int n);
327 virtual unsigned long int operator ()(
void)
const;
329 virtual unsigned long int operator ++(
void);
348 virtual unsigned long int operator ()(
void)
const;
350 virtual unsigned long int operator ++(
void);
369 virtual unsigned long int operator ()(
void)
const;
371 virtual unsigned long int operator ++(
void);
394 virtual unsigned long int operator ()(
void)
const;
396 virtual unsigned long int operator ++(
void);
405 namespace Gecode {
namespace Search {
485 namespace Gecode {
namespace Search {
514 static Stop* node(
unsigned long int l);
517 static Stop* fail(
unsigned long int l);
519 static Stop* time(
unsigned long int l);
539 unsigned long int limit(
void)
const;
541 void limit(
unsigned long int l);
562 unsigned long int limit(
void)
const;
564 void limit(
unsigned long int l);
583 unsigned long int limit(
void)
const;
585 void limit(
unsigned long int l);
596 namespace Gecode {
namespace Search {
604 virtual Space* next(
void) = 0;
606 virtual Statistics statistics(
void)
const = 0;
608 virtual bool stopped(
void)
const = 0;
610 virtual void constrain(
const Space&
b);
612 virtual void reset(
Space* s);
614 virtual NoGoods& nogoods(
void);
623 namespace Gecode {
namespace Search {
628 template<
class,
class>
630 template<
class,
template<
class>
class>
639 virtual T*
next(
void);
643 virtual bool stopped(
void)
const;
657 namespace Gecode {
namespace Search {
660 template<
class T,
class E>
661 Engine*
build(Space* s,
const Options&
opt);
663 template<
class T,
template<
class>
class E>
664 Engine*
build(Space* s,
const Options&
opt);
679 const Options& options(
void)
const;
681 bool best(
void)
const;
711 explicit SEBs(
int n);
713 SEBs(
const std::vector<SEB>&
x);
715 template<
class InputIterator>
716 SEBs(InputIterator first, InputIterator last);
744 static const bool best =
false;
816 static const bool best =
false;
854 template<
class T,
template<
class>
class E = DFS>
861 static const bool best = E<T>::best;
882 template<
class T,
template<
class>
class E>
886 template<
class T,
template<
class>
class E>
893 namespace Gecode {
namespace Search {
namespace Meta {
896 template<
class T,
template<
class>
class E>
897 Engine*
sequential(T* master,
const Search::Statistics& stat, Options&
opt);
900 template<
class T,
template<
class>
class E>
902 const Search::Statistics& stat, Options&
opt,
bool best);
904 #ifdef GECODE_HAS_THREADS 907 template<
class T,
template<
class>
class E>
908 Engine*
parallel(T* master,
const Search::Statistics& stat, Options&
opt);
911 template<
class T,
template<
class>
class E>
912 Engine*
parallel(T* master, SEBs& sebs,
913 const Search::Statistics& stat, Options&
opt,
bool best);
938 template<
class T,
template<
class>
class E = DFS>
959 static const bool best = E<T>::best;
979 template<
class T,
template<
class>
class E>
unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance) ...
double scale
Scale factor.
void build(T *s, SEBs &sebs, const Search::Options &o)
The actual build function.
Search engine implementation interface
unsigned int nogoods_limit
Depth limit for extraction of no-goods.
Limited discrepancy search engine.
unsigned long int scale
Scale factor.
Stop-object based on number of nodes
void log(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
RBS(T *s, const Search::Options &o)
Initialize engine for space s and options o.
Meta-engine performing restart-based search.
Meta engine using a portfolio of search engines.
#define GECODE_SEARCH_EXPORT
Cutoff * c1
First cutoff generator.
Argument array for primtive types.
unsigned int c_d
Create a clone after every c_d commits (commit distance)
Cutoff generator appending two cutoff generators.
static const bool best
Whether engine does best solution search.
static const bool best
Whether engine does best solution search.
A class for building search engines.
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Options opt
Stored and already expanded options.
unsigned long int l
Current limit in milliseconds.
void stop(Support::Timer &timer, std::ostream &os)
Get time since start of timer and print user friendly time information.
unsigned long int step
Step size.
Engine * build(Space *s, const Options &opt)
Build an engine of type E for a script T.
const unsigned int initial_delay
Initial delay in milliseconds for all but first worker thread.
virtual T * next(void)
Return next solution (NULL, if none exists or search has been stopped)
unsigned int slice
Size of a slice in a portfolio (in number of failures)
SEBs(void)
Allocate empty array.
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatVal c)
Post propagator for .
unsigned long int scale
Scale factor.
unsigned long int fail
Number of failed nodes in search tree.
unsigned long int nogood
Number of no-goods posted.
Support::Timer t
Time when execution should stop.
unsigned long int depth
Maximum depth of search stack.
Cutoff generator for the Luby sequence.
Base class for cutoff generators for restart-based meta engine.
Statistics & operator+=(const Statistics &s)
Increment by statistics s.
unsigned long int min
Minimum cutoff value.
virtual ~Base(void)
Destructor.
unsigned long int c
Constant.
unsigned int d_l
Discrepancy limit (for LDS)
Options expand(void) const
Expand with real number of threads.
unsigned long int n
Random values.
Statistics for execution of status
Gecode::FloatVal c(-8, 8)
Cutoff generator merging two cutoff generators.
Cutoff * cutoff
Cutoff for restart-based search.
static const bool best
Whether engine does best solution search.
double threads
Number of threads to use.
const bool b
Whether engine to be built is a best solution search engine.
Gecode::IntArgs i(4, 1, 2, 3, 4)
Cutoff generator for the random sequence.
int n
Number of negative literals for node type.
bool share_rbs
Whether to share AFC information between restarts.
Base-class for search engines.
Depth-first branch-and-bound search engine.
Statistics(void)
Initialize.
static const Options def
Default options.
const unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance) ...
unsigned long int n
How many number to take from the first.
unsigned long int cur
Current value.
Support::RandomGenerator rnd
Random number generator.
struct Gecode::@579::NNF::@61::@62 b
For binary nodes (and, or, eqv)
unsigned long int i
Iteration number.
double n
Current cutoff value.
bool clone
Whether engines create a clone when being initialized.
bool share_pbs
Whether to share AFC information among assets in a portfolio.
Template for linear congruential generators.
Search::Builder * SEB
Type for a search engine builder.
const unsigned int d_l
Default discrepancy limit for LDS.
Cutoff * c2
Second cutoff generators.
T * lds(T *s, const Search::Options &o)
Invoke limited-discrepancy search for s as root node and optionso.
virtual Statistics statistics(void) const
Return statistics.
Cutoff * c1
First cutoff generators.
Cutoff generator for linear sequence.
const double threads
Number of threads to use.
Base(Engine *e=NULL)
Constructor.
T * dfs(T *s, const Search::Options &o)
Invoke depth-first search engine for subclass T of space s with options o.
unsigned int assets
Number of assets (engines) in a portfolio.
Cutoff generator for the geometric sequence.
T * bab(T *s, const Search::Options &o)
Perform depth-first branch-and-bound search for subclass T of space s and options o...
friend Engine * build(Space *, const Options &)
Build an engine of type E for a script T.
BAB(T *s, const Search::Options &o=Search::Options::def)
Initialize engine for space s and options o.
LDS(T *s, const Search::Options &o=Search::Options::def)
Initialize engine for space s and options o.
T * pbs(T *s, const Search::Options &o)
Run a portfolio of search engines.
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Cutoff * c
Actual cutoff generator.
Cutoff generator for constant sequence.
const double base
Base for geometric restart sequence.
static const bool best
Whether engine does best solution search.
unsigned long int n
Next number in sequence.
No-goods recorded from restarts.
unsigned long int l
Node limit.
Engine * e
The actual search engine.
unsigned long int l
Failure limit.
Statistics operator+(const Statistics &s)
Return sum with s.
virtual bool stopped(void) const
Check whether engine has been stopped.
Cutoff generator that repeats a cutoff from another cutoff generator.
const unsigned int c_d
Create a clone after every c_d commits (commit distance)
Post propagator for SetVar x
unsigned long int restart
Number of restarts.
Passing search engine builder arguments.
Stop * stop
Stop object for stopping search.
Gecode toplevel namespace
unsigned long int node
Number of nodes expanded.
const unsigned int nogoods_limit
Depth limit for no-good generation during search.
Stop-object based on time
Base-class for Stop-object.
Cutoff * c2
Second cutoff generator.
PBS(T *s, const Search::Options &o=Search::Options::def)
Initialize with engines running copies of s with options o.
Base class for heap allocated objects.
const unsigned int steal_limit
Minimal number of open nodes for stealing.
T * rbs(T *s, const Search::Options &o)
Perform restart-based search.
const unsigned int slice
Size of a slice in a portfolio and scale factor for restarts(in number of failures) ...
Depth-first search engine.
Stop-object based on number of failures
Options(void)
Initialize with default values.
static const bool best
Whether engine does best solution search.
DFS(T *s, const Search::Options &o=Search::Options::def)
Initialize search engine for space s with options o.
const bool clone
Whether engines create a clone when being initialized.