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 {
235 template<
template<
class>
class E,
class T>
240 namespace Gecode {
namespace Search {
namespace Meta {
246 namespace Gecode {
namespace Search {
271 static void*
operator new(
size_t s);
273 static void operator delete(
void*
p);
292 unsigned long int limit(
void)
const;
294 void limit(
unsigned long int l);
315 unsigned long int limit(
void)
const;
317 void limit(
unsigned long int l);
336 unsigned long int limit(
void)
const;
338 void limit(
unsigned long int l);
350 template<
template<
class>
class,
class>
friend class ::Gecode::RBS;
351 friend class ::Gecode::Search::Meta::RBS;
371 Stop* enginestop(
void)
const;
373 bool enginestopped(
void)
const;
384 namespace Gecode {
namespace Search {
394 virtual unsigned long int operator ()(
void)
const = 0;
396 virtual unsigned long int operator ++(
void) = 0;
401 constant(
unsigned long int scale=1U);
404 linear(
unsigned long int scale=1U);
409 geometric(
unsigned long int scale=1U,
double base=1.5);
412 luby(
unsigned long int scale=1U);
418 rnd(
unsigned int seed,
419 unsigned long int min,
unsigned long int max,
420 unsigned long int n);
429 repeat(
Cutoff*
c,
unsigned long int n);
431 static void*
operator new(
size_t s);
433 static void operator delete(
void*
p);
440 namespace Gecode {
namespace Search {
452 virtual bool stopped(
void)
const = 0;
469 template<
template<
class>
class,
class>
friend class ::Gecode::RBS;
583 template<
template<
class>
class E,
class T>
584 class RBS :
public EngineBase {
587 RBS(T* s,
const Search::Options& o);
614 template<
template<
class>
class E,
class T>
615 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) ...
bool stopped(void) const
Check whether engine has been stopped.
Search engine implementation interface
unsigned int nogoods_limit
Depth limit for extraction of no-goods.
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatNum c)
Post propagator for .
Search::Statistics statistics(void) const
Return statistics.
Stop-object based on number of nodes
Meta-engine performing restart-based search.
#define GECODE_SEARCH_EXPORT
Search::Engine * e
The actual search engine.
virtual ~Engine(void)
Destructor.
unsigned int c_d
Create a clone after every c_d commits (commit distance)
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.
Search::Statistics statistics(void) const
Return statistics.
const unsigned int initial_delay
Initial delay in milliseconds for all but first worker thread.
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.
Base class for cutoff generators for restart-based meta engine.
Statistics & operator+=(const Statistics &s)
Increment by statistics s.
Statistics for execution of status
Gecode::FloatVal c(-8, 8)
Cutoff * cutoff
Cutoff for restart-based search.
double threads
Number of threads to use.
int p
Number of positive literals for node type.
int n
Number of negative literals for node type.
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) ...
bool clone
Whether engines create a clone when being initialized.
virtual void reset(Space *s)=0
Reset engine to restart at space s.
~EngineBase(void)
Destructor.
virtual NoGoods & nogoods(void)=0
Return no-goods.
EngineBase(Search::Engine *e=NULL)
Constructor.
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.
T * next(void)
Return next solution (NULL, if non exists or search has been stopped)
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.
bool stopped(void) const
Check whether engine has been stopped.
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
bool stopped(void) const
Check whether engine has been stopped.
Options expand(void) const
Expand with real number of threads.
No-goods recorded from restarts.
unsigned long int l
Node limit.
virtual Space * next(void)=0
Return next solution (NULL, if none exists or search has been stopped)
T * next(void)
Return next solution (NULL, if none exists or search has been stopped)
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.
Search::Statistics statistics(void) const
Return statistics.
NoGoods & nogoods(void)
Return no-goods.
const unsigned int c_d
Create a clone after every c_d commits (commit distance)
unsigned long int restart
Number of restarts.
Base-class for search engines.
Stop * stop
Stop object for stopping search.
virtual Statistics statistics(void) const =0
Return statistics.
Gecode toplevel namespace
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.
NoGoods & nogoods(void)
Return no-goods.
T * next(void)
Return next better solution (NULL, if none exists or search has been stopped)
Stop-object based on time
Base-class for Stop-object.
const unsigned int steal_limit
Minimal number of open nodes for stealing.
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.
virtual bool stopped(void) const =0
Check whether engine has been stopped.