search.hh
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 {
00076
00078 namespace Search {
00079
00085 namespace Config {
00087 const bool clone = true;
00089 const double threads = 1.0;
00091 const unsigned int c_d = 8;
00093 const unsigned int a_d = 2;
00095 const unsigned int d = 5;
00096
00098 const unsigned int steal_limit = 3;
00100 const unsigned int initial_delay = 5;
00101 }
00102
00107 class Statistics : public StatusStatistics {
00108 public:
00110 unsigned long int fail;
00112 unsigned long int node;
00114 unsigned long int depth;
00116 size_t memory;
00118 Statistics(void);
00120 void reset(void);
00122 Statistics operator +(const Statistics& s);
00124 Statistics& operator +=(const Statistics& s);
00125 };
00126
00127 class Stop;
00128
00166 class Options {
00167 public:
00169 bool clone;
00171 double threads;
00173 unsigned int c_d;
00175 unsigned int a_d;
00177 unsigned int d;
00179 Stop* stop;
00181 GECODE_SEARCH_EXPORT static const Options def;
00183 Options(void);
00185 GECODE_SEARCH_EXPORT Options
00186 expand(void) const;
00187 };
00188
00203 class GECODE_SEARCH_EXPORT Stop {
00204 public:
00206 Stop(void);
00208 virtual bool stop(const Statistics& s, const Options& o) = 0;
00210 virtual ~Stop(void);
00211 };
00212
00218 class GECODE_SEARCH_EXPORT MemoryStop : public Stop {
00219 protected:
00221 size_t l;
00222 public:
00224 MemoryStop(size_t l);
00226 size_t limit(void) const;
00228 void limit(size_t l);
00230 virtual bool stop(const Statistics& s, const Options& o);
00231 };
00232
00241 class GECODE_SEARCH_EXPORT NodeStop : public Stop {
00242 protected:
00244 unsigned long int l;
00245 public:
00247 NodeStop(unsigned long int l);
00249 unsigned long int limit(void) const;
00251 void limit(unsigned long int l);
00253 virtual bool stop(const Statistics& s, const Options& o);
00254 };
00255
00264 class GECODE_SEARCH_EXPORT FailStop : public Stop {
00265 protected:
00267 unsigned long int l;
00268 public:
00270 FailStop(unsigned long int l);
00272 unsigned long int limit(void) const;
00274 void limit(unsigned long int l);
00276 virtual bool stop(const Statistics& s, const Options& o);
00277 };
00278
00283 class GECODE_SEARCH_EXPORT TimeStop : public Stop {
00284 protected:
00286 Support::Timer t;
00288 unsigned long int l;
00289 public:
00291 TimeStop(unsigned long int l);
00293 unsigned long int limit(void) const;
00295 void limit(unsigned long int l);
00297 void reset(void);
00299 virtual bool stop(const Statistics& s, const Options& o);
00300 };
00301
00302
00306 class Engine {
00307 public:
00309 virtual Space* next(void) = 0;
00311 virtual Search::Statistics statistics(void) const = 0;
00313 virtual bool stopped(void) const = 0;
00315 virtual ~Engine(void) {}
00316 };
00317
00319 namespace Sequential {}
00320
00322 namespace Parallel {}
00323
00324 }
00325
00326 }
00327
00328 #include <gecode/search/statistics.hpp>
00329 #include <gecode/search/stop.hpp>
00330 #include <gecode/search/options.hpp>
00331
00332 namespace Gecode {
00333
00341 template<class T>
00342 class DFS {
00343 private:
00345 Search::Engine* e;
00346 public:
00348 DFS(T* s, const Search::Options& o=Search::Options::def);
00350 T* next(void);
00352 Search::Statistics statistics(void) const;
00354 bool stopped(void) const;
00356 ~DFS(void);
00357 };
00358
00360 template<class T>
00361 T* dfs(T* s, const Search::Options& o=Search::Options::def);
00362
00363
00364
00376 template<class T>
00377 class BAB {
00378 private:
00380 Search::Engine* e;
00381 public:
00383 BAB(T* s, const Search::Options& o=Search::Options::def);
00385 T* next(void);
00387 Search::Statistics statistics(void) const;
00389 bool stopped(void) const;
00391 ~BAB(void);
00392 };
00393
00406 template<class T>
00407 T* bab(T* s, const Search::Options& o=Search::Options::def);
00408
00409
00410
00422 template<class T>
00423 class Restart {
00424 private:
00426 Search::Engine* e;
00427 public:
00429 Restart(T* s, const Search::Options& o=Search::Options::def);
00431 T* next(void);
00433 Search::Statistics statistics(void) const;
00435 bool stopped(void) const;
00437 ~Restart(void);
00438 };
00439
00451 template<class T>
00452 T* restart(T* s, const Search::Options& o=Search::Options::def);
00453
00454
00455
00460 template<class T>
00461 class LDS {
00462 private:
00464 Search::Engine* e;
00465 public:
00467 LDS(T* s, const Search::Options& o=Search::Options::def);
00469 T* next(void);
00471 Search::Statistics statistics(void) const;
00473 bool stopped(void) const;
00475 ~LDS(void);
00476 };
00477
00482 template<class T>
00483 T* lds(T* s, const Search::Options& o=Search::Options::def);
00484
00485 }
00486
00487 #include <gecode/search/dfs.hpp>
00488 #include <gecode/search/bab.hpp>
00489 #include <gecode/search/restart.hpp>
00490 #include <gecode/search/lds.hpp>
00491
00492 #endif
00493
00494