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 <initializer_list>
00046
00047 #include <gecode/kernel.hh>
00048
00049
00050
00051
00052
00053 #if !defined(GECODE_STATIC_LIBS) && \
00054 (defined(__CYGWIN__) || defined(__MINGW32__) || defined(_MSC_VER))
00055
00056 #ifdef GECODE_BUILD_SEARCH
00057 #define GECODE_SEARCH_EXPORT __declspec( dllexport )
00058 #else
00059 #define GECODE_SEARCH_EXPORT __declspec( dllimport )
00060 #endif
00061
00062 #else
00063
00064 #ifdef GECODE_GCC_HAS_CLASS_VISIBILITY
00065 #define GECODE_SEARCH_EXPORT __attribute__ ((visibility("default")))
00066 #else
00067 #define GECODE_SEARCH_EXPORT
00068 #endif
00069
00070 #endif
00071
00072
00073 #ifndef GECODE_BUILD_SEARCH
00074 #define GECODE_LIBRARY_NAME "Search"
00075 #include <gecode/support/auto-link.hpp>
00076 #endif
00077
00078
00079 namespace Gecode { namespace Search {
00080
00082 namespace Sequential {}
00083
00085 namespace Parallel {}
00086
00088 namespace Meta {}
00089
00090 namespace Meta {
00091
00093 namespace Sequential {}
00094
00096 namespace Parallel {}
00097
00098 }
00099
00100
00106 namespace Config {
00108 const bool clone = true;
00110 const double threads = 1.0;
00111
00113 const unsigned int c_d = 8;
00115 const unsigned int a_d = 2;
00116
00118 const unsigned int steal_limit = 3;
00120 const unsigned int initial_delay = 5;
00121
00123 const unsigned int d_l = 5;
00124
00126 const double base = 1.5;
00128 const unsigned int slice = 250;
00129
00131 const unsigned int nogoods_limit = 128;
00132
00134 const unsigned int cpprofiler_port = 6565U;
00135 }
00136
00137 }}
00138
00139 #include <gecode/search/exception.hpp>
00140
00141 namespace Gecode { namespace Search {
00142
00147 class Statistics : public StatusStatistics {
00148 public:
00150 unsigned long int fail;
00152 unsigned long int node;
00154 unsigned long int depth;
00156 unsigned long int restart;
00158 unsigned long int nogood;
00160 Statistics(void);
00162 void reset(void);
00164 Statistics operator +(const Statistics& s);
00166 Statistics& operator +=(const Statistics& s);
00167 };
00168
00169 }}
00170
00171 #include <gecode/search/statistics.hpp>
00172
00173 namespace Gecode { namespace Search {
00174
00175 class WrapTraceRecorder;
00176 class TraceRecorder;
00177 class EdgeTraceRecorder;
00178
00179 }}
00180
00181 #include <string>
00182 #include <sstream>
00183
00184 namespace Gecode {
00185
00187 class SearchTracer {
00188 friend class Search::WrapTraceRecorder;
00189 friend class Search::TraceRecorder;
00190 friend class Search::EdgeTraceRecorder;
00191 public:
00193 enum EngineType {
00194 DFS = 0,
00195 BAB = 1,
00196 LDS = 2,
00197 RBS = 3,
00198 PBS = 4,
00199 AOE = 5
00200 };
00202 class EngineInfo {
00203 protected:
00205 EngineType _type;
00207 unsigned int _fst;
00209 unsigned int _lst;
00210 public:
00212 EngineInfo(void);
00214 EngineInfo(EngineType et, unsigned int fst, unsigned int lst);
00216
00217
00218 EngineType type(void) const;
00220 bool meta(void) const;
00222
00223
00224
00225 unsigned int wfst(void) const;
00227 unsigned int wlst(void) const;
00229 unsigned int workers(void) const;
00231
00232
00233
00234 unsigned int efst(void) const;
00236 unsigned int elst(void) const;
00238 unsigned int engines(void) const;
00240 };
00242 class EdgeInfo {
00243 protected:
00245 unsigned int _wid;
00247 unsigned int _nid;
00249 unsigned int _a;
00251 std::string _s;
00252 public:
00254 void init(unsigned int wid, unsigned int nid, unsigned int a);
00256 void init(unsigned int wid, unsigned int nid, unsigned int a,
00257 const Space& s, const Choice & c);
00259 void invalidate(void);
00261 EdgeInfo(void);
00263 EdgeInfo(unsigned int wid, unsigned int nid, unsigned int a);
00265 operator bool(void) const;
00267 unsigned int wid(void) const;
00269 unsigned int nid(void) const;
00271 unsigned int alternative(void) const;
00273 std::string string(void) const;
00274 };
00276 enum NodeType {
00277 SOLVED = 0,
00278 FAILED = 1,
00279 BRANCH = 2
00280 };
00282 class NodeInfo {
00283 protected:
00285 NodeType _nt;
00287 unsigned int _wid;
00289 unsigned int _nid;
00291 const Space& _s;
00293 const Choice* _c;
00294 public:
00296 NodeInfo(NodeType nt,
00297 unsigned int wid, unsigned int nid,
00298 const Space& s, const Choice* c = nullptr);
00300 NodeType type(void) const;
00302 unsigned int wid(void) const;
00304 unsigned int nid(void) const;
00306 const Space& space(void) const;
00308 const Choice& choice(void) const;
00309 };
00310 private:
00312 Support::Mutex m;
00314 unsigned int pending;
00316 unsigned int n_e;
00318 unsigned int n_w;
00320 unsigned int n_active;
00322 Support::DynamicArray<EngineInfo,Heap> es;
00324 Support::DynamicArray<unsigned int,Heap> w2e;
00326 void engine(EngineType t, unsigned int n);
00328 void worker(unsigned int& wid, unsigned int& eid);
00330 void worker(void);
00332
00334 void _round(unsigned int eid);
00336 void _skip(const EdgeInfo& ei);
00338 void _node(const EdgeInfo& ei, const NodeInfo& ni);
00340 public:
00342 SearchTracer(void);
00344
00345
00346 unsigned int workers(void) const;
00348 unsigned int engines(void) const;
00350 const EngineInfo& engine(unsigned int eid) const;
00352 unsigned int eid(unsigned int wid) const;
00354
00355
00356
00357 virtual void init(void) = 0;
00359 virtual void round(unsigned int eid) = 0;
00361 virtual void skip(const EdgeInfo& ei) = 0;
00363 virtual void node(const EdgeInfo& ei, const NodeInfo& ni) = 0;
00365 virtual void done(void) = 0;
00367
00368 virtual ~SearchTracer(void);
00369 };
00370
00371 class GECODE_SEARCH_EXPORT StdSearchTracer : public SearchTracer {
00372 protected:
00374 std::ostream& os;
00376 static const char* t2s[EngineType::AOE + 1];
00377 public:
00379 StdSearchTracer(std::ostream& os = std::cerr);
00381 virtual void init(void);
00383 virtual void round(unsigned int eid);
00385 virtual void skip(const EdgeInfo& ei);
00387 virtual void node(const EdgeInfo& ei, const NodeInfo& ni);
00389 virtual void done(void);
00391 virtual ~StdSearchTracer(void);
00393 static StdSearchTracer def;
00394 };
00395
00396 }
00397
00398 #include <gecode/search/tracer.hpp>
00399 #include <gecode/search/trace-recorder.hpp>
00400
00401 #ifdef GECODE_HAS_CPPROFILER
00402
00403 namespace Gecode {
00404
00406 namespace CPProfiler {}
00407
00408 }
00409
00410 namespace Gecode { namespace CPProfiler {
00411
00413 class Connector;
00414
00415 }}
00416
00417 namespace Gecode {
00418
00420 class GECODE_SEARCH_EXPORT CPProfilerSearchTracer : public SearchTracer {
00421 public:
00423 class GECODE_SEARCH_EXPORT GetInfo : public HeapAllocated {
00424 public:
00426 GetInfo(void);
00428 virtual std::string getInfo(const Space& home) const = 0;
00430 virtual ~GetInfo(void);
00431 };
00432 private:
00434 CPProfiler::Connector* connector;
00436 int execution_id;
00438 std::string name;
00440 int restart;
00442 const GetInfo* pgi;
00443 public:
00445 CPProfilerSearchTracer(int eid, std::string name,
00446 unsigned int port = Search::Config::cpprofiler_port,
00447 const GetInfo* pgi = nullptr);
00449 virtual void init(void);
00451 virtual void round(unsigned int eid);
00453 virtual void skip(const EdgeInfo& ei);
00455 virtual void node(const EdgeInfo& ei, const NodeInfo& ni);
00457 virtual void done(void);
00459 virtual ~CPProfilerSearchTracer(void);
00460 };
00461
00462 }
00463
00464 #endif
00465
00466 namespace Gecode { namespace Search {
00467
00472 class GECODE_SEARCH_EXPORT Cutoff : public HeapAllocated {
00473 public:
00475
00476
00477 Cutoff(void);
00479 virtual unsigned long int operator ()(void) const = 0;
00481 virtual unsigned long int operator ++(void) = 0;
00483 virtual ~Cutoff(void);
00485
00486
00487
00488 static Cutoff*
00489 constant(unsigned long int scale=Config::slice);
00491 static Cutoff*
00492 linear(unsigned long int scale=Config::slice);
00496 static Cutoff*
00497 geometric(unsigned long int scale=Config::slice, double base=Config::base);
00499 static Cutoff*
00500 luby(unsigned long int scale=Config::slice);
00505 static Cutoff*
00506 rnd(unsigned int seed,
00507 unsigned long int min, unsigned long int max,
00508 unsigned long int n);
00510 static Cutoff*
00511 append(Cutoff* c1, unsigned long int n, Cutoff* c2);
00513 static Cutoff*
00514 merge(Cutoff* c1, Cutoff* c2);
00516 static Cutoff*
00517 repeat(Cutoff* c, unsigned long int n);
00519 };
00520
00525 class GECODE_SEARCH_EXPORT CutoffConstant : public Cutoff {
00526 protected:
00528 unsigned long int c;
00529 public:
00531 CutoffConstant(unsigned long int c);
00533 virtual unsigned long int operator ()(void) const;
00535 virtual unsigned long int operator ++(void);
00536 };
00537
00542 class GECODE_SEARCH_EXPORT CutoffLinear : public Cutoff {
00543 protected:
00545 unsigned long int scale;
00547 unsigned long int n;
00548 public:
00550 CutoffLinear(unsigned long int scale);
00552 virtual unsigned long int operator ()(void) const;
00554 virtual unsigned long int operator ++(void);
00555 };
00556
00561 class GECODE_SEARCH_EXPORT CutoffLuby : public Cutoff {
00562 protected:
00564 unsigned long int i;
00566 unsigned long int scale;
00568 static const unsigned long int n_start = 63U;
00570 static unsigned long int start[n_start];
00572 static unsigned long int log(unsigned long int i);
00574 static unsigned long int luby(unsigned long int i);
00575 public:
00577 CutoffLuby(unsigned long int scale);
00579 virtual unsigned long int operator ()(void) const;
00581 virtual unsigned long int operator ++(void);
00582 };
00583
00588 class GECODE_SEARCH_EXPORT CutoffGeometric : public Cutoff {
00589 protected:
00591 double n;
00593 double scale;
00595 double base;
00596 public:
00598 CutoffGeometric(unsigned long int scale, double base);
00600 virtual unsigned long int operator ()(void) const;
00602 virtual unsigned long int operator ++(void);
00603 };
00604
00609 class GECODE_SEARCH_EXPORT CutoffRandom : public Cutoff {
00610 protected:
00612 Support::RandomGenerator rnd;
00614 unsigned long int min;
00616 unsigned long int n;
00618 unsigned long int step;
00620 unsigned long int cur;
00621 public:
00623 CutoffRandom(unsigned int seed,
00624 unsigned long int min, unsigned long int max,
00625 unsigned long int n);
00627 virtual unsigned long int operator ()(void) const;
00629 virtual unsigned long int operator ++(void);
00630 };
00631
00636 class GECODE_SEARCH_EXPORT CutoffAppend : public Cutoff {
00637 protected:
00639 Cutoff* c1;
00641 Cutoff* c2;
00643 unsigned long int n;
00644 public:
00646 CutoffAppend(Cutoff* c1, unsigned long int n, Cutoff* c2);
00648 virtual unsigned long int operator ()(void) const;
00650 virtual unsigned long int operator ++(void);
00652 virtual ~CutoffAppend(void);
00653 };
00654
00659 class GECODE_SEARCH_EXPORT CutoffMerge : public Cutoff {
00660 protected:
00662 Cutoff* c1;
00664 Cutoff* c2;
00665 public:
00667 CutoffMerge(Cutoff* c1, Cutoff* c2);
00669 virtual unsigned long int operator ()(void) const;
00671 virtual unsigned long int operator ++(void);
00673 virtual ~CutoffMerge(void);
00674 };
00675
00680 class GECODE_SEARCH_EXPORT CutoffRepeat : public Cutoff {
00681 protected:
00683 Cutoff* c;
00684
00685 unsigned int cutoff;
00686
00687 unsigned long int i;
00688
00689 unsigned long int n;
00690 public:
00692 CutoffRepeat(Cutoff* c, unsigned long int n);
00694 virtual unsigned long int operator ()(void) const;
00696 virtual unsigned long int operator ++(void);
00698 virtual ~CutoffRepeat(void);
00699 };
00700
00701 }}
00702
00703 #include <gecode/search/cutoff.hpp>
00704
00705 namespace Gecode { namespace Search {
00706
00707 class Stop;
00708
00746 class Options {
00747 public:
00749 bool clone;
00751 double threads;
00753 unsigned int c_d;
00755 unsigned int a_d;
00757 unsigned int d_l;
00759 unsigned int assets;
00761 unsigned int slice;
00763 unsigned int nogoods_limit;
00765 Stop* stop;
00767 Cutoff* cutoff;
00769 SearchTracer* tracer;
00771 GECODE_SEARCH_EXPORT static const Options def;
00773 Options(void);
00775 GECODE_SEARCH_EXPORT Options
00776 expand(void) const;
00777 };
00778
00779 }}
00780
00781 #include <gecode/search/options.hpp>
00782
00783 namespace Gecode { namespace Search {
00784
00799 class GECODE_SEARCH_EXPORT Stop : public HeapAllocated {
00800 public:
00802
00803
00804 Stop(void);
00806 virtual bool stop(const Statistics& s, const Options& o) = 0;
00808 virtual ~Stop(void);
00810
00811
00812
00813 static Stop* node(unsigned long int l);
00815 static Stop* fail(unsigned long int l);
00817 static Stop* time(unsigned long int l);
00819 };
00820
00829 class GECODE_SEARCH_EXPORT NodeStop : public Stop {
00830 protected:
00832 unsigned long int l;
00833 public:
00835 NodeStop(unsigned long int l);
00837 unsigned long int limit(void) const;
00839 void limit(unsigned long int l);
00841 virtual bool stop(const Statistics& s, const Options& o);
00842 };
00843
00852 class GECODE_SEARCH_EXPORT FailStop : public Stop {
00853 protected:
00855 unsigned long int l;
00856 public:
00858 FailStop(unsigned long int l);
00860 unsigned long int limit(void) const;
00862 void limit(unsigned long int l);
00864 virtual bool stop(const Statistics& s, const Options& o);
00865 };
00866
00871 class GECODE_SEARCH_EXPORT TimeStop : public Stop {
00872 protected:
00874 Support::Timer t;
00876 unsigned long int l;
00877 public:
00879 TimeStop(unsigned long int l);
00881 unsigned long int limit(void) const;
00883 void limit(unsigned long int l);
00885 void reset(void);
00887 virtual bool stop(const Statistics& s, const Options& o);
00888 };
00889
00890 }}
00891
00892 #include <gecode/search/stop.hpp>
00893
00894 namespace Gecode { namespace Search {
00895
00899 class GECODE_SEARCH_EXPORT Engine : public HeapAllocated {
00900 public:
00902 virtual Space* next(void) = 0;
00904 virtual Statistics statistics(void) const = 0;
00906 virtual bool stopped(void) const = 0;
00908 virtual void constrain(const Space& b);
00910 virtual void reset(Space* s);
00912 virtual NoGoods& nogoods(void);
00914 virtual ~Engine(void);
00915 };
00916
00917 }}
00918
00919 #include <gecode/search/engine.hpp>
00920
00921 namespace Gecode { namespace Search {
00922
00924 template<class T>
00925 class Base : public HeapAllocated {
00926 template<class, class>
00927 friend Engine* build(Space*, const Options&);
00928 template<class, template<class> class>
00929 friend Engine* build(Space*, const Options&);
00930 protected:
00932 Engine* e;
00934 Base(Engine* e = NULL);
00935 public:
00937 virtual T* next(void);
00939 virtual Statistics statistics(void) const;
00941 virtual bool stopped(void) const;
00943 virtual ~Base(void);
00944 private:
00946 Base(const Base&);
00948 Base& operator =(const Base&);
00949 };
00950
00951 }}
00952
00953 #include <gecode/search/base.hpp>
00954
00955 namespace Gecode { namespace Search {
00956
00958 template<class T, class E>
00959 Engine* build(Space* s, const Options& opt);
00961 template<class T, template<class> class E>
00962 Engine* build(Space* s, const Options& opt);
00963
00965 class GECODE_SEARCH_EXPORT Builder : public HeapAllocated {
00966 protected:
00968 Options opt;
00970 const bool b;
00971 public:
00973 Builder(const Options& opt, bool best);
00975 Options& options(void);
00977 const Options& options(void) const;
00979 bool best(void) const;
00981 virtual Engine* operator() (Space* s) const = 0;
00983 virtual ~Builder(void);
00984 };
00985
00986 }}
00987
00988 #include <gecode/search/build.hpp>
00989
00990 namespace Gecode {
00991
00993 typedef Search::Builder* SEB;
00994
00995 }
00996
00997 #include <gecode/search/traits.hpp>
00998
00999 namespace Gecode {
01000
01002 class SEBs : public ArgArray<SEB> {
01003 public:
01005
01006
01007 SEBs(void);
01009 explicit SEBs(int n);
01011 SEBs(const std::vector<SEB>& x);
01013 SEBs(std::initializer_list<SEB> x);
01015 template<class InputIterator>
01016 SEBs(InputIterator first, InputIterator last);
01018 SEBs(const ArgArray<SEB>& a);
01020 };
01021
01022 }
01023
01024 #include <gecode/search/sebs.hpp>
01025
01026 namespace Gecode {
01027
01035 template<class T>
01036 class DFS : public Search::Base<T> {
01037 public:
01039 DFS(T* s, const Search::Options& o=Search::Options::def);
01041 static const bool best = false;
01042 };
01043
01045 template<class T>
01046 T* dfs(T* s, const Search::Options& o=Search::Options::def);
01047
01049 template<class T>
01050 SEB dfs(const Search::Options& o=Search::Options::def);
01051
01052 }
01053
01054 #include <gecode/search/dfs.hpp>
01055
01056 namespace Gecode {
01057
01069 template<class T>
01070 class BAB : public Search::Base<T> {
01071 public:
01073 BAB(T* s, const Search::Options& o=Search::Options::def);
01075 static const bool best = true;
01076 };
01077
01090 template<class T>
01091 T* bab(T* s, const Search::Options& o=Search::Options::def);
01092
01094 template<class T>
01095 SEB bab(const Search::Options& o=Search::Options::def);
01096
01097 }
01098
01099 #include <gecode/search/bab.hpp>
01100
01101 namespace Gecode {
01102
01107 template<class T>
01108 class LDS : public Search::Base<T> {
01109 public:
01111 LDS(T* s, const Search::Options& o=Search::Options::def);
01113 static const bool best = false;
01114 };
01115
01120 template<class T>
01121 T* lds(T* s, const Search::Options& o=Search::Options::def);
01122
01124 template<class T>
01125 SEB lds(const Search::Options& o=Search::Options::def);
01126
01127 }
01128
01129 #include <gecode/search/lds.hpp>
01130
01131 namespace Gecode {
01132
01151 template<class T, template<class> class E = DFS>
01152 class RBS : public Search::Base<T> {
01153 using Search::Base<T>::e;
01154 public:
01156 RBS(T* s, const Search::Options& o);
01158 static const bool best = E<T>::best;
01159 };
01160
01179 template<class T, template<class> class E>
01180 T* rbs(T* s, const Search::Options& o);
01181
01183 template<class T, template<class> class E>
01184 SEB rbs(const Search::Options& o);
01185
01186 }
01187
01188 #include <gecode/search/rbs.hpp>
01189
01190 namespace Gecode { namespace Search { namespace Meta {
01191
01193 template<class T, template<class> class E>
01194 Engine* sequential(T* master, const Search::Statistics& stat, Options& opt);
01195
01197 template<class T, template<class> class E>
01198 Engine* sequential(T* master, SEBs& sebs,
01199 const Search::Statistics& stat, Options& opt, bool best);
01200
01201 #ifdef GECODE_HAS_THREADS
01202
01204 template<class T, template<class> class E>
01205 Engine* parallel(T* master, const Search::Statistics& stat, Options& opt);
01206
01208 template<class T, template<class> class E>
01209 Engine* parallel(T* master, SEBs& sebs,
01210 const Search::Statistics& stat, Options& opt, bool best);
01211
01212 #endif
01213
01214 }}}
01215
01216 namespace Gecode {
01217
01235 template<class T, template<class> class E = DFS>
01236 class PBS : public Search::Base<T> {
01237 using Search::Base<T>::e;
01238 protected:
01240 void build(T* s, SEBs& sebs, const Search::Options& o);
01241 public:
01243 PBS(T* s, const Search::Options& o=Search::Options::def);
01245 PBS(T* s, SEBs& sebs, const Search::Options& o=Search::Options::def);
01247 PBS(T* s, SEB seb0, SEB seb1,
01248 const Search::Options& o=Search::Options::def);
01250 PBS(T* s, SEB seb0, SEB seb1, SEB seb2,
01251 const Search::Options& o=Search::Options::def);
01253 PBS(T* s, SEB seb0, SEB seb1, SEB seb2, SEB seb3,
01254 const Search::Options& o=Search::Options::def);
01256 static const bool best = E<T>::best;
01257 };
01258
01276 template<class T, template<class> class E>
01277 T* pbs(T* s, const Search::Options& o=Search::Options::def);
01278
01280 template<class T>
01281 SEB pbs(const Search::Options& o=Search::Options::def);
01282
01283 }
01284
01285 #include <gecode/search/pbs.hpp>
01286
01287 #endif
01288
01289