search.hh (Revision: 2551)
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 #ifndef __GECODE_SEARCH_HH__
00025 #define __GECODE_SEARCH_HH__
00026
00027 #include "./kernel.hh"
00028
00029
00030
00031
00032
00033
00034 #if !defined(GECODE_STATIC_LIBS) && \
00035 (defined(__CYGWIN__) || defined(__MINGW32__) || defined(_MSC_VER))
00036
00037 #ifdef GECODE_BUILD_SEARCH
00038 #define GECODE_SEARCH_EXPORT __declspec( dllexport )
00039 #else
00040 #define GECODE_SEARCH_EXPORT __declspec( dllimport )
00041 #endif
00042
00043 #else
00044
00045 #define GECODE_SEARCH_EXPORT
00046
00047 #endif
00048
00049 #include "support/dynamic-stack.hh"
00050
00051 namespace Gecode {
00052
00054 namespace Search {
00055
00061 namespace Config {
00063 const unsigned int c_d = 5;
00065 const unsigned int a_d = 2;
00066 }
00067
00072 class Statistics {
00073 public:
00075 unsigned long int propagate;
00077 unsigned long int fail;
00079 unsigned long int clone;
00081 unsigned long int commit;
00083 size_t memory;
00085 Statistics(void);
00086 };
00087
00088
00092 class FullStatistics : public Statistics {
00093 public:
00095 size_t mem_space;
00097 size_t mem_cur;
00099 size_t mem_total;
00101 FullStatistics(size_t sz);
00103 void push(const Space* s);
00105 void push(const Space* s, const BranchingDesc* d);
00107 void pop(const Space* s);
00109 void pop(const Space* s, const BranchingDesc* d);
00111 void current(const Space* s);
00113 void reset(const Space* s);
00114 };
00115
00116
00120 class PlainEngine : public FullStatistics {
00121 public:
00123 PlainEngine(size_t sz);
00125 GECODE_SEARCH_EXPORT
00126 virtual ~PlainEngine(void);
00128 virtual void reset(Space* s) = 0;
00130 virtual Space* explore(void) = 0;
00132 virtual size_t stacksize(void) const = 0;
00134 static void* operator new(size_t);
00136 static void operator delete(void*,size_t);
00137 };
00138
00139
00140
00149 class GECODE_SEARCH_EXPORT DFS {
00150 protected:
00152 PlainEngine* e;
00153 public:
00161 DFS(Space* s, unsigned int c_d, unsigned int a_d, size_t sz);
00163 ~DFS(void);
00165 Statistics statistics(void) const;
00167 Space* next(void);
00168 };
00169
00170 }
00171
00179 template <class T>
00180 class DFS : public Search::DFS {
00181 public:
00188 DFS(T* s,
00189 unsigned int c_d=Search::Config::c_d,
00190 unsigned int a_d=Search::Config::a_d);
00192 T* next(void);
00193 };
00194
00202 template <class T>
00203 T* dfs(T* s,
00204 unsigned int c_d=Search::Config::c_d,
00205 unsigned int a_d=Search::Config::a_d);
00206
00207
00208
00209 namespace Search {
00210
00215 class ProbeEngine : public FullStatistics {
00216 protected:
00218 class Node {
00219 private:
00221 Space* _space;
00223 unsigned int _alt;
00224 public:
00226 Node(Space* s, unsigned int a);
00228 Space* space(void) const;
00230 void space(Space* s);
00232 unsigned int alt(void) const;
00234 void alt(unsigned int a);
00235 };
00237 Support::DynamicStack<Node> ds;
00239 Space* cur;
00241 unsigned int d;
00242 public:
00244 ProbeEngine(size_t s);
00246 void init(Space* s, unsigned int d);
00248 void reset(Space* s, unsigned int d);
00250 size_t stacksize(void) const;
00252 ~ProbeEngine(void);
00254 Space* explore(void);
00255 };
00256
00260 class LDS {
00261 protected:
00262 Space* root;
00263 unsigned int d_cur;
00264 unsigned int d_max;
00265 bool no_solution;
00266 ProbeEngine e;
00267 public:
00273 GECODE_SEARCH_EXPORT LDS(Space* s, unsigned int d, size_t sz);
00275 GECODE_SEARCH_EXPORT ~LDS(void);
00277 GECODE_SEARCH_EXPORT Statistics statistics(void) const;
00279 GECODE_SEARCH_EXPORT Space* next(void);
00280 };
00281
00282 }
00283
00288 template <class T>
00289 class LDS : public Search::LDS {
00290 public:
00295 LDS(T* s, unsigned int d);
00297 T* next(void);
00298 };
00299
00306 template <class T>
00307 T* lds(T* s,unsigned int d);
00308
00309
00310
00311
00312
00313
00314
00315
00316
00317
00318 namespace Search {
00319
00323 class BabEngine : public FullStatistics {
00324 public:
00326 BabEngine(size_t sz);
00328 GECODE_SEARCH_EXPORT virtual ~BabEngine(void);
00339 virtual bool explore(Space*& s1, Space*& s2) = 0;
00341 virtual size_t stacksize(void) const = 0;
00343 static void* operator new(size_t);
00345 static void operator delete(void*,size_t);
00346 };
00347
00357 class GECODE_SEARCH_EXPORT BAB {
00358 protected:
00360 BabEngine* e;
00361 public:
00369 BAB(Space* s, unsigned int c_d, unsigned int a_d, size_t sz);
00371 ~BAB(void);
00373 Statistics statistics(void) const;
00374 };
00375
00376 }
00377
00382 template <class T>
00383 class BAB : public Search::BAB {
00384 public:
00397 BAB(T* s,
00398 unsigned int c_d=Search::Config::c_d,
00399 unsigned int a_d=Search::Config::a_d);
00401 T* next(void);
00402 };
00403
00417 template <class T>
00418 T* bab(T* s,
00419 unsigned int c_d=Search::Config::c_d,
00420 unsigned int a_d=Search::Config::a_d);
00421
00422
00423
00428 template <class T>
00429 class Restart : public DFS<T> {
00430 protected:
00432 Space* root;
00434 Space* best;
00435 public:
00448 Restart(T* s,
00449 unsigned int c_d=Search::Config::c_d,
00450 unsigned int a_d=Search::Config::a_d);
00452 ~Restart(void);
00454 T* next(void);
00455 };
00456
00469 template <class T>
00470 T* restart(T* s,
00471 unsigned int c_d=Search::Config::c_d,
00472 unsigned int a_d=Search::Config::a_d);
00473
00474 }
00475
00476 #include "search/statistics.icc"
00477 #include "search/plain.icc"
00478 #include "search/dfs.icc"
00479 #include "search/lds.icc"
00480 #include "search/bab.icc"
00481 #include "search/restart.icc"
00482
00483 #endif
00484
00485