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