Generated on Tue Oct 22 2013 00:49:07 for Gecode by doxygen 1.8.4
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-07-11 12:30:18 +0200 (Thu, 11 Jul 2013) $ by $Author: schulte $
13  * $Revision: 13840 $
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 
107  const unsigned int nogoods_limit = 128;
108  }
109 
110 }}
111 
112 namespace Gecode { namespace Search {
113 
119  class GECODE_VTABLE_EXPORT UninitializedCutoff : public Exception {
121  public:
123  UninitializedCutoff(const char* l);
124  };
126 }}
127 
129 
130 namespace Gecode { namespace Search {
131 
136  class Statistics : public StatusStatistics {
137  public:
139  unsigned long int fail;
141  unsigned long int node;
143  unsigned long int depth;
145  unsigned long int restart;
147  unsigned long int nogood;
149  Statistics(void);
151  void reset(void);
153  Statistics operator +(const Statistics& s);
155  Statistics& operator +=(const Statistics& s);
156  };
157 
158 }}
159 
161 
162 namespace Gecode { namespace Search {
163 
164  class Stop;
165  class Cutoff;
166 
204  class Options {
205  public:
207  bool clone;
209  double threads;
211  unsigned int c_d;
213  unsigned int a_d;
215  unsigned int nogoods_limit;
223  Options(void);
226  expand(void) const;
227  };
228 
229 }}
230 
231 #include <gecode/search/options.hpp>
232 
233 namespace Gecode {
234 
235  template<template<class> class E, class T>
236  class RBS;
237 
238 }
239 
240 namespace Gecode { namespace Search { namespace Meta {
241 
242  class RBS;
243 
244 }}}
245 
246 namespace Gecode { namespace Search {
247 
263  public:
265  Stop(void);
267  virtual bool stop(const Statistics& s, const Options& o) = 0;
269  virtual ~Stop(void);
271  static void* operator new(size_t s);
273  static void operator delete(void* p);
274  };
275 
285  protected:
287  unsigned long int l;
288  public:
290  NodeStop(unsigned long int l);
292  unsigned long int limit(void) const;
294  void limit(unsigned long int l);
296  virtual bool stop(const Statistics& s, const Options& o);
297  };
298 
308  protected:
310  unsigned long int l;
311  public:
313  FailStop(unsigned long int l);
315  unsigned long int limit(void) const;
317  void limit(unsigned long int l);
319  virtual bool stop(const Statistics& s, const Options& o);
320  };
321 
327  protected:
331  unsigned long int l;
332  public:
334  TimeStop(unsigned long int l);
336  unsigned long int limit(void) const;
338  void limit(unsigned long int l);
340  void reset(void);
342  virtual bool stop(const Statistics& s, const Options& o);
343  };
344 
350  template<template<class>class,class> friend class ::Gecode::RBS;
351  friend class ::Gecode::Search::Meta::RBS;
352  private:
354  FailStop* e_stop;
356  Stop* m_stop;
358  bool e_stopped;
360  Statistics m_stat;
361  public:
363  MetaStop(Stop* s);
365  virtual bool stop(const Statistics& s, const Options& o);
367  void limit(const Search::Statistics& s, unsigned long int l);
369  Stop* enginestop(void) const;
371  bool enginestopped(void) const;
373  Statistics metastatistics(void) const;
375  ~MetaStop(void);
376  };
377 
378 }}
379 
380 #include <gecode/search/stop.hpp>
381 
382 namespace Gecode { namespace Search {
383 
388  public:
390  Cutoff(void);
392  virtual unsigned long int operator ()(void) = 0;
394  virtual ~Cutoff(void);
396  static Cutoff*
397  constant(unsigned long int scale=1U);
399  static Cutoff*
400  linear(unsigned long int scale=1U);
404  static Cutoff*
405  geometric(unsigned long int scale=1U, double base=1.5);
407  static Cutoff*
408  luby(unsigned long int scale=1U);
413  static Cutoff*
414  rnd(unsigned int seed,
415  unsigned long int min, unsigned long int max,
416  unsigned long int n);
418  static Cutoff*
419  append(Cutoff* c1, unsigned long int n, Cutoff* c2);
421  static void* operator new(size_t s);
423  static void operator delete(void* p);
424  };
425 
426 }}
427 
428 #include <gecode/search/cutoff.hpp>
429 
430 namespace Gecode { namespace Search {
431 
435  class Engine {
436  public:
438  virtual Space* next(void) = 0;
440  virtual Statistics statistics(void) const = 0;
442  virtual bool stopped(void) const = 0;
444  virtual void reset(Space* s) = 0;
446  virtual NoGoods& nogoods(void) = 0;
448  virtual ~Engine(void) {}
449  };
450 
451 }}
452 
453 namespace Gecode {
454 
458  class EngineBase {
459  template<template<class>class,class> friend class ::Gecode::RBS;
460  protected:
464  ~EngineBase(void);
466  EngineBase(Search::Engine* e = NULL);
467  };
468 
469 }
470 
472 
473 namespace Gecode {
474 
475 
483  template<class T>
484  class DFS : public EngineBase {
485  public:
487  DFS(T* s, const Search::Options& o=Search::Options::def);
489  T* next(void);
491  Search::Statistics statistics(void) const;
493  bool stopped(void) const;
495  NoGoods& nogoods(void);
496  };
497 
499  template<class T>
500  T* dfs(T* s, const Search::Options& o=Search::Options::def);
501 
502 }
503 
504 #include <gecode/search/dfs.hpp>
505 
506 namespace Gecode {
507 
519  template<class T>
520  class BAB : public EngineBase {
521  public:
523  BAB(T* s, const Search::Options& o=Search::Options::def);
525  T* next(void);
527  Search::Statistics statistics(void) const;
529  bool stopped(void) const;
531  NoGoods& nogoods(void);
532  };
533 
546  template<class T>
547  T* bab(T* s, const Search::Options& o=Search::Options::def);
548 
549 }
550 
551 #include <gecode/search/bab.hpp>
552 
553 namespace Gecode {
554 
573  template<template<class> class E, class T>
574  class RBS : public EngineBase {
575  public:
577  RBS(T* s, const Search::Options& o);
579  T* next(void);
581  Search::Statistics statistics(void) const;
583  bool stopped(void) const;
584  };
585 
604  template<template<class> class E, class T>
605  T* rbs(T* s, const Search::Options& o);
606 
607 }
608 
609 #include <gecode/search/rbs.hpp>
610 
611 #endif
612 
613 // STATISTICS: search-other