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
00041
00042 #ifndef __GECODE_SEARCH_HH__
00043 #define __GECODE_SEARCH_HH__
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
00071 #ifndef GECODE_BUILD_SEARCH
00072 #define GECODE_LIBRARY_NAME "Search"
00073 #include <gecode/support/auto-link.hpp>
00074 #endif
00075
00076
00077 namespace Gecode { namespace Search {
00078
00080 namespace Sequential {}
00081
00083 namespace Parallel {}
00084
00086 namespace Meta {}
00087
00088 namespace Meta {
00089
00091 namespace Sequential {}
00092
00094 namespace Parallel {}
00095
00096 }
00097
00098
00104 namespace Config {
00106 const bool clone = true;
00108 const double threads = 1.0;
00109
00111 const unsigned int c_d = 8;
00113 const unsigned int a_d = 2;
00114
00116 const unsigned int steal_limit = 3;
00118 const unsigned int initial_delay = 5;
00119
00121 const unsigned int d_l = 5;
00122
00124 const double base = 1.5;
00126 const unsigned int slice = 250;
00127
00129 const unsigned int nogoods_limit = 128;
00130
00132 const unsigned int cpprofiler_port = 6565U;
00133 }
00134
00135 }}
00136
00137 #include <gecode/search/exception.hpp>
00138
00139 namespace Gecode { namespace Search {
00140
00145 class Statistics : public StatusStatistics {
00146 public:
00148 unsigned long int fail;
00150 unsigned long int node;
00152 unsigned long int depth;
00154 unsigned long int restart;
00156 unsigned long int nogood;
00158 Statistics(void);
00160 void reset(void);
00162 Statistics operator +(const Statistics& s);
00164 Statistics& operator +=(const Statistics& s);
00165 };
00166
00167 }}
00168
00169 #include <gecode/search/statistics.hpp>
00170
00171 namespace Gecode { namespace Search {
00172
00173 class WrapTraceRecorder;
00174 class TraceRecorder;
00175 class EdgeTraceRecorder;
00176
00177 }}
00178
00179 #include <string>
00180 #include <sstream>
00181
00182 namespace Gecode {
00183
00185 class SearchTracer {
00186 friend class Search::WrapTraceRecorder;
00187 friend class Search::TraceRecorder;
00188 friend class Search::EdgeTraceRecorder;
00189 public:
00191 enum EngineType {
00192 DFS = 0,
00193 BAB = 1,
00194 LDS = 2,
00195 RBS = 3,
00196 PBS = 4,
00197 AOE = 5
00198 };
00200 class EngineInfo {
00201 protected:
00203 EngineType _type;
00205 unsigned int _fst;
00207 unsigned int _lst;
00208 public:
00210 EngineInfo(void);
00212 EngineInfo(EngineType et, unsigned int fst, unsigned int lst);
00214
00215
00216 EngineType type(void) const;
00218 bool meta(void) const;
00220
00221
00222
00223 unsigned int wfst(void) const;
00225 unsigned int wlst(void) const;
00227 unsigned int workers(void) const;
00229
00230
00231
00232 unsigned int efst(void) const;
00234 unsigned int elst(void) const;
00236 unsigned int engines(void) const;
00238 };
00240 class EdgeInfo {
00241 protected:
00243 unsigned int _wid;
00245 unsigned int _nid;
00247 unsigned int _a;
00249 std::string _s;
00250 public:
00252 void init(unsigned int wid, unsigned int nid, unsigned int a);
00254 void init(unsigned int wid, unsigned int nid, unsigned int a,
00255 const Space& s, const Choice & c);
00257 void invalidate(void);
00259 EdgeInfo(void);
00261 EdgeInfo(unsigned int wid, unsigned int nid, unsigned int a);
00263 operator bool(void) const;
00265 unsigned int wid(void) const;
00267 unsigned int nid(void) const;
00269 unsigned int alternative(void) const;
00271 std::string string(void) const;
00272 };
00274 enum NodeType {
00275 SOLVED = 0,
00276 FAILED = 1,
00277 BRANCH = 2
00278 };
00280 class NodeInfo {
00281 protected:
00283 NodeType _nt;
00285 unsigned int _wid;
00287 unsigned int _nid;
00289 const Space& _s;
00291 const Choice* _c;
00292 public:
00294 NodeInfo(NodeType nt,
00295 unsigned int wid, unsigned int nid,
00296 const Space& s, const Choice* c = nullptr);
00298 NodeType type(void) const;
00300 unsigned int wid(void) const;
00302 unsigned int nid(void) const;
00304 const Space& space(void) const;
00306 const Choice& choice(void) const;
00307 };
00308 private:
00310 Support::Mutex m;
00312 unsigned int pending;
00314 unsigned int n_e;
00316 unsigned int n_w;
00318 unsigned int n_active;
00320 Support::DynamicArray<EngineInfo,Heap> es;
00322 Support::DynamicArray<unsigned int,Heap> w2e;
00324 void engine(EngineType t, unsigned int n);
00326 void worker(unsigned int& wid, unsigned int& eid);
00328 void worker(void);
00330
00332 void _round(unsigned int eid);
00334 void _skip(const EdgeInfo& ei);
00336 void _node(const EdgeInfo& ei, const NodeInfo& ni);
00338 public:
00340 SearchTracer(void);
00342
00343
00344 unsigned int workers(void) const;
00346 unsigned int engines(void) const;
00348 const EngineInfo& engine(unsigned int eid) const;
00350 unsigned int eid(unsigned int wid) const;
00352
00353
00354
00355 virtual void init(void) = 0;
00357 virtual void round(unsigned int eid) = 0;
00359 virtual void skip(const EdgeInfo& ei) = 0;
00361 virtual void node(const EdgeInfo& ei, const NodeInfo& ni) = 0;
00363 virtual void done(void) = 0;
00365
00366 virtual ~SearchTracer(void);
00367 };
00368
00369 class GECODE_SEARCH_EXPORT StdSearchTracer : public SearchTracer {
00370 protected:
00372 std::ostream& os;
00374 static const char* t2s[EngineType::AOE + 1];
00375 public:
00377 StdSearchTracer(std::ostream& os = std::cerr);
00379 virtual void init(void);
00381 virtual void round(unsigned int eid);
00383 virtual void skip(const EdgeInfo& ei);
00385 virtual void node(const EdgeInfo& ei, const NodeInfo& ni);
00387 virtual void done(void);
00389 virtual ~StdSearchTracer(void);
00391 static StdSearchTracer def;
00392 };
00393
00394 }
00395
00396 #include <gecode/search/tracer.hpp>
00397 #include <gecode/search/trace-recorder.hpp>
00398
00399 #ifdef GECODE_HAS_CPPROFILER
00400
00401 namespace Gecode {
00402
00404 namespace CPProfiler {}
00405
00406 }
00407
00408 namespace Gecode { namespace CPProfiler {
00409
00411 class Connector;
00412
00413 }}
00414
00415 namespace Gecode {
00416
00418 class GECODE_SEARCH_EXPORT CPProfilerSearchTracer : public SearchTracer {
00419 public:
00421 class GECODE_SEARCH_EXPORT GetInfo : public HeapAllocated {
00422 public:
00424 GetInfo(void);
00426 virtual std::string getInfo(const Space& home) const = 0;
00428 virtual ~GetInfo(void);
00429 };
00430 private:
00432 CPProfiler::Connector* connector;
00434 int execution_id;
00436 std::string name;
00438 int restart;
00440 const GetInfo* pgi;
00441 public:
00443 CPProfilerSearchTracer(int eid, std::string name,
00444 unsigned int port = Search::Config::cpprofiler_port,
00445 const GetInfo* pgi = nullptr);
00447 virtual void init(void);
00449 virtual void round(unsigned int eid);
00451 virtual void skip(const EdgeInfo& ei);
00453 virtual void node(const EdgeInfo& ei, const NodeInfo& ni);
00455 virtual void done(void);
00457 virtual ~CPProfilerSearchTracer(void);
00458 };
00459
00460 }
00461
00462 #endif
00463
00464 namespace Gecode { namespace Search {
00465
00470 class GECODE_SEARCH_EXPORT Cutoff : public HeapAllocated {
00471 public:
00473
00474
00475 Cutoff(void);
00477 virtual unsigned long int operator ()(void) const = 0;
00479 virtual unsigned long int operator ++(void) = 0;
00481 virtual ~Cutoff(void);
00483
00484
00485
00486 static Cutoff*
00487 constant(unsigned long int scale=Config::slice);
00489 static Cutoff*
00490 linear(unsigned long int scale=Config::slice);
00494 static Cutoff*
00495 geometric(unsigned long int scale=Config::slice, double base=Config::base);
00497 static Cutoff*
00498 luby(unsigned long int scale=Config::slice);
00503 static Cutoff*
00504 rnd(unsigned int seed,
00505 unsigned long int min, unsigned long int max,
00506 unsigned long int n);
00508 static Cutoff*
00509 append(Cutoff* c1, unsigned long int n, Cutoff* c2);
00511 static Cutoff*
00512 merge(Cutoff* c1, Cutoff* c2);
00514 static Cutoff*
00515 repeat(Cutoff* c, unsigned long int n);
00517 };
00518
00523 class GECODE_SEARCH_EXPORT CutoffConstant : public Cutoff {
00524 protected:
00526 unsigned long int c;
00527 public:
00529 CutoffConstant(unsigned long int c);
00531 virtual unsigned long int operator ()(void) const;
00533 virtual unsigned long int operator ++(void);
00534 };
00535
00540 class GECODE_SEARCH_EXPORT CutoffLinear : public Cutoff {
00541 protected:
00543 unsigned long int scale;
00545 unsigned long int n;
00546 public:
00548 CutoffLinear(unsigned long int scale);
00550 virtual unsigned long int operator ()(void) const;
00552 virtual unsigned long int operator ++(void);
00553 };
00554
00559 class GECODE_SEARCH_EXPORT CutoffLuby : public Cutoff {
00560 protected:
00562 unsigned long int i;
00564 unsigned long int scale;
00566 static const unsigned long int n_start = 63U;
00568 static unsigned long int start[n_start];
00570 static unsigned long int log(unsigned long int i);
00572 static unsigned long int luby(unsigned long int i);
00573 public:
00575 CutoffLuby(unsigned long int scale);
00577 virtual unsigned long int operator ()(void) const;
00579 virtual unsigned long int operator ++(void);
00580 };
00581
00586 class GECODE_SEARCH_EXPORT CutoffGeometric : public Cutoff {
00587 protected:
00589 double n;
00591 double scale;
00593 double base;
00594 public:
00596 CutoffGeometric(unsigned long int scale, double base);
00598 virtual unsigned long int operator ()(void) const;
00600 virtual unsigned long int operator ++(void);
00601 };
00602
00607 class GECODE_SEARCH_EXPORT CutoffRandom : public Cutoff {
00608 protected:
00610 Support::RandomGenerator rnd;
00612 unsigned long int min;
00614 unsigned long int n;
00616 unsigned long int step;
00618 unsigned long int cur;
00619 public:
00621 CutoffRandom(unsigned int seed,
00622 unsigned long int min, unsigned long int max,
00623 unsigned long int n);
00625 virtual unsigned long int operator ()(void) const;
00627 virtual unsigned long int operator ++(void);
00628 };
00629
00634 class GECODE_SEARCH_EXPORT CutoffAppend : public Cutoff {
00635 protected:
00637 Cutoff* c1;
00639 Cutoff* c2;
00641 unsigned long int n;
00642 public:
00644 CutoffAppend(Cutoff* c1, unsigned long int n, Cutoff* c2);
00646 virtual unsigned long int operator ()(void) const;
00648 virtual unsigned long int operator ++(void);
00650 virtual ~CutoffAppend(void);
00651 };
00652
00657 class GECODE_SEARCH_EXPORT CutoffMerge : public Cutoff {
00658 protected:
00660 Cutoff* c1;
00662 Cutoff* c2;
00663 public:
00665 CutoffMerge(Cutoff* c1, Cutoff* c2);
00667 virtual unsigned long int operator ()(void) const;
00669 virtual unsigned long int operator ++(void);
00671 virtual ~CutoffMerge(void);
00672 };
00673
00678 class GECODE_SEARCH_EXPORT CutoffRepeat : public Cutoff {
00679 protected:
00681 Cutoff* c;
00682
00683 unsigned int cutoff;
00684
00685 unsigned long int i;
00686
00687 unsigned long int n;
00688 public:
00690 CutoffRepeat(Cutoff* c, unsigned long int n);
00692 virtual unsigned long int operator ()(void) const;
00694 virtual unsigned long int operator ++(void);
00696 virtual ~CutoffRepeat(void);
00697 };
00698
00699 }}
00700
00701 #include <gecode/search/cutoff.hpp>
00702
00703 namespace Gecode { namespace Search {
00704
00705 class Stop;
00706
00744 class Options {
00745 public:
00747 bool clone;
00749 double threads;
00751 unsigned int c_d;
00753 unsigned int a_d;
00755 unsigned int d_l;
00757 unsigned int assets;
00759 unsigned int slice;
00761 unsigned int nogoods_limit;
00763 Stop* stop;
00765 Cutoff* cutoff;
00767 SearchTracer* tracer;
00769 GECODE_SEARCH_EXPORT static const Options def;
00771 Options(void);
00773 GECODE_SEARCH_EXPORT Options
00774 expand(void) const;
00775 };
00776
00777 }}
00778
00779 #include <gecode/search/options.hpp>
00780
00781 namespace Gecode { namespace Search {
00782
00797 class GECODE_SEARCH_EXPORT Stop : public HeapAllocated {
00798 public:
00800
00801
00802 Stop(void);
00804 virtual bool stop(const Statistics& s, const Options& o) = 0;
00806 virtual ~Stop(void);
00808
00809
00810
00811 static Stop* node(unsigned long int l);
00813 static Stop* fail(unsigned long int l);
00815 static Stop* time(unsigned long int l);
00817 };
00818
00827 class GECODE_SEARCH_EXPORT NodeStop : public Stop {
00828 protected:
00830 unsigned long int l;
00831 public:
00833 NodeStop(unsigned long int l);
00835 unsigned long int limit(void) const;
00837 void limit(unsigned long int l);
00839 virtual bool stop(const Statistics& s, const Options& o);
00840 };
00841
00850 class GECODE_SEARCH_EXPORT FailStop : public Stop {
00851 protected:
00853 unsigned long int l;
00854 public:
00856 FailStop(unsigned long int l);
00858 unsigned long int limit(void) const;
00860 void limit(unsigned long int l);
00862 virtual bool stop(const Statistics& s, const Options& o);
00863 };
00864
00869 class GECODE_SEARCH_EXPORT TimeStop : public Stop {
00870 protected:
00872 Support::Timer t;
00874 unsigned long int l;
00875 public:
00877 TimeStop(unsigned long int l);
00879 unsigned long int limit(void) const;
00881 void limit(unsigned long int l);
00883 void reset(void);
00885 virtual bool stop(const Statistics& s, const Options& o);
00886 };
00887
00888 }}
00889
00890 #include <gecode/search/stop.hpp>
00891
00892 namespace Gecode { namespace Search {
00893
00897 class GECODE_SEARCH_EXPORT Engine : public HeapAllocated {
00898 public:
00900 virtual Space* next(void) = 0;
00902 virtual Statistics statistics(void) const = 0;
00904 virtual bool stopped(void) const = 0;
00906 virtual void constrain(const Space& b);
00908 virtual void reset(Space* s);
00910 virtual NoGoods& nogoods(void);
00912 virtual ~Engine(void);
00913 };
00914
00915 }}
00916
00917 #include <gecode/search/engine.hpp>
00918
00919 namespace Gecode { namespace Search {
00920
00922 template<class T>
00923 class Base : public HeapAllocated {
00924 template<class, class>
00925 friend Engine* build(Space*, const Options&);
00926 template<class, template<class> class>
00927 friend Engine* build(Space*, const Options&);
00928 protected:
00930 Engine* e;
00932 Base(Engine* e = NULL);
00933 public:
00935 virtual T* next(void);
00937 virtual Statistics statistics(void) const;
00939 virtual bool stopped(void) const;
00941 virtual ~Base(void);
00942 private:
00944 Base(const Base&);
00946 Base& operator =(const Base&);
00947 };
00948
00949 }}
00950
00951 #include <gecode/search/base.hpp>
00952
00953 namespace Gecode { namespace Search {
00954
00956 template<class T, class E>
00957 Engine* build(Space* s, const Options& opt);
00959 template<class T, template<class> class E>
00960 Engine* build(Space* s, const Options& opt);
00961
00963 class GECODE_SEARCH_EXPORT Builder : public HeapAllocated {
00964 protected:
00966 Options opt;
00968 const bool b;
00969 public:
00971 Builder(const Options& opt, bool best);
00973 Options& options(void);
00975 const Options& options(void) const;
00977 bool best(void) const;
00979 virtual Engine* operator() (Space* s) const = 0;
00981 virtual ~Builder(void);
00982 };
00983
00984 }}
00985
00986 #include <gecode/search/build.hpp>
00987
00988 namespace Gecode {
00989
00991 typedef Search::Builder* SEB;
00992
00993 }
00994
00995 #include <gecode/search/traits.hpp>
00996
00997 namespace Gecode {
00998
01000 class SEBs : public PrimArgArray<SEB> {
01001 public:
01003
01004
01005 SEBs(void);
01007 explicit SEBs(int n);
01009 SEBs(const std::vector<SEB>& x);
01011 template<class InputIterator>
01012 SEBs(InputIterator first, InputIterator last);
01014 SEBs(const PrimArgArray<SEB>& a);
01016 GECODE_SEARCH_EXPORT
01017 SEBs(int n, SEB b0, ...);
01019 };
01020
01021 }
01022
01023 #include <gecode/search/sebs.hpp>
01024
01025 namespace Gecode {
01026
01034 template<class T>
01035 class DFS : public Search::Base<T> {
01036 public:
01038 DFS(T* s, const Search::Options& o=Search::Options::def);
01040 static const bool best = false;
01041 };
01042
01044 template<class T>
01045 T* dfs(T* s, const Search::Options& o=Search::Options::def);
01046
01048 template<class T>
01049 SEB dfs(const Search::Options& o=Search::Options::def);
01050
01051 }
01052
01053 #include <gecode/search/dfs.hpp>
01054
01055 namespace Gecode {
01056
01068 template<class T>
01069 class BAB : public Search::Base<T> {
01070 public:
01072 BAB(T* s, const Search::Options& o=Search::Options::def);
01074 static const bool best = true;
01075 };
01076
01089 template<class T>
01090 T* bab(T* s, const Search::Options& o=Search::Options::def);
01091
01093 template<class T>
01094 SEB bab(const Search::Options& o=Search::Options::def);
01095
01096 }
01097
01098 #include <gecode/search/bab.hpp>
01099
01100 namespace Gecode {
01101
01106 template<class T>
01107 class LDS : public Search::Base<T> {
01108 public:
01110 LDS(T* s, const Search::Options& o=Search::Options::def);
01112 static const bool best = false;
01113 };
01114
01119 template<class T>
01120 T* lds(T* s, const Search::Options& o=Search::Options::def);
01121
01123 template<class T>
01124 SEB lds(const Search::Options& o=Search::Options::def);
01125
01126 }
01127
01128 #include <gecode/search/lds.hpp>
01129
01130 namespace Gecode {
01131
01150 template<class T, template<class> class E = DFS>
01151 class RBS : public Search::Base<T> {
01152 using Search::Base<T>::e;
01153 public:
01155 RBS(T* s, const Search::Options& o);
01157 static const bool best = E<T>::best;
01158 };
01159
01178 template<class T, template<class> class E>
01179 T* rbs(T* s, const Search::Options& o);
01180
01182 template<class T, template<class> class E>
01183 SEB rbs(const Search::Options& o);
01184
01185 }
01186
01187 #include <gecode/search/rbs.hpp>
01188
01189 namespace Gecode { namespace Search { namespace Meta {
01190
01192 template<class T, template<class> class E>
01193 Engine* sequential(T* master, const Search::Statistics& stat, Options& opt);
01194
01196 template<class T, template<class> class E>
01197 Engine* sequential(T* master, SEBs& sebs,
01198 const Search::Statistics& stat, Options& opt, bool best);
01199
01200 #ifdef GECODE_HAS_THREADS
01201
01203 template<class T, template<class> class E>
01204 Engine* parallel(T* master, const Search::Statistics& stat, Options& opt);
01205
01207 template<class T, template<class> class E>
01208 Engine* parallel(T* master, SEBs& sebs,
01209 const Search::Statistics& stat, Options& opt, bool best);
01210
01211 #endif
01212
01213 }}}
01214
01215 namespace Gecode {
01216
01234 template<class T, template<class> class E = DFS>
01235 class PBS : public Search::Base<T> {
01236 using Search::Base<T>::e;
01237 protected:
01239 void build(T* s, SEBs& sebs, const Search::Options& o);
01240 public:
01242 PBS(T* s, const Search::Options& o=Search::Options::def);
01244 PBS(T* s, SEBs& sebs, const Search::Options& o=Search::Options::def);
01246 PBS(T* s, SEB seb0, SEB seb1,
01247 const Search::Options& o=Search::Options::def);
01249 PBS(T* s, SEB seb0, SEB seb1, SEB seb2,
01250 const Search::Options& o=Search::Options::def);
01252 PBS(T* s, SEB seb0, SEB seb1, SEB seb2, SEB seb3,
01253 const Search::Options& o=Search::Options::def);
01255 static const bool best = E<T>::best;
01256 };
01257
01275 template<class T, template<class> class E>
01276 T* pbs(T* s, const Search::Options& o=Search::Options::def);
01277
01279 template<class T>
01280 SEB pbs(const Search::Options& o=Search::Options::def);
01281
01282 }
01283
01284 #include <gecode/search/pbs.hpp>
01285
01286 #endif
01287
01288