Generated on Wed Mar 19 07:30:01 2008 for Gecode by doxygen 1.5.5

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  *  Copyright:
00008  *     Christian Schulte, 2002
00009  *     Guido Tack, 2004
00010  *
00011  *  Last modified:
00012  *     $Date: 2008-02-29 01:09:17 +0100 (Fri, 29 Feb 2008) $ by $Author: schulte $
00013  *     $Revision: 6355 $
00014  *
00015  *  This file is part of Gecode, the generic constraint
00016  *  development environment:
00017  *     http://www.gecode.org
00018  *
00019  *  Permission is hereby granted, free of charge, to any person obtaining
00020  *  a copy of this software and associated documentation files (the
00021  *  "Software"), to deal in the Software without restriction, including
00022  *  without limitation the rights to use, copy, modify, merge, publish,
00023  *  distribute, sublicense, and/or sell copies of the Software, and to
00024  *  permit persons to whom the Software is furnished to do so, subject to
00025  *  the following conditions:
00026  *
00027  *  The above copyright notice and this permission notice shall be
00028  *  included in all copies or substantial portions of the Software.
00029  *
00030  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00031  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00032  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00033  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00034  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00035  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00036  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00037  *
00038  */
00039 
00040 #ifndef __GECODE_SEARCH_HH__
00041 #define __GECODE_SEARCH_HH__
00042 
00043 #include <ctime>
00044 
00045 #include "gecode/kernel.hh"
00046 
00047 /*
00048  * Configure linking
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 namespace Gecode {
00071 
00073   namespace Search {
00074 
00080     namespace Config {
00082       const unsigned int c_d = 8;
00084       const unsigned int a_d = 2;
00085     }
00086 
00091     class Statistics {
00092     public:
00094       unsigned long int propagate;
00096       unsigned long int fail;
00098       unsigned long int clone;
00100       unsigned long int commit;
00102       size_t memory;
00104       Statistics(void);
00105     };
00106 
00107 
00122     class GECODE_SEARCH_EXPORT Stop {
00123     public:
00125       Stop(void);
00127       virtual bool stop(const Statistics& s) = 0;
00129       virtual ~Stop(void);
00130     };
00131 
00137     class GECODE_SEARCH_EXPORT MemoryStop : public Stop {
00138     protected:
00140       size_t l;
00141     public:
00143       MemoryStop(size_t l);
00145       size_t limit(void) const;
00147       void limit(size_t l);
00149       virtual bool stop(const Statistics& s);
00150     };
00151 
00160     class GECODE_SEARCH_EXPORT FailStop : public Stop {
00161     protected:
00163       unsigned long int l;
00164     public:
00166       FailStop(unsigned long int l);
00168       unsigned long int limit(void) const;
00170       void limit(unsigned long int l);
00172       virtual bool stop(const Statistics& s);
00173     };
00174 
00179     class GECODE_SEARCH_EXPORT TimeStop : public Stop {
00180     protected:
00182       clock_t s;
00184       unsigned long int l;
00185     public:
00187       TimeStop(unsigned long int l);
00189       unsigned long int limit(void) const;
00191       void limit(unsigned long int l);
00193       void reset(void);
00195       virtual bool stop(const Statistics& s);
00196     };
00197 
00224     class Options {
00225     public:
00227       unsigned int c_d;
00229       unsigned int a_d;
00231       Stop* stop;
00233       GECODE_SEARCH_EXPORT static const Options def;
00235       Options(void);
00236     };
00237 
00241     class EngineCtrl : public Statistics {
00242     protected:
00244       Stop* st;
00246       bool _stopped;
00248       size_t mem_space;
00250       size_t mem_cur;
00252       size_t mem_total;
00253     public:
00255       EngineCtrl(Stop* st, size_t sz);
00257       void start(void);
00259       bool stop(size_t sz);
00261       bool stopped(void) const;
00263       void push(const Space* s, const BranchingDesc* d);
00265       void constrained(const Space* s1, const Space* s2);
00267       void adapt(const Space* s);
00269       void pop(const Space* s, const BranchingDesc* d);
00271       void lao(const Space* s);
00273       void current(const Space* s);
00275       void reset(const Space* s);
00277       void reset(void);
00278     };
00279 
00284     class ReCoNode {
00285     protected:
00287       Space*               _space;
00289       unsigned int         _alt;
00291       const BranchingDesc* _desc;
00292     public:
00294       ReCoNode(Space* s, Space* c);
00295 
00297       Space* space(void) const;
00299       void space(Space* s);
00300 
00302       const BranchingDesc* desc(void) const;
00303 
00305       unsigned int alt(void) const;
00307       bool rightmost(void) const;
00309       void next(void);
00310 
00312       void dispose(void);
00313     };
00314 
00315 
00329     class ReCoStack {
00330     private:
00332       Support::DynamicStack<ReCoNode> ds;
00334       const unsigned int a_d;
00335     public:
00337       ReCoStack(unsigned int a_d);
00339       const BranchingDesc* push(Space* s, Space* c);
00341       bool next(EngineCtrl& s);
00343       int lc(Space*& s) const;
00345       void unwind(int l);
00347       void commit(Space* s, int i) const;
00355       template <bool constrained>
00356       Space* recompute(unsigned int& d, EngineCtrl& s);
00358       int entries(void) const;
00360       size_t stacksize(void) const;
00362       void reset(void);
00363     };
00364 
00369     class DfsEngine : public EngineCtrl {
00370     private:
00372       ReCoStack          rcs;
00374       Space*             cur;
00376       const unsigned int c_d;
00378       unsigned int       d;
00379     public:
00387       DfsEngine(unsigned int c_d, unsigned int a_d, Stop* st, size_t sz);
00389       void init(Space* s);
00391       void reset(Space* s);
00393       void reset(void);
00395       Space* explore(void);
00397       size_t stacksize(void) const;
00399       ~DfsEngine(void);
00400     };
00401 
00410     class GECODE_SEARCH_EXPORT DFS {
00411     protected:
00413       DfsEngine e;
00414     public:
00423       DFS(Space* s, unsigned int c_d, unsigned int a_d, Stop* st, size_t sz);
00425       Space* next(void);
00427       Statistics statistics(void) const;
00429       bool stopped(void) const;
00430     };
00431 
00432   }
00433 
00441   template <class T>
00442   class DFS : public Search::DFS {
00443   public:
00445     DFS(T* s, const Search::Options& o=Search::Options::def);
00447     T* next(void);
00448   };
00449 
00451   template <class T>
00452   T* dfs(T* s, const Search::Options& o=Search::Options::def);
00453 
00454 
00455   namespace Search {
00456 
00461     class ProbeEngine : public EngineCtrl {
00462     protected:
00464       class ProbeNode {
00465       private:
00467         Space*               _space;
00469         const BranchingDesc* _desc;
00471         unsigned int         _alt;
00472       public:
00474         ProbeNode(Space* s, const BranchingDesc* d, unsigned int a);
00476         Space* space(void) const;
00478         const BranchingDesc* desc(void) const;
00480         unsigned int alt(void) const;
00482         void next(void);
00483       };
00485       Support::DynamicStack<ProbeNode> ds;
00487       Space* cur;
00489       unsigned int d;
00491       bool exhausted;
00492     public:
00494       ProbeEngine(Stop* st, size_t s);
00496       void init(Space* s, unsigned int d);
00498       void reset(Space* s, unsigned int d);
00500       size_t stacksize(void) const;
00502       ~ProbeEngine(void);
00504       Space* explore(void);
00506       bool done(void) const;
00507     };
00508 
00512     class GECODE_SEARCH_EXPORT LDS {
00513     protected:
00514       Space*       root;        
00515       unsigned int d_cur;       
00516       unsigned int d_max;       
00517       bool         no_solution; 
00518       ProbeEngine  e;           
00519     public:
00526       LDS(Space* s, unsigned int d, Stop* st, size_t sz);
00528       Space* next(void);
00530       Statistics statistics(void) const;
00532       bool stopped(void) const;
00534       ~LDS(void);
00535     };
00536 
00537   }
00538 
00543   template <class T>
00544   class LDS : public Search::LDS {
00545   public:
00547     LDS(T* s, unsigned int d,
00548         const Search::Options& o=Search::Options::def);
00550     T* next(void);
00551   };
00552 
00557   template <class T>
00558   T* lds(T* s, unsigned int d,
00559          const Search::Options& o=Search::Options::def);
00560 
00561 
00562 
00563 
00564 
00565   /*
00566    * Best solution search engines
00567    *
00568    */
00569 
00570   namespace Search {
00571 
00575     class BabEngine : public EngineCtrl {
00576     public:
00578       enum ExploreStatus {
00579         ES_SOLUTION,
00580         ES_CONSTRAIN
00581       };
00582     private:
00584       ReCoStack          rcs;
00586       Space*             cur;
00588       int                mark;
00590       ExploreStatus      es;
00592       Space*             best;
00594       const unsigned int c_d;
00596       unsigned int       d;
00597     public:
00605       BabEngine(unsigned int c_d, unsigned int a_d, Stop* st, size_t sz);
00607       void init(Space* s);
00619       GECODE_SEARCH_EXPORT
00620       ExploreStatus explore(Space*& s1, Space*& s2);
00622       size_t stacksize(void) const;
00624       ~BabEngine(void);
00625     };
00626 
00636     class GECODE_SEARCH_EXPORT BAB {
00637     protected:
00639       BabEngine e;
00640     public:
00649       BAB(Space* s, unsigned int c_d, unsigned int a_d, Stop* st, size_t sz);
00651       bool stopped(void) const;
00653       Statistics statistics(void) const;
00654     };
00655 
00656   }
00657 
00669   template <class T>
00670   class BAB : public Search::BAB {
00671   public:
00673     BAB(T* s, const Search::Options& o=Search::Options::def);
00675     T* next(void);
00676   };
00677 
00690   template <class T>
00691   T* bab(T* s, const Search::Options& o=Search::Options::def);
00692 
00693 
00694 
00706   template <class T>
00707   class Restart : public DFS<T> {
00708   protected:
00710     Space* root;
00712     Space* best;
00713   public:
00715     Restart(T* s, const Search::Options& o=Search::Options::def);
00717     ~Restart(void);
00719     T* next(void);
00720   };
00721 
00733   template <class T>
00734   T* restart(T* s, const Search::Options& o=Search::Options::def);
00735 
00736 }
00737 
00738 #include "gecode/search/statistics.icc"
00739 #include "gecode/search/stop.icc"
00740 #include "gecode/search/options.icc"
00741 #include "gecode/search/engine-ctrl.icc"
00742 
00743 #include "gecode/search/reco-stack.icc"
00744 
00745 #include "gecode/search/dfs.icc"
00746 #include "gecode/search/lds.icc"
00747 #include "gecode/search/bab.icc"
00748 #include "gecode/search/restart.icc"
00749 
00750 #endif
00751 
00752 // STATISTICS: search-any