Generated on Wed Jan 4 17:49:13 2006 for Gecode by doxygen 1.4.6

search.hh (Revision: 2551)

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: 2005-11-14 13:28:55 +0100 (Mon, 14 Nov 2005) $ by $Author: schulte $
00012  *     $Revision: 2551 $
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 "./kernel.hh"
00028 
00029 /*
00030  * Support for DLLs under Windows
00031  *
00032  */
00033 
00034 #if !defined(GECODE_STATIC_LIBS) && \
00035     (defined(__CYGWIN__) || defined(__MINGW32__) || defined(_MSC_VER))
00036 
00037 #ifdef GECODE_BUILD_SEARCH
00038 #define GECODE_SEARCH_EXPORT __declspec( dllexport )
00039 #else
00040 #define GECODE_SEARCH_EXPORT __declspec( dllimport )
00041 #endif
00042 
00043 #else
00044 
00045 #define GECODE_SEARCH_EXPORT
00046 
00047 #endif
00048 
00049 #include "support/dynamic-stack.hh"
00050 
00051 namespace Gecode { 
00052 
00054   namespace Search {
00055 
00061     namespace Config {
00063       const unsigned int c_d = 5;
00065       const unsigned int a_d = 2;
00066     }
00067 
00072     class Statistics {
00073     public:
00075       unsigned long int propagate;
00077       unsigned long int fail;
00079       unsigned long int clone;
00081       unsigned long int commit;
00083       size_t memory;
00085       Statistics(void);
00086     };
00087     
00088     
00092     class FullStatistics : public Statistics {
00093     public:
00095       size_t mem_space;
00097       size_t mem_cur;
00099       size_t mem_total;
00101       FullStatistics(size_t sz);
00103       void push(const Space* s);
00105       void push(const Space* s, const BranchingDesc* d);
00107       void pop(const Space* s);
00109       void pop(const Space* s, const BranchingDesc* d);
00111       void current(const Space* s);
00113       void reset(const Space* s);
00114     };
00115     
00116     
00120     class PlainEngine : public FullStatistics {
00121     public:
00123       PlainEngine(size_t sz);
00125       GECODE_SEARCH_EXPORT
00126       virtual ~PlainEngine(void);
00128       virtual void reset(Space* s) = 0;
00130       virtual Space* explore(void) = 0;
00132       virtual size_t stacksize(void) const = 0;
00134       static void* operator new(size_t);
00136       static void  operator delete(void*,size_t);
00137     };
00138     
00139     
00140 
00149     class GECODE_SEARCH_EXPORT DFS {
00150     protected:
00152       PlainEngine* e;
00153     public:
00161       DFS(Space* s, unsigned int c_d, unsigned int a_d, size_t sz);
00163       ~DFS(void);
00165       Statistics statistics(void) const;
00167       Space* next(void);
00168     };
00169 
00170   }
00171 
00179   template <class T>
00180   class DFS : public Search::DFS {
00181   public:
00188     DFS(T* s, 
00189         unsigned int c_d=Search::Config::c_d, 
00190         unsigned int a_d=Search::Config::a_d);
00192     T* next(void);
00193   };
00194 
00202   template <class T>
00203   T* dfs(T* s,
00204          unsigned int c_d=Search::Config::c_d,
00205          unsigned int a_d=Search::Config::a_d);
00206 
00207 
00208 
00209   namespace Search {
00210 
00215     class ProbeEngine : public FullStatistics {
00216     protected:
00218       class Node {
00219       private:
00221         Space*       _space;
00223         unsigned int _alt;
00224       public:
00226         Node(Space* s, unsigned int a);
00228         Space* space(void) const; 
00230         void space(Space* s);
00232         unsigned int alt(void) const; 
00234         void alt(unsigned int a);
00235       };
00237       Support::DynamicStack<Node> ds;
00239       Space* cur;
00241       unsigned int d;
00242     public:
00244       ProbeEngine(size_t s);
00246       void init(Space* s, unsigned int d);
00248       void reset(Space* s, unsigned int d);
00250       size_t stacksize(void) const;
00252       ~ProbeEngine(void);
00254       Space* explore(void);
00255     };
00256 
00260     class LDS {
00261     protected:
00262       Space*       root;        
00263       unsigned int d_cur;       
00264       unsigned int d_max;       
00265       bool         no_solution; 
00266       ProbeEngine  e;           
00267     public:
00273       GECODE_SEARCH_EXPORT LDS(Space* s, unsigned int d, size_t sz);
00275       GECODE_SEARCH_EXPORT ~LDS(void);
00277       GECODE_SEARCH_EXPORT Statistics statistics(void) const;
00279       GECODE_SEARCH_EXPORT Space* next(void);
00280     };
00281 
00282   }
00283 
00288   template <class T>
00289   class LDS : public Search::LDS {
00290   public:
00295     LDS(T* s, unsigned int d);
00297     T* next(void);
00298   };
00299 
00306   template <class T>
00307   T* lds(T* s,unsigned int d);
00308 
00309 
00310 
00311 
00312 
00313   /*
00314    * Best solution search engines
00315    *
00316    */
00317 
00318   namespace Search {
00319 
00323     class BabEngine : public FullStatistics {
00324     public:
00326       BabEngine(size_t sz);
00328       GECODE_SEARCH_EXPORT virtual ~BabEngine(void);
00339       virtual bool explore(Space*& s1, Space*& s2) = 0;
00341       virtual size_t stacksize(void) const = 0;
00343       static void* operator new(size_t);
00345       static void  operator delete(void*,size_t);
00346     };
00347 
00357     class GECODE_SEARCH_EXPORT BAB {
00358     protected:
00360       BabEngine* e;
00361     public:
00369       BAB(Space* s, unsigned int c_d, unsigned int a_d, size_t sz);
00371       ~BAB(void);
00373       Statistics statistics(void) const;
00374     };
00375 
00376   }
00377   
00382   template <class T>
00383   class BAB : public Search::BAB {
00384   public:
00397     BAB(T* s,
00398         unsigned int c_d=Search::Config::c_d,
00399         unsigned int a_d=Search::Config::a_d);
00401     T* next(void);
00402   };
00403 
00417   template <class T>
00418   T* bab(T* s,
00419          unsigned int c_d=Search::Config::c_d,
00420          unsigned int a_d=Search::Config::a_d);
00421 
00422 
00423 
00428   template <class T>
00429   class Restart : public DFS<T> {
00430   protected:
00432     Space* root;
00434     Space* best;
00435   public:
00448     Restart(T* s, 
00449             unsigned int c_d=Search::Config::c_d, 
00450             unsigned int a_d=Search::Config::a_d);
00452     ~Restart(void);
00454     T* next(void);
00455   };
00456 
00469   template <class T>
00470   T* restart(T* s,
00471              unsigned int c_d=Search::Config::c_d,
00472              unsigned int a_d=Search::Config::a_d);
00473 
00474 }
00475 
00476 #include "search/statistics.icc"
00477 #include "search/plain.icc"
00478 #include "search/dfs.icc"
00479 #include "search/lds.icc"
00480 #include "search/bab.icc"
00481 #include "search/restart.icc"
00482 
00483 #endif
00484 
00485 // STATISTICS: search-any