Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040 #ifndef __GECODE_SEARCH_HH__
00041 #define __GECODE_SEARCH_HH__
00042
00043 #include <gecode/kernel.hh>
00044
00045
00046
00047
00048
00049 #if !defined(GECODE_STATIC_LIBS) && \
00050 (defined(__CYGWIN__) || defined(__MINGW32__) || defined(_MSC_VER))
00051
00052 #ifdef GECODE_BUILD_SEARCH
00053 #define GECODE_SEARCH_EXPORT __declspec( dllexport )
00054 #else
00055 #define GECODE_SEARCH_EXPORT __declspec( dllimport )
00056 #endif
00057
00058 #else
00059
00060 #ifdef GECODE_GCC_HAS_CLASS_VISIBILITY
00061 #define GECODE_SEARCH_EXPORT __attribute__ ((visibility("default")))
00062 #else
00063 #define GECODE_SEARCH_EXPORT
00064 #endif
00065
00066 #endif
00067
00068
00069 #ifndef GECODE_BUILD_SEARCH
00070 #define GECODE_LIBRARY_NAME "Search"
00071 #include <gecode/support/auto-link.hpp>
00072 #endif
00073
00074
00075 namespace Gecode { namespace Search {
00076
00078 namespace Sequential {}
00079
00081 namespace Parallel {}
00082
00084 namespace Meta {}
00085
00091 namespace Config {
00093 const bool clone = true;
00095 const double threads = 1.0;
00097 const unsigned int c_d = 8;
00099 const unsigned int a_d = 2;
00100
00102 const unsigned int steal_limit = 3;
00104 const unsigned int initial_delay = 5;
00105
00107 const unsigned int nogoods_limit = 128;
00108 }
00109
00110 }}
00111
00112 namespace Gecode { namespace Search {
00113
00119
00120 class GECODE_VTABLE_EXPORT UninitializedCutoff : public Exception {
00121 public:
00123 UninitializedCutoff(const char* l);
00124 };
00126 }}
00127
00128 #include <gecode/search/exception.hpp>
00129
00130 namespace Gecode { namespace Search {
00131
00136 class Statistics : public StatusStatistics {
00137 public:
00139 unsigned long int fail;
00141 unsigned long int node;
00143 unsigned long int depth;
00145 unsigned long int restart;
00147 unsigned long int nogood;
00149 Statistics(void);
00151 void reset(void);
00153 Statistics operator +(const Statistics& s);
00155 Statistics& operator +=(const Statistics& s);
00156 };
00157
00158 }}
00159
00160 #include <gecode/search/statistics.hpp>
00161
00162 namespace Gecode { namespace Search {
00163
00164 class Stop;
00165 class Cutoff;
00166
00204 class Options {
00205 public:
00207 bool clone;
00209 double threads;
00211 unsigned int c_d;
00213 unsigned int a_d;
00215 unsigned int nogoods_limit;
00217 Stop* stop;
00219 Cutoff* cutoff;
00221 GECODE_SEARCH_EXPORT static const Options def;
00223 Options(void);
00225 GECODE_SEARCH_EXPORT Options
00226 expand(void) const;
00227 };
00228
00229 }}
00230
00231 #include <gecode/search/options.hpp>
00232
00233 namespace Gecode {
00234
00235 template<template<class> class E, class T>
00236 class RBS;
00237
00238 }
00239
00240 namespace Gecode { namespace Search { namespace Meta {
00241
00242 class RBS;
00243
00244 }}}
00245
00246 namespace Gecode { namespace Search {
00247
00262 class GECODE_SEARCH_EXPORT Stop {
00263 public:
00265 Stop(void);
00267 virtual bool stop(const Statistics& s, const Options& o) = 0;
00269 virtual ~Stop(void);
00271 static void* operator new(size_t s);
00273 static void operator delete(void* p);
00274 };
00275
00284 class GECODE_SEARCH_EXPORT NodeStop : public Stop {
00285 protected:
00287 unsigned long int l;
00288 public:
00290 NodeStop(unsigned long int l);
00292 unsigned long int limit(void) const;
00294 void limit(unsigned long int l);
00296 virtual bool stop(const Statistics& s, const Options& o);
00297 };
00298
00307 class GECODE_SEARCH_EXPORT FailStop : public Stop {
00308 protected:
00310 unsigned long int l;
00311 public:
00313 FailStop(unsigned long int l);
00315 unsigned long int limit(void) const;
00317 void limit(unsigned long int l);
00319 virtual bool stop(const Statistics& s, const Options& o);
00320 };
00321
00326 class GECODE_SEARCH_EXPORT TimeStop : public Stop {
00327 protected:
00329 Support::Timer t;
00331 unsigned long int l;
00332 public:
00334 TimeStop(unsigned long int l);
00336 unsigned long int limit(void) const;
00338 void limit(unsigned long int l);
00340 void reset(void);
00342 virtual bool stop(const Statistics& s, const Options& o);
00343 };
00344
00349 class GECODE_SEARCH_EXPORT MetaStop : public Stop {
00350 template<template<class>class,class> friend class ::Gecode::RBS;
00351 friend class ::Gecode::Search::Meta::RBS;
00352 private:
00354 FailStop* e_stop;
00356 Stop* m_stop;
00358 bool e_stopped;
00360 Statistics m_stat;
00361 public:
00363 MetaStop(Stop* s);
00365 virtual bool stop(const Statistics& s, const Options& o);
00367 void limit(const Search::Statistics& s, unsigned long int l);
00369 void update(const Search::Statistics& s);
00371 Stop* enginestop(void) const;
00373 bool enginestopped(void) const;
00375 Statistics metastatistics(void) const;
00377 ~MetaStop(void);
00378 };
00379
00380 }}
00381
00382 #include <gecode/search/stop.hpp>
00383
00384 namespace Gecode { namespace Search {
00385
00389 class GECODE_SEARCH_EXPORT Cutoff {
00390 public:
00392 Cutoff(void);
00394 virtual unsigned long int operator ()(void) = 0;
00396 virtual ~Cutoff(void);
00398 static Cutoff*
00399 constant(unsigned long int scale=1U);
00401 static Cutoff*
00402 linear(unsigned long int scale=1U);
00406 static Cutoff*
00407 geometric(unsigned long int scale=1U, double base=1.5);
00409 static Cutoff*
00410 luby(unsigned long int scale=1U);
00415 static Cutoff*
00416 rnd(unsigned int seed,
00417 unsigned long int min, unsigned long int max,
00418 unsigned long int n);
00420 static Cutoff*
00421 append(Cutoff* c1, unsigned long int n, Cutoff* c2);
00423 static Cutoff*
00424 repeat(Cutoff* c, unsigned long int n);
00426 static void* operator new(size_t s);
00428 static void operator delete(void* p);
00429 };
00430
00431 }}
00432
00433 #include <gecode/search/cutoff.hpp>
00434
00435 namespace Gecode { namespace Search {
00436
00440 class Engine {
00441 public:
00443 virtual Space* next(void) = 0;
00445 virtual Statistics statistics(void) const = 0;
00447 virtual bool stopped(void) const = 0;
00449 virtual void reset(Space* s) = 0;
00451 virtual NoGoods& nogoods(void) = 0;
00453 virtual ~Engine(void) {}
00454 };
00455
00456 }}
00457
00458 namespace Gecode {
00459
00463 class EngineBase {
00464 template<template<class>class,class> friend class ::Gecode::RBS;
00465 protected:
00467 Search::Engine* e;
00469 ~EngineBase(void);
00471 EngineBase(Search::Engine* e = NULL);
00472 };
00473
00474 }
00475
00476 #include <gecode/search/engine-base.hpp>
00477
00478 namespace Gecode {
00479
00480
00488 template<class T>
00489 class DFS : public EngineBase {
00490 public:
00492 DFS(T* s, const Search::Options& o=Search::Options::def);
00494 T* next(void);
00496 Search::Statistics statistics(void) const;
00498 bool stopped(void) const;
00500 NoGoods& nogoods(void);
00501 };
00502
00504 template<class T>
00505 T* dfs(T* s, const Search::Options& o=Search::Options::def);
00506
00507 }
00508
00509 #include <gecode/search/dfs.hpp>
00510
00511 namespace Gecode {
00512
00524 template<class T>
00525 class BAB : public EngineBase {
00526 public:
00528 BAB(T* s, const Search::Options& o=Search::Options::def);
00530 T* next(void);
00532 Search::Statistics statistics(void) const;
00534 bool stopped(void) const;
00536 NoGoods& nogoods(void);
00537 };
00538
00551 template<class T>
00552 T* bab(T* s, const Search::Options& o=Search::Options::def);
00553
00554 }
00555
00556 #include <gecode/search/bab.hpp>
00557
00558 namespace Gecode {
00559
00578 template<template<class> class E, class T>
00579 class RBS : public EngineBase {
00580 public:
00582 RBS(T* s, const Search::Options& o);
00584 T* next(void);
00586 Search::Statistics statistics(void) const;
00588 bool stopped(void) const;
00589 };
00590
00609 template<template<class> class E, class T>
00610 T* rbs(T* s, const Search::Options& o);
00611
00612 }
00613
00614 #include <gecode/search/rbs.hpp>
00615
00616 #endif
00617
00618