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 {}
97 const unsigned int c_d = 8;
99 const unsigned int a_d = 2;
112 namespace Gecode {
namespace Search {
123 UninitializedCutoff(
const char*
l);
130 namespace Gecode {
namespace Search {
162 namespace Gecode {
namespace Search {
175 virtual unsigned long int operator ()(
void)
const = 0;
177 virtual unsigned long int operator ++(
void) = 0;
183 static void*
operator new(
size_t s);
186 static void operator delete(
void*
p);
192 constant(
unsigned long int scale=1U);
195 linear(
unsigned long int scale=1U);
200 geometric(
unsigned long int scale=1U,
double base=1.5);
203 luby(
unsigned long int scale=1U);
209 rnd(
unsigned int seed,
210 unsigned long int min,
unsigned long int max,
211 unsigned long int n);
220 repeat(
Cutoff*
c,
unsigned long int n);
236 virtual unsigned long int operator ()(
void)
const;
238 virtual unsigned long int operator ++(
void);
255 virtual unsigned long int operator ()(
void)
const;
257 virtual unsigned long int operator ++(
void);
271 static const unsigned long int n_start = 63U;
273 static unsigned long int start[n_start];
275 static unsigned long int log(
unsigned long int i);
277 static unsigned long int luby(
unsigned long int i);
282 virtual unsigned long int operator ()(
void)
const;
284 virtual unsigned long int operator ++(
void);
303 virtual unsigned long int operator ()(
void)
const;
305 virtual unsigned long int operator ++(
void);
327 unsigned long int min,
unsigned long int max,
328 unsigned long int n);
330 virtual unsigned long int operator ()(
void)
const;
332 virtual unsigned long int operator ++(
void);
351 virtual unsigned long int operator ()(
void)
const;
353 virtual unsigned long int operator ++(
void);
372 virtual unsigned long int operator ()(
void)
const;
374 virtual unsigned long int operator ++(
void);
397 virtual unsigned long int operator ()(
void)
const;
399 virtual unsigned long int operator ++(
void);
408 namespace Gecode {
namespace Search {
478 namespace Gecode {
namespace Search {
507 static void*
operator new(
size_t s);
510 static void operator delete(
void*
p);
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 reset(
Space* s);
612 virtual NoGoods& nogoods(
void);
617 static void*
operator new(
size_t s);
620 static void operator delete(
void*
p);
630 template<
template<
class>
class E,
class T>
635 namespace Gecode {
namespace Search {
640 template<
template<
class>
class,
class>
friend class ::Gecode::RBS;
648 virtual T*
next(
void);
652 virtual bool stopped(
void)
const;
659 static void*
operator new(
size_t s);
662 static void operator delete(
void*
p);
754 template<
template<
class>
class E,
class T>
755 class RBS :
public Search::EngineBase<T> {
756 using Search::EngineBase<T>::e;
759 RBS(T* s,
const Search::Options& o);
780 template<
template<
class>
class E,
class T>
781 T*
rbs(T* s,
const Search::Options& o);
unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance) ...
double scale
Scale factor.
Search engine implementation interface
unsigned int nogoods_limit
Depth limit for extraction of no-goods.
unsigned long int scale
Scale factor.
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatNum c)
Post propagator for .
Stop-object based on number of nodes
void log(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
Meta-engine performing restart-based search.
#define GECODE_SEARCH_EXPORT
Cutoff * c1
First cutoff generator.
unsigned int c_d
Create a clone after every c_d commits (commit distance)
Cutoff generator appending two cutoff generators.
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
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.
const unsigned int initial_delay
Initial delay in milliseconds for all but first worker thread.
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.
unsigned long int c
Constant.
virtual ~EngineBase(void)
Destructor.
unsigned long int n
Random values.
Statistics for execution of status
virtual T * next(void)
Return next solution (NULL, if none exists or search has been stopped)
Gecode::FloatVal c(-8, 8)
Cutoff generator merging two cutoff generators.
Cutoff * cutoff
Cutoff for restart-based search.
double threads
Number of threads to use.
int p
Number of positive literals for node type.
Gecode::IntArgs i(4, 1, 2, 3, 4)
Cutoff generator for the random sequence.
int n
Number of negative literals for node type.
virtual Statistics statistics(void) const
Return statistics.
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) ...
Base-class for search engines.
unsigned long int n
How many number to take from the first.
unsigned long int cur
Current value.
Support::RandomGenerator rnd
Random number generator.
unsigned long int i
Iteration number.
double n
Current cutoff value.
Engine * e
The actual search engine.
bool clone
Whether engines create a clone when being initialized.
Template for linear congruential generators.
Cutoff * c2
Second cutoff generators.
Cutoff * c1
First cutoff generators.
Cutoff generator for linear sequence.
const double threads
Number of threads to use.
T * dfs(T *s, const Search::Options &o)
Invoke depth-first search engine for subclass T of space s with options o.
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...
BAB(T *s, const Search::Options &o=Search::Options::def)
Initialize engine for space s and options o.
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Cutoff * c
Actual cutoff generator.
Cutoff generator for constant sequence.
unsigned long int n
Next number in sequence.
Options expand(void) const
Expand with real number of threads.
No-goods recorded from restarts.
unsigned long int l
Node limit.
unsigned long int l
Failure limit.
Statistics operator+(const Statistics &s)
Return sum with s.
RBS(T *s, const Search::Options &o)
Initialize engine for space s and options o.
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)
unsigned long int restart
Number of restarts.
Stop * stop
Stop object for stopping search.
unsigned long int node
Number of nodes expanded.
#define GECODE_VTABLE_EXPORT
const unsigned int nogoods_limit
Depth limit for no-good generation during search.
virtual bool stopped(void) const
Check whether engine has been stopped.
Stop-object based on time
Base-class for Stop-object.
Cutoff * c2
Second cutoff generator.
virtual NoGoods & nogoods(void)
Return no-goods (the no-goods are empty)
const unsigned int steal_limit
Minimal number of open nodes for stealing.
EngineBase(Engine *e=NULL)
Constructor.
T * rbs(T *s, const Search::Options &o)
Perform restart-based search.
Depth-first search engine.
Stop-object based on number of failures
Options(void)
Initialize with default values.
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.