Generated on Sat May 25 2013 18:00:40 for Gecode by doxygen 1.8.3.1
search.hh
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  * Guido Tack <tack@gecode.org>
6  *
7  * Copyright:
8  * Christian Schulte, 2002
9  * Guido Tack, 2004
10  *
11  * Last modified:
12  * $Date: 2013-03-08 11:11:37 +0100 (Fri, 08 Mar 2013) $ by $Author: schulte $
13  * $Revision: 13482 $
14  *
15  * This file is part of Gecode, the generic constraint
16  * development environment:
17  * http://www.gecode.org
18  *
19  * Permission is hereby granted, free of charge, to any person obtaining
20  * a copy of this software and associated documentation files (the
21  * "Software"), to deal in the Software without restriction, including
22  * without limitation the rights to use, copy, modify, merge, publish,
23  * distribute, sublicense, and/or sell copies of the Software, and to
24  * permit persons to whom the Software is furnished to do so, subject to
25  * the following conditions:
26  *
27  * The above copyright notice and this permission notice shall be
28  * included in all copies or substantial portions of the Software.
29  *
30  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37  *
38  */
39 
40 #ifndef __GECODE_SEARCH_HH__
41 #define __GECODE_SEARCH_HH__
42 
43 #include <gecode/kernel.hh>
44 
45 /*
46  * Configure linking
47  *
48  */
49 #if !defined(GECODE_STATIC_LIBS) && \
50  (defined(__CYGWIN__) || defined(__MINGW32__) || defined(_MSC_VER))
51 
52 #ifdef GECODE_BUILD_SEARCH
53 #define GECODE_SEARCH_EXPORT __declspec( dllexport )
54 #else
55 #define GECODE_SEARCH_EXPORT __declspec( dllimport )
56 #endif
57 
58 #else
59 
60 #ifdef GECODE_GCC_HAS_CLASS_VISIBILITY
61 #define GECODE_SEARCH_EXPORT __attribute__ ((visibility("default")))
62 #else
63 #define GECODE_SEARCH_EXPORT
64 #endif
65 
66 #endif
67 
68 // Configure auto-linking
69 #ifndef GECODE_BUILD_SEARCH
70 #define GECODE_LIBRARY_NAME "Search"
72 #endif
73 
74 
75 namespace Gecode { namespace Search {
76 
78  namespace Sequential {}
79 
81  namespace Parallel {}
82 
84  namespace Meta {}
85 
91  namespace Config {
93  const bool clone = true;
95  const double threads = 1.0;
97  const unsigned int c_d = 8;
99  const unsigned int a_d = 2;
100 
102  const unsigned int steal_limit = 3;
104  const unsigned int initial_delay = 5;
105  }
106 
107 }}
108 
109 namespace Gecode { namespace Search {
110 
116 
118  public:
120  UninitializedCutoff(const char* l);
121  };
123 }}
124 
126 
127 namespace Gecode { namespace Search {
128 
133  class Statistics : public StatusStatistics {
134  public:
136  unsigned long int fail;
138  unsigned long int node;
140  unsigned long int depth;
142  size_t memory;
144  unsigned long int restart;
146  Statistics(void);
148  void reset(void);
150  Statistics operator +(const Statistics& s);
152  Statistics& operator +=(const Statistics& s);
153  };
154 
155 }}
156 
158 
159 namespace Gecode { namespace Search {
160 
161  class Stop;
162  class Cutoff;
163 
201  class Options {
202  public:
204  bool clone;
206  double threads;
208  unsigned int c_d;
210  unsigned int a_d;
218  Options(void);
221  expand(void) const;
222  };
223 
224 }}
225 
226 #include <gecode/search/options.hpp>
227 
228 namespace Gecode {
229 
230  template<template<class> class E, class T>
231  class RBS;
232 
233 }
234 
235 namespace Gecode { namespace Search { namespace Meta {
236 
237  class RBS;
238 
239 }}}
240 
241 namespace Gecode { namespace Search {
242 
258  public:
260  Stop(void);
262  virtual bool stop(const Statistics& s, const Options& o) = 0;
264  virtual ~Stop(void);
266  static void* operator new(size_t s);
268  static void operator delete(void* p);
269  };
270 
277  protected:
279  size_t l;
280  public:
282  MemoryStop(size_t l);
284  size_t limit(void) const;
286  void limit(size_t l);
288  virtual bool stop(const Statistics& s, const Options& o);
289  };
290 
300  protected:
302  unsigned long int l;
303  public:
305  NodeStop(unsigned long int l);
307  unsigned long int limit(void) const;
309  void limit(unsigned long int l);
311  virtual bool stop(const Statistics& s, const Options& o);
312  };
313 
323  protected:
325  unsigned long int l;
326  public:
328  FailStop(unsigned long int l);
330  unsigned long int limit(void) const;
332  void limit(unsigned long int l);
334  virtual bool stop(const Statistics& s, const Options& o);
335  };
336 
342  protected:
346  unsigned long int l;
347  public:
349  TimeStop(unsigned long int l);
351  unsigned long int limit(void) const;
353  void limit(unsigned long int l);
355  void reset(void);
357  virtual bool stop(const Statistics& s, const Options& o);
358  };
359 
365  template<template<class>class,class> friend class ::Gecode::RBS;
366  friend class ::Gecode::Search::Meta::RBS;
367  private:
369  FailStop* e_stop;
371  Stop* m_stop;
373  bool e_stopped;
375  Statistics m_stat;
376  public:
378  MetaStop(Stop* s);
380  virtual bool stop(const Statistics& s, const Options& o);
382  void limit(const Search::Statistics& s, unsigned long int l);
384  Stop* enginestop(void) const;
386  bool enginestopped(void) const;
388  Statistics metastatistics(void) const;
390  ~MetaStop(void);
391  };
392 
393 }}
394 
395 #include <gecode/search/stop.hpp>
396 
397 namespace Gecode { namespace Search {
398 
403  public:
405  Cutoff(void);
407  virtual unsigned long int operator ()(void) = 0;
409  virtual ~Cutoff(void);
411  static Cutoff*
412  constant(unsigned long int scale=1U);
414  static Cutoff*
415  linear(unsigned long int scale=1U);
419  static Cutoff*
420  geometric(unsigned long int scale=1U, double base=1.5);
422  static Cutoff*
423  luby(unsigned long int scale=1U);
428  static Cutoff*
429  rnd(unsigned int seed,
430  unsigned long int min, unsigned long int max,
431  unsigned long int n);
433  static Cutoff*
434  append(Cutoff* c1, unsigned long int n, Cutoff* c2);
436  static void* operator new(size_t s);
438  static void operator delete(void* p);
439  };
440 
441 }}
442 
443 #include <gecode/search/cutoff.hpp>
444 
445 namespace Gecode { namespace Search {
446 
450  class Engine {
451  public:
453  virtual Space* next(void) = 0;
455  virtual Statistics statistics(void) const = 0;
457  virtual bool stopped(void) const = 0;
459  virtual void reset(Space* s) = 0;
461  virtual ~Engine(void) {}
462  };
463 
464 }}
465 
466 namespace Gecode {
467 
471  class EngineBase {
472  template<template<class>class,class> friend class ::Gecode::RBS;
473  protected:
477  ~EngineBase(void);
479  EngineBase(Search::Engine* e = NULL);
480  };
481 
482 }
483 
485 
486 namespace Gecode {
487 
488 
496  template<class T>
497  class DFS : public EngineBase {
498  public:
500  DFS(T* s, const Search::Options& o=Search::Options::def);
502  T* next(void);
504  Search::Statistics statistics(void) const;
506  bool stopped(void) const;
507  };
508 
510  template<class T>
511  T* dfs(T* s, const Search::Options& o=Search::Options::def);
512 
513 }
514 
515 #include <gecode/search/dfs.hpp>
516 
517 namespace Gecode {
518 
530  template<class T>
531  class BAB : public EngineBase {
532  public:
534  BAB(T* s, const Search::Options& o=Search::Options::def);
536  T* next(void);
538  Search::Statistics statistics(void) const;
540  bool stopped(void) const;
541  };
542 
555  template<class T>
556  T* bab(T* s, const Search::Options& o=Search::Options::def);
557 
558 }
559 
560 #include <gecode/search/bab.hpp>
561 
562 namespace Gecode {
563 
582  template<template<class> class E, class T>
583  class RBS : public EngineBase {
584  public:
586  RBS(T* s, const Search::Options& o);
588  T* next(void);
590  Search::Statistics statistics(void) const;
592  bool stopped(void) const;
593  };
594 
613  template<template<class> class E, class T>
614  T* rbs(T* s, const Search::Options& o);
615 
616 }
617 
618 #include <gecode/search/rbs.hpp>
619 
620 #endif
621 
622 // STATISTICS: search-other