Generated on Wed Nov 5 2014 05:18:30 for Gecode by doxygen 1.7.6.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: 2013-10-30 15:42:34 +0100 (Wed, 30 Oct 2013) $ by $Author: schulte $
00013  *     $Revision: 14037 $
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 { namespace Search {
00076 
00078   namespace Sequential {}
00079   
00081   namespace Parallel {}
00082 
00084   namespace Meta {}
00085 
00091   namespace Config {
00093     const bool clone = true;
00095     const double threads = 1.0;
00097     const unsigned int c_d = 8;
00099     const unsigned int a_d = 2;
00100     
00102     const unsigned int steal_limit = 3;
00104     const unsigned int initial_delay = 5;
00105 
00107     const unsigned int nogoods_limit = 128;
00108   }
00109 
00110 }}
00111 
00112 namespace Gecode { namespace Search {
00113 
00119 
00120   class GECODE_VTABLE_EXPORT UninitializedCutoff : public Exception {
00121   public:
00123     UninitializedCutoff(const char* l);
00124   };
00126 }}
00127 
00128 #include <gecode/search/exception.hpp>
00129 
00130 namespace Gecode { namespace Search {
00131 
00136   class Statistics : public StatusStatistics {
00137   public:
00139     unsigned long int fail;
00141     unsigned long int node;
00143     unsigned long int depth;
00145     unsigned long int restart;
00147     unsigned long int nogood;
00149     Statistics(void);
00151     void reset(void);
00153     Statistics operator +(const Statistics& s);
00155     Statistics& operator +=(const Statistics& s);
00156   };
00157 
00158 }}
00159 
00160 #include <gecode/search/statistics.hpp>
00161 
00162 namespace Gecode { namespace Search {
00163 
00164     class Stop;
00165     class Cutoff;
00166 
00204     class Options {
00205     public:
00207       bool clone;
00209       double threads;
00211       unsigned int c_d;
00213       unsigned int a_d;
00215       unsigned int nogoods_limit;
00217       Stop* stop;
00219       Cutoff* cutoff;
00221       GECODE_SEARCH_EXPORT static const Options def;
00223       Options(void);
00225       GECODE_SEARCH_EXPORT Options
00226       expand(void) const;
00227     };
00228 
00229 }}
00230 
00231 #include <gecode/search/options.hpp>
00232 
00233 namespace Gecode {
00234 
00235   template<template<class> class E, class T>
00236   class RBS;
00237 
00238 }
00239 
00240 namespace Gecode { namespace Search { namespace Meta {
00241 
00242   class RBS;
00243 
00244 }}}
00245 
00246 namespace Gecode { namespace Search {
00247 
00262   class GECODE_SEARCH_EXPORT Stop {
00263   public:
00265     Stop(void);
00267     virtual bool stop(const Statistics& s, const Options& o) = 0;
00269     virtual ~Stop(void);
00271     static void* operator new(size_t s);
00273     static void  operator delete(void* p);
00274   };
00275   
00284   class GECODE_SEARCH_EXPORT NodeStop : public Stop {
00285   protected:
00287     unsigned long int l;
00288   public:
00290     NodeStop(unsigned long int l);
00292     unsigned long int limit(void) const;
00294     void limit(unsigned long int l);
00296     virtual bool stop(const Statistics& s, const Options& o);
00297   };
00298 
00307   class GECODE_SEARCH_EXPORT FailStop : public Stop {
00308   protected:
00310     unsigned long int l;
00311   public:
00313     FailStop(unsigned long int l);
00315     unsigned long int limit(void) const;
00317     void limit(unsigned long int l);
00319     virtual bool stop(const Statistics& s, const Options& o);
00320   };
00321   
00326   class GECODE_SEARCH_EXPORT TimeStop : public Stop {
00327   protected:
00329     Support::Timer t;
00331     unsigned long int l;
00332   public:
00334     TimeStop(unsigned long int l);
00336     unsigned long int limit(void) const;
00338     void limit(unsigned long int l);
00340     void reset(void);
00342     virtual bool stop(const Statistics& s, const Options& o);
00343   };
00344 
00349   class GECODE_SEARCH_EXPORT MetaStop : public Stop {
00350     template<template<class>class,class> friend class ::Gecode::RBS;
00351     friend class ::Gecode::Search::Meta::RBS;
00352   private:
00354     FailStop* e_stop;
00356     Stop* m_stop;
00358     bool e_stopped;
00360     Statistics m_stat;
00361   public:
00363     MetaStop(Stop* s);
00365     virtual bool stop(const Statistics& s, const Options& o);
00367     void limit(const Search::Statistics& s, unsigned long int l);
00369     void update(const Search::Statistics& s);
00371     Stop* enginestop(void) const;
00373     bool enginestopped(void) const;
00375     Statistics metastatistics(void) const;
00377     ~MetaStop(void);
00378   };
00379 
00380 }}
00381 
00382 #include <gecode/search/stop.hpp>
00383 
00384 namespace Gecode { namespace Search {
00385 
00389   class GECODE_SEARCH_EXPORT Cutoff {
00390   public:
00392     Cutoff(void);
00394     virtual unsigned long int operator ()(void) = 0;
00396     virtual ~Cutoff(void);
00398     static Cutoff*
00399     constant(unsigned long int scale=1U);
00401     static Cutoff*
00402     linear(unsigned long int scale=1U);
00406     static Cutoff*
00407     geometric(unsigned long int scale=1U, double base=1.5);
00409     static Cutoff*
00410     luby(unsigned long int scale=1U);
00415     static Cutoff*
00416     rnd(unsigned int seed, 
00417         unsigned long int min, unsigned long int max, 
00418         unsigned long int n);
00420     static Cutoff*
00421     append(Cutoff* c1, unsigned long int n, Cutoff* c2);
00423     static Cutoff*
00424     repeat(Cutoff* c, unsigned long int n);
00426     static void* operator new(size_t s);
00428     static void  operator delete(void* p);
00429   };
00430     
00431 }}
00432 
00433 #include <gecode/search/cutoff.hpp>
00434 
00435 namespace Gecode { namespace Search {
00436 
00440   class Engine {
00441   public:
00443     virtual Space* next(void) = 0;
00445     virtual Statistics statistics(void) const = 0;
00447     virtual bool stopped(void) const = 0;
00449     virtual void reset(Space* s) = 0;
00451     virtual NoGoods& nogoods(void) = 0;
00453     virtual ~Engine(void) {}
00454   };
00455 
00456 }}
00457 
00458 namespace Gecode {
00459 
00463   class EngineBase {
00464     template<template<class>class,class> friend class ::Gecode::RBS;
00465   protected:
00467     Search::Engine* e;
00469     ~EngineBase(void);
00471     EngineBase(Search::Engine* e = NULL);
00472   };
00473 
00474 }
00475 
00476 #include <gecode/search/engine-base.hpp>
00477 
00478 namespace Gecode {
00479 
00480 
00488   template<class T>
00489   class DFS : public EngineBase {
00490   public:
00492     DFS(T* s, const Search::Options& o=Search::Options::def);
00494     T* next(void);
00496     Search::Statistics statistics(void) const;
00498     bool stopped(void) const;
00500     NoGoods& nogoods(void);
00501   };
00502 
00504   template<class T>
00505   T* dfs(T* s, const Search::Options& o=Search::Options::def);
00506 
00507 }
00508 
00509 #include <gecode/search/dfs.hpp>
00510 
00511 namespace Gecode {
00512 
00524   template<class T>
00525   class BAB : public EngineBase {
00526   public:
00528     BAB(T* s, const Search::Options& o=Search::Options::def);
00530     T* next(void);
00532     Search::Statistics statistics(void) const;
00534     bool stopped(void) const;
00536     NoGoods& nogoods(void);
00537   };
00538 
00551   template<class T>
00552   T* bab(T* s, const Search::Options& o=Search::Options::def);
00553 
00554 }
00555 
00556 #include <gecode/search/bab.hpp>
00557 
00558 namespace Gecode {
00559 
00578   template<template<class> class E, class T>
00579   class RBS : public EngineBase {
00580   public:
00582     RBS(T* s, const Search::Options& o);
00584     T* next(void);
00586     Search::Statistics statistics(void) const;
00588     bool stopped(void) const;
00589   };
00590 
00609   template<template<class> class E, class T>
00610   T* rbs(T* s, const Search::Options& o);
00611 
00612 }
00613 
00614 #include <gecode/search/rbs.hpp>
00615 
00616 #endif
00617 
00618 // STATISTICS: search-other