Generated on Tue Jul 27 2010 21:59:18 for Gecode by doxygen 1.7.1

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: 2009-11-02 09:45:08 +0100 (Mon, 02 Nov 2009) $ by $Author: tack $
00013  *     $Revision: 10017 $
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 <gecode/kernel.hh>
00044 
00045 /*
00046  * Configure linking
00047  *
00048  */
00049 #if !defined(GECODE_STATIC_LIBS) && \
00050     (defined(__CYGWIN__) || defined(__MINGW32__) || defined(_MSC_VER))
00051 
00052 #ifdef GECODE_BUILD_SEARCH
00053 #define GECODE_SEARCH_EXPORT __declspec( dllexport )
00054 #else
00055 #define GECODE_SEARCH_EXPORT __declspec( dllimport )
00056 #endif
00057 
00058 #else
00059 
00060 #ifdef GECODE_GCC_HAS_CLASS_VISIBILITY
00061 #define GECODE_SEARCH_EXPORT __attribute__ ((visibility("default")))
00062 #else
00063 #define GECODE_SEARCH_EXPORT
00064 #endif
00065 
00066 #endif
00067 
00068 // Configure auto-linking
00069 #ifndef GECODE_BUILD_SEARCH
00070 #define GECODE_LIBRARY_NAME "Search"
00071 #include <gecode/support/auto-link.hpp>
00072 #endif
00073 
00074 
00075 namespace Gecode {
00076 
00078   namespace Search {
00079 
00085     namespace Config {
00087       const bool clone = true;
00089       const double threads = 1.0;
00091       const unsigned int c_d = 8;
00093       const unsigned int a_d = 2;
00095       const unsigned int d = 5;
00096 
00098       const unsigned int steal_limit = 3;
00100       const unsigned int initial_delay = 5;
00101     }
00102 
00107     class Statistics : public StatusStatistics {
00108     public:
00110       unsigned long int fail;
00112       unsigned long int node;
00114       unsigned long int depth;
00116       size_t memory;
00118       Statistics(void);
00120       void reset(void);
00122       Statistics operator +(const Statistics& s);
00124       Statistics& operator +=(const Statistics& s);
00125     };
00126 
00127     class Stop;
00128 
00166     class Options {
00167     public:
00169       bool clone;
00171       double threads;
00173       unsigned int c_d;
00175       unsigned int a_d;
00177       unsigned int d;
00179       Stop* stop;
00181       GECODE_SEARCH_EXPORT static const Options def;
00183       Options(void);
00185       GECODE_SEARCH_EXPORT Options
00186       expand(void) const;
00187     };
00188 
00203     class GECODE_SEARCH_EXPORT Stop {
00204     public:
00206       Stop(void);
00208       virtual bool stop(const Statistics& s, const Options& o) = 0;
00210       virtual ~Stop(void);
00211     };
00212 
00218     class GECODE_SEARCH_EXPORT MemoryStop : public Stop {
00219     protected:
00221       size_t l;
00222     public:
00224       MemoryStop(size_t l);
00226       size_t limit(void) const;
00228       void limit(size_t l);
00230       virtual bool stop(const Statistics& s, const Options& o);
00231     };
00232 
00241     class GECODE_SEARCH_EXPORT NodeStop : public Stop {
00242     protected:
00244       unsigned long int l;
00245     public:
00247       NodeStop(unsigned long int l);
00249       unsigned long int limit(void) const;
00251       void limit(unsigned long int l);
00253       virtual bool stop(const Statistics& s, const Options& o);
00254     };
00255 
00264     class GECODE_SEARCH_EXPORT FailStop : public Stop {
00265     protected:
00267       unsigned long int l;
00268     public:
00270       FailStop(unsigned long int l);
00272       unsigned long int limit(void) const;
00274       void limit(unsigned long int l);
00276       virtual bool stop(const Statistics& s, const Options& o);
00277     };
00278 
00283     class GECODE_SEARCH_EXPORT TimeStop : public Stop {
00284     protected:
00286       Support::Timer t;
00288       unsigned long int l;
00289     public:
00291       TimeStop(unsigned long int l);
00293       unsigned long int limit(void) const;
00295       void limit(unsigned long int l);
00297       void reset(void);
00299       virtual bool stop(const Statistics& s, const Options& o);
00300     };
00301 
00302 
00306     class Engine {
00307     public:
00309       virtual Space* next(void) = 0;
00311       virtual Search::Statistics statistics(void) const = 0;
00313       virtual bool stopped(void) const = 0;
00315       virtual ~Engine(void) {}
00316     };
00317 
00319     namespace Sequential {}
00320 
00322     namespace Parallel {}
00323 
00324   }
00325 
00326 }
00327 
00328 #include <gecode/search/statistics.hpp>
00329 #include <gecode/search/stop.hpp>
00330 #include <gecode/search/options.hpp>
00331 
00332 namespace Gecode {
00333 
00341   template<class T>
00342   class DFS {
00343   private:
00345     Search::Engine* e;
00346   public:
00348     DFS(T* s, const Search::Options& o=Search::Options::def);
00350     T* next(void);
00352     Search::Statistics statistics(void) const;
00354     bool stopped(void) const;
00356     ~DFS(void);
00357   };
00358 
00360   template<class T>
00361   T* dfs(T* s, const Search::Options& o=Search::Options::def);
00362 
00363 
00364 
00376   template<class T>
00377   class BAB {
00378   private:
00380     Search::Engine* e;
00381   public:
00383     BAB(T* s, const Search::Options& o=Search::Options::def);
00385     T* next(void);
00387     Search::Statistics statistics(void) const;
00389     bool stopped(void) const;
00391     ~BAB(void);
00392   };
00393 
00406   template<class T>
00407   T* bab(T* s, const Search::Options& o=Search::Options::def);
00408 
00409 
00410 
00422   template<class T>
00423   class Restart {
00424   private:
00426     Search::Engine* e;
00427   public:
00429     Restart(T* s, const Search::Options& o=Search::Options::def);
00431     T* next(void);
00433     Search::Statistics statistics(void) const;
00435     bool stopped(void) const;
00437     ~Restart(void);
00438   };
00439 
00451   template<class T>
00452   T* restart(T* s, const Search::Options& o=Search::Options::def);
00453 
00454 
00455 
00460   template<class T>
00461   class LDS {
00462   private:
00464     Search::Engine* e;
00465   public:
00467     LDS(T* s, const Search::Options& o=Search::Options::def);
00469     T* next(void);
00471     Search::Statistics statistics(void) const;
00473     bool stopped(void) const;
00475     ~LDS(void);
00476   };
00477 
00482   template<class T>
00483   T* lds(T* s, const Search::Options& o=Search::Options::def);
00484 
00485 }
00486 
00487 #include <gecode/search/dfs.hpp>
00488 #include <gecode/search/bab.hpp>
00489 #include <gecode/search/restart.hpp>
00490 #include <gecode/search/lds.hpp>
00491 
00492 #endif
00493 
00494 // STATISTICS: search-other