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 <ctime>
00044
00045 #include "gecode/kernel.hh"
00046
00047
00048
00049
00050
00051 #if !defined(GECODE_STATIC_LIBS) && \
00052 (defined(__CYGWIN__) || defined(__MINGW32__) || defined(_MSC_VER))
00053
00054 #ifdef GECODE_BUILD_SEARCH
00055 #define GECODE_SEARCH_EXPORT __declspec( dllexport )
00056 #else
00057 #define GECODE_SEARCH_EXPORT __declspec( dllimport )
00058 #endif
00059
00060 #else
00061
00062 #ifdef GECODE_GCC_HAS_CLASS_VISIBILITY
00063 #define GECODE_SEARCH_EXPORT __attribute__ ((visibility("default")))
00064 #else
00065 #define GECODE_SEARCH_EXPORT
00066 #endif
00067
00068 #endif
00069
00070 namespace Gecode {
00071
00073 namespace Search {
00074
00080 namespace Config {
00082 const unsigned int c_d = 8;
00084 const unsigned int a_d = 2;
00085 }
00086
00091 class Statistics {
00092 public:
00094 unsigned long int propagate;
00096 unsigned long int fail;
00098 unsigned long int clone;
00100 unsigned long int commit;
00102 size_t memory;
00104 Statistics(void);
00105 };
00106
00107
00122 class GECODE_SEARCH_EXPORT Stop {
00123 public:
00125 Stop(void);
00127 virtual bool stop(const Statistics& s) = 0;
00129 virtual ~Stop(void);
00130 };
00131
00137 class GECODE_SEARCH_EXPORT MemoryStop : public Stop {
00138 protected:
00140 size_t l;
00141 public:
00143 MemoryStop(size_t l);
00145 size_t limit(void) const;
00147 void limit(size_t l);
00149 virtual bool stop(const Statistics& s);
00150 };
00151
00160 class GECODE_SEARCH_EXPORT FailStop : public Stop {
00161 protected:
00163 unsigned long int l;
00164 public:
00166 FailStop(unsigned long int l);
00168 unsigned long int limit(void) const;
00170 void limit(unsigned long int l);
00172 virtual bool stop(const Statistics& s);
00173 };
00174
00179 class GECODE_SEARCH_EXPORT TimeStop : public Stop {
00180 protected:
00182 clock_t s;
00184 unsigned long int l;
00185 public:
00187 TimeStop(unsigned long int l);
00189 unsigned long int limit(void) const;
00191 void limit(unsigned long int l);
00193 void reset(void);
00195 virtual bool stop(const Statistics& s);
00196 };
00197
00224 class Options {
00225 public:
00227 unsigned int c_d;
00229 unsigned int a_d;
00231 Stop* stop;
00233 GECODE_SEARCH_EXPORT static const Options def;
00235 Options(void);
00236 };
00237
00241 class EngineCtrl : public Statistics {
00242 protected:
00244 Stop* st;
00246 bool _stopped;
00248 size_t mem_space;
00250 size_t mem_cur;
00252 size_t mem_total;
00253 public:
00255 EngineCtrl(Stop* st, size_t sz);
00257 void start(void);
00259 bool stop(size_t sz);
00261 bool stopped(void) const;
00263 void push(const Space* s, const BranchingDesc* d);
00265 void constrained(const Space* s1, const Space* s2);
00267 void adapt(const Space* s);
00269 void pop(const Space* s, const BranchingDesc* d);
00271 void lao(const Space* s);
00273 void current(const Space* s);
00275 void reset(const Space* s);
00277 void reset(void);
00278 };
00279
00284 class ReCoNode {
00285 protected:
00287 Space* _space;
00289 unsigned int _alt;
00291 const BranchingDesc* _desc;
00292 public:
00294 ReCoNode(Space* s, Space* c);
00295
00297 Space* space(void) const;
00299 void space(Space* s);
00300
00302 const BranchingDesc* desc(void) const;
00303
00305 unsigned int alt(void) const;
00307 bool rightmost(void) const;
00309 void next(void);
00310
00312 void dispose(void);
00313 };
00314
00315
00329 class ReCoStack {
00330 private:
00332 Support::DynamicStack<ReCoNode> ds;
00334 const unsigned int a_d;
00335 public:
00337 ReCoStack(unsigned int a_d);
00339 const BranchingDesc* push(Space* s, Space* c);
00341 bool next(EngineCtrl& s);
00343 int lc(Space*& s) const;
00345 void unwind(int l);
00347 void commit(Space* s, int i) const;
00355 template <bool constrained>
00356 Space* recompute(unsigned int& d, EngineCtrl& s);
00358 int entries(void) const;
00360 size_t stacksize(void) const;
00362 void reset(void);
00363 };
00364
00369 class DfsEngine : public EngineCtrl {
00370 private:
00372 ReCoStack rcs;
00374 Space* cur;
00376 const unsigned int c_d;
00378 unsigned int d;
00379 public:
00387 DfsEngine(unsigned int c_d, unsigned int a_d, Stop* st, size_t sz);
00389 void init(Space* s);
00391 void reset(Space* s);
00393 void reset(void);
00395 Space* explore(void);
00397 size_t stacksize(void) const;
00399 ~DfsEngine(void);
00400 };
00401
00410 class GECODE_SEARCH_EXPORT DFS {
00411 protected:
00413 DfsEngine e;
00414 public:
00423 DFS(Space* s, unsigned int c_d, unsigned int a_d, Stop* st, size_t sz);
00425 Space* next(void);
00427 Statistics statistics(void) const;
00429 bool stopped(void) const;
00430 };
00431
00432 }
00433
00441 template <class T>
00442 class DFS : public Search::DFS {
00443 public:
00445 DFS(T* s, const Search::Options& o=Search::Options::def);
00447 T* next(void);
00448 };
00449
00451 template <class T>
00452 T* dfs(T* s, const Search::Options& o=Search::Options::def);
00453
00454
00455 namespace Search {
00456
00461 class ProbeEngine : public EngineCtrl {
00462 protected:
00464 class ProbeNode {
00465 private:
00467 Space* _space;
00469 const BranchingDesc* _desc;
00471 unsigned int _alt;
00472 public:
00474 ProbeNode(Space* s, const BranchingDesc* d, unsigned int a);
00476 Space* space(void) const;
00478 const BranchingDesc* desc(void) const;
00480 unsigned int alt(void) const;
00482 void next(void);
00483 };
00485 Support::DynamicStack<ProbeNode> ds;
00487 Space* cur;
00489 unsigned int d;
00491 bool exhausted;
00492 public:
00494 ProbeEngine(Stop* st, size_t s);
00496 void init(Space* s, unsigned int d);
00498 void reset(Space* s, unsigned int d);
00500 size_t stacksize(void) const;
00502 ~ProbeEngine(void);
00504 Space* explore(void);
00506 bool done(void) const;
00507 };
00508
00512 class GECODE_SEARCH_EXPORT LDS {
00513 protected:
00514 Space* root;
00515 unsigned int d_cur;
00516 unsigned int d_max;
00517 bool no_solution;
00518 ProbeEngine e;
00519 public:
00526 LDS(Space* s, unsigned int d, Stop* st, size_t sz);
00528 Space* next(void);
00530 Statistics statistics(void) const;
00532 bool stopped(void) const;
00534 ~LDS(void);
00535 };
00536
00537 }
00538
00543 template <class T>
00544 class LDS : public Search::LDS {
00545 public:
00547 LDS(T* s, unsigned int d,
00548 const Search::Options& o=Search::Options::def);
00550 T* next(void);
00551 };
00552
00557 template <class T>
00558 T* lds(T* s, unsigned int d,
00559 const Search::Options& o=Search::Options::def);
00560
00561
00562
00563
00564
00565
00566
00567
00568
00569
00570 namespace Search {
00571
00575 class BabEngine : public EngineCtrl {
00576 public:
00578 enum ExploreStatus {
00579 ES_SOLUTION,
00580 ES_CONSTRAIN
00581 };
00582 private:
00584 ReCoStack rcs;
00586 Space* cur;
00588 int mark;
00590 ExploreStatus es;
00592 Space* best;
00594 const unsigned int c_d;
00596 unsigned int d;
00597 public:
00605 BabEngine(unsigned int c_d, unsigned int a_d, Stop* st, size_t sz);
00607 void init(Space* s);
00619 GECODE_SEARCH_EXPORT
00620 ExploreStatus explore(Space*& s1, Space*& s2);
00622 size_t stacksize(void) const;
00624 ~BabEngine(void);
00625 };
00626
00636 class GECODE_SEARCH_EXPORT BAB {
00637 protected:
00639 BabEngine e;
00640 public:
00649 BAB(Space* s, unsigned int c_d, unsigned int a_d, Stop* st, size_t sz);
00651 bool stopped(void) const;
00653 Statistics statistics(void) const;
00654 };
00655
00656 }
00657
00669 template <class T>
00670 class BAB : public Search::BAB {
00671 public:
00673 BAB(T* s, const Search::Options& o=Search::Options::def);
00675 T* next(void);
00676 };
00677
00690 template <class T>
00691 T* bab(T* s, const Search::Options& o=Search::Options::def);
00692
00693
00694
00706 template <class T>
00707 class Restart : public DFS<T> {
00708 protected:
00710 Space* root;
00712 Space* best;
00713 public:
00715 Restart(T* s, const Search::Options& o=Search::Options::def);
00717 ~Restart(void);
00719 T* next(void);
00720 };
00721
00733 template <class T>
00734 T* restart(T* s, const Search::Options& o=Search::Options::def);
00735
00736 }
00737
00738 #include "gecode/search/statistics.icc"
00739 #include "gecode/search/stop.icc"
00740 #include "gecode/search/options.icc"
00741 #include "gecode/search/engine-ctrl.icc"
00742
00743 #include "gecode/search/reco-stack.icc"
00744
00745 #include "gecode/search/dfs.icc"
00746 #include "gecode/search/lds.icc"
00747 #include "gecode/search/bab.icc"
00748 #include "gecode/search/restart.icc"
00749
00750 #endif
00751
00752