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: 2010-10-09 13:58:12 +0200 (Sat, 09 Oct 2010) $ by $Author: schulte $ 00013 * $Revision: 11498 $ 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; 00094 00096 const unsigned int steal_limit = 3; 00098 const unsigned int initial_delay = 5; 00099 } 00100 00105 class Statistics : public StatusStatistics { 00106 public: 00108 unsigned long int fail; 00110 unsigned long int node; 00112 unsigned long int depth; 00114 size_t memory; 00116 Statistics(void); 00118 void reset(void); 00120 Statistics operator +(const Statistics& s); 00122 Statistics& operator +=(const Statistics& s); 00123 }; 00124 00125 class Stop; 00126 00164 class Options { 00165 public: 00167 bool clone; 00169 double threads; 00171 unsigned int c_d; 00173 unsigned int a_d; 00175 Stop* stop; 00177 GECODE_SEARCH_EXPORT static const Options def; 00179 Options(void); 00181 GECODE_SEARCH_EXPORT Options 00182 expand(void) const; 00183 }; 00184 00199 class GECODE_SEARCH_EXPORT Stop { 00200 public: 00202 Stop(void); 00204 virtual bool stop(const Statistics& s, const Options& o) = 0; 00206 virtual ~Stop(void); 00207 }; 00208 00214 class GECODE_SEARCH_EXPORT MemoryStop : public Stop { 00215 protected: 00217 size_t l; 00218 public: 00220 MemoryStop(size_t l); 00222 size_t limit(void) const; 00224 void limit(size_t l); 00226 virtual bool stop(const Statistics& s, const Options& o); 00227 }; 00228 00237 class GECODE_SEARCH_EXPORT NodeStop : public Stop { 00238 protected: 00240 unsigned long int l; 00241 public: 00243 NodeStop(unsigned long int l); 00245 unsigned long int limit(void) const; 00247 void limit(unsigned long int l); 00249 virtual bool stop(const Statistics& s, const Options& o); 00250 }; 00251 00260 class GECODE_SEARCH_EXPORT FailStop : public Stop { 00261 protected: 00263 unsigned long int l; 00264 public: 00266 FailStop(unsigned long int l); 00268 unsigned long int limit(void) const; 00270 void limit(unsigned long int l); 00272 virtual bool stop(const Statistics& s, const Options& o); 00273 }; 00274 00279 class GECODE_SEARCH_EXPORT TimeStop : public Stop { 00280 protected: 00282 Support::Timer t; 00284 unsigned long int l; 00285 public: 00287 TimeStop(unsigned long int l); 00289 unsigned long int limit(void) const; 00291 void limit(unsigned long int l); 00293 void reset(void); 00295 virtual bool stop(const Statistics& s, const Options& o); 00296 }; 00297 00298 00302 class Engine { 00303 public: 00305 virtual Space* next(void) = 0; 00307 virtual Search::Statistics statistics(void) const = 0; 00309 virtual bool stopped(void) const = 0; 00311 virtual ~Engine(void) {} 00312 }; 00313 00315 namespace Sequential {} 00316 00318 namespace Parallel {} 00319 00320 } 00321 00322 } 00323 00324 #include <gecode/search/statistics.hpp> 00325 #include <gecode/search/stop.hpp> 00326 #include <gecode/search/options.hpp> 00327 00328 namespace Gecode { 00329 00337 template<class T> 00338 class DFS { 00339 private: 00341 Search::Engine* e; 00342 public: 00344 DFS(T* s, const Search::Options& o=Search::Options::def); 00346 T* next(void); 00348 Search::Statistics statistics(void) const; 00350 bool stopped(void) const; 00352 ~DFS(void); 00353 }; 00354 00356 template<class T> 00357 T* dfs(T* s, const Search::Options& o=Search::Options::def); 00358 00359 00360 00372 template<class T> 00373 class BAB { 00374 private: 00376 Search::Engine* e; 00377 public: 00379 BAB(T* s, const Search::Options& o=Search::Options::def); 00381 T* next(void); 00383 Search::Statistics statistics(void) const; 00385 bool stopped(void) const; 00387 ~BAB(void); 00388 }; 00389 00402 template<class T> 00403 T* bab(T* s, const Search::Options& o=Search::Options::def); 00404 00405 00406 00418 template<class T> 00419 class Restart { 00420 private: 00422 Search::Engine* e; 00423 public: 00425 Restart(T* s, const Search::Options& o=Search::Options::def); 00427 T* next(void); 00429 Search::Statistics statistics(void) const; 00431 bool stopped(void) const; 00433 ~Restart(void); 00434 }; 00435 00447 template<class T> 00448 T* restart(T* s, const Search::Options& o=Search::Options::def); 00449 00450 } 00451 00452 #include <gecode/search/dfs.hpp> 00453 #include <gecode/search/bab.hpp> 00454 #include <gecode/search/restart.hpp> 00455 00456 #endif 00457 00458 // STATISTICS: search-other