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 <ctime>
00028
00029 #include "gecode/kernel.hh"
00030
00031
00032
00033
00034
00035
00036 #if !defined(GECODE_STATIC_LIBS) && \
00037 (defined(__CYGWIN__) || defined(__MINGW32__) || defined(_MSC_VER))
00038
00039 #ifdef GECODE_BUILD_SEARCH
00040 #define GECODE_SEARCH_EXPORT __declspec( dllexport )
00041 #else
00042 #define GECODE_SEARCH_EXPORT __declspec( dllimport )
00043 #endif
00044
00045 #else
00046
00047 #define GECODE_SEARCH_EXPORT
00048
00049 #endif
00050
00051 #include "gecode/support/dynamic-stack.hh"
00052
00053 namespace Gecode {
00054
00056 namespace Search {
00057
00063 namespace Config {
00065 const unsigned int c_d = 8;
00067 const unsigned int a_d = 2;
00068 }
00069
00074 class Statistics {
00075 public:
00077 unsigned long int propagate;
00079 unsigned long int fail;
00081 unsigned long int clone;
00083 unsigned long int commit;
00085 size_t memory;
00087 Statistics(void);
00088 };
00089
00090
00105 class Stop {
00106 public:
00108 Stop(void);
00110 virtual bool stop(const Statistics& s) = 0;
00112 GECODE_SEARCH_EXPORT virtual ~Stop(void);
00113 };
00114
00120 class MemoryStop : public Stop {
00121 protected:
00123 size_t l;
00124 public:
00126 MemoryStop(size_t l);
00128 size_t limit(void) const;
00130 void limit(size_t l);
00132 GECODE_SEARCH_EXPORT virtual bool stop(const Statistics& s);
00133 };
00134
00143 class FailStop : public Stop {
00144 protected:
00146 unsigned long int l;
00147 public:
00149 FailStop(unsigned long int l);
00151 unsigned long int limit(void) const;
00153 void limit(unsigned long int l);
00155 GECODE_SEARCH_EXPORT virtual bool stop(const Statistics& s);
00156 };
00157
00162 class TimeStop : public Stop {
00163 protected:
00165 clock_t s;
00167 unsigned long int l;
00168 public:
00170 TimeStop(unsigned long int l);
00172 unsigned long int limit(void) const;
00174 void limit(unsigned long int l);
00176 void reset(void);
00178 GECODE_SEARCH_EXPORT virtual bool stop(const Statistics& s);
00179 };
00180
00181
00185 class EngineCtrl : public Statistics {
00186 protected:
00188 Stop* st;
00190 bool _stopped;
00192 size_t mem_space;
00194 size_t mem_cur;
00196 size_t mem_total;
00197 public:
00199 EngineCtrl(Stop* st, size_t sz);
00201 void start(void);
00203 bool stop(size_t sz);
00205 bool stopped(void) const;
00207 void push(const Space* s);
00209 void push(const Space* s, const BranchingDesc* d);
00211 void pop(const Space* s);
00213 void pop(const Space* s, const BranchingDesc* d);
00215 void current(const Space* s);
00217 void reset(const Space* s);
00218 };
00219
00224 class ReCoNode {
00225 protected:
00227 Space* _space;
00229 unsigned int _alt;
00231 unsigned int _last;
00233 BranchingDesc* _desc;
00234 public:
00236 ReCoNode(Space* s, Space* c, unsigned int alt);
00238 Space* space(void) const;
00240 unsigned int alt(void) const;
00242 BranchingDesc* desc(void) const;
00244 void space(Space* s);
00246 void alt(unsigned int a);
00248 void desc(BranchingDesc* d);
00250 bool rightmost(void) const;
00252 void next(void);
00254 unsigned int share(void);
00256 void dispose(void);
00257 };
00258
00259
00273 class ReCoStack : public Support::DynamicStack<ReCoNode> {
00274 private:
00276 const unsigned int a_d;
00277 public:
00279 ReCoStack(unsigned int a_d);
00281 BranchingDesc* push(Space* s, Space* c, unsigned int a);
00283 bool next(EngineCtrl& s);
00285 GECODE_SEARCH_EXPORT
00286 Space* recompute(unsigned int& d,
00287 EngineCtrl& s);
00289 void reset(void);
00290 };
00291
00296 class DfsEngine : public EngineCtrl {
00297 private:
00299 ReCoStack ds;
00301 Space* cur;
00303 const unsigned int c_d;
00305 unsigned int d;
00306 public:
00314 DfsEngine(unsigned int c_d, unsigned int a_d, Stop* st, size_t sz);
00316 void init(Space* s);
00318 void reset(Space* s);
00320 Space* explore(void);
00322 size_t stacksize(void) const;
00324 ~DfsEngine(void);
00325 };
00326
00335 class GECODE_SEARCH_EXPORT DFS {
00336 protected:
00338 DfsEngine e;
00339 public:
00348 DFS(Space* s, unsigned int c_d, unsigned int a_d, Stop* st, size_t sz);
00350 Space* next(void);
00352 Statistics statistics(void) const;
00354 bool stopped(void) const;
00355 };
00356
00357 }
00358
00366 template <class T>
00367 class DFS : public Search::DFS {
00368 public:
00376 DFS(T* s,
00377 unsigned int c_d=Search::Config::c_d,
00378 unsigned int a_d=Search::Config::a_d,
00379 Search::Stop* st=NULL);
00381 T* next(void);
00382 };
00383
00392 template <class T>
00393 T* dfs(T* s,
00394 unsigned int c_d=Search::Config::c_d,
00395 unsigned int a_d=Search::Config::a_d,
00396 Search::Stop* st=NULL);
00397
00398
00399
00400 namespace Search {
00401
00406 class ProbeEngine : public EngineCtrl {
00407 protected:
00409 class ProbeNode {
00410 private:
00412 Space* _space;
00414 unsigned int _alt;
00415 public:
00417 ProbeNode(Space* s, unsigned int a);
00419 Space* space(void) const;
00421 void space(Space* s);
00423 unsigned int alt(void) const;
00425 void alt(unsigned int a);
00426 };
00428 Support::DynamicStack<ProbeNode> ds;
00430 Space* cur;
00432 unsigned int d;
00433 public:
00435 ProbeEngine(Stop* st, size_t s);
00437 void init(Space* s, unsigned int d);
00439 void reset(Space* s, unsigned int d);
00441 size_t stacksize(void) const;
00443 ~ProbeEngine(void);
00445 Space* explore(void);
00446 };
00447
00451 class GECODE_SEARCH_EXPORT LDS {
00452 protected:
00453 Space* root;
00454 unsigned int d_cur;
00455 unsigned int d_max;
00456 bool no_solution;
00457 ProbeEngine e;
00458 public:
00465 LDS(Space* s, unsigned int d, Stop* st, size_t sz);
00467 Space* next(void);
00469 Statistics statistics(void) const;
00471 bool stopped(void) const;
00473 ~LDS(void);
00474 };
00475
00476 }
00477
00482 template <class T>
00483 class LDS : public Search::LDS {
00484 public:
00490 LDS(T* s, unsigned int d, Search::Stop* st=NULL);
00492 T* next(void);
00493 };
00494
00502 template <class T>
00503 T* lds(T* s,unsigned int d, Search::Stop* st=NULL);
00504
00505
00506
00507
00508
00509
00510
00511
00512
00513
00514 namespace Search {
00515
00519 class BabEngine : public EngineCtrl {
00520 private:
00522 ReCoStack ds;
00524 Space* cur;
00526 unsigned int mark;
00528 Space* best;
00530 const unsigned int c_d;
00532 unsigned int d;
00533 public:
00541 BabEngine(unsigned int c_d, unsigned int a_d, Stop* st, size_t sz);
00543 void init(Space* s);
00554 GECODE_SEARCH_EXPORT
00555 bool explore(Space*& s1, Space*& s2);
00557 size_t stacksize(void) const;
00559 ~BabEngine(void);
00560 };
00561
00571 class GECODE_SEARCH_EXPORT BAB {
00572 protected:
00574 BabEngine e;
00575 public:
00584 BAB(Space* s, unsigned int c_d, unsigned int a_d, Stop* st, size_t sz);
00586 bool stopped(void) const;
00588 Statistics statistics(void) const;
00589 };
00590
00591 }
00592
00597 template <class T>
00598 class BAB : public Search::BAB {
00599 public:
00613 BAB(T* s,
00614 unsigned int c_d=Search::Config::c_d,
00615 unsigned int a_d=Search::Config::a_d,
00616 Search::Stop* st=NULL);
00618 T* next(void);
00619 };
00620
00635 template <class T>
00636 T* bab(T* s,
00637 unsigned int c_d=Search::Config::c_d,
00638 unsigned int a_d=Search::Config::a_d,
00639 Search::Stop* st=NULL);
00640
00641
00642
00647 template <class T>
00648 class Restart : public DFS<T> {
00649 protected:
00651 Space* root;
00653 Space* best;
00654 public:
00668 Restart(T* s,
00669 unsigned int c_d=Search::Config::c_d,
00670 unsigned int a_d=Search::Config::a_d,
00671 Search::Stop* st=NULL);
00673 ~Restart(void);
00675 T* next(void);
00676 };
00677
00691 template <class T>
00692 T* restart(T* s,
00693 unsigned int c_d=Search::Config::c_d,
00694 unsigned int a_d=Search::Config::a_d,
00695 Search::Stop* st=NULL);
00696
00697 }
00698
00699 #include "gecode/search/statistics.icc"
00700 #include "gecode/search/stop.icc"
00701 #include "gecode/search/engine-ctrl.icc"
00702
00703 #include "gecode/search/reco-stack.icc"
00704
00705 #include "gecode/search/dfs.icc"
00706 #include "gecode/search/lds.icc"
00707 #include "gecode/search/bab.icc"
00708 #include "gecode/search/restart.icc"
00709
00710 #endif
00711
00712