Generated on Fri Oct 19 11:25:14 2018 for Gecode by doxygen 1.6.3

search.hh

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *     Guido Tack <tack@gecode.org>
00006  *
00007  *  Contributing authors:
00008  *     Kevin Leo <kevin.leo@monash.edu>
00009  *     Maxim Shishmarev <maxim.shishmarev@monash.edu>
00010  * 
00011  *  Copyright:
00012  *     Kevin Leo, 2017
00013  *     Christian Schulte, 2002
00014  *     Maxim Shishmarev, 2017
00015  *     Guido Tack, 2004
00016  *
00017  *  This file is part of Gecode, the generic constraint
00018  *  development environment:
00019  *     http://www.gecode.org
00020  *
00021  *  Permission is hereby granted, free of charge, to any person obtaining
00022  *  a copy of this software and associated documentation files (the
00023  *  "Software"), to deal in the Software without restriction, including
00024  *  without limitation the rights to use, copy, modify, merge, publish,
00025  *  distribute, sublicense, and/or sell copies of the Software, and to
00026  *  permit persons to whom the Software is furnished to do so, subject to
00027  *  the following conditions:
00028  *
00029  *  The above copyright notice and this permission notice shall be
00030  *  included in all copies or substantial portions of the Software.
00031  *
00032  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00033  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00034  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00035  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00036  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00037  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00038  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
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  * Configure linking
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 // Configure auto-linking
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     // Current cutoff
00685     unsigned int cutoff;
00686     // Iteration
00687     unsigned long int i;
00688     // Number of repetitions
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 // STATISTICS: search-other