Generated on Thu Jul 6 07:06:48 2006 for Gecode by doxygen 1.4.7

search.hh

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *     Guido Tack <tack@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2002
00008  *     Guido Tack, 2004
00009  *
00010  *  Last modified:
00011  *     $Date: 2006-05-17 16:00:08 +0200 (Wed, 17 May 2006) $ by $Author: schulte $
00012  *     $Revision: 3226 $
00013  *
00014  *  This file is part of Gecode, the generic constraint
00015  *  development environment:
00016  *     http://www.gecode.org
00017  *
00018  *  See the file "LICENSE" for information on usage and
00019  *  redistribution of this file, and for a
00020  *     DISCLAIMER OF ALL WARRANTIES.
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  * Support for DLLs under Windows
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    * Best solution search engines
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 // STATISTICS: search-any