Generated on Sat Nov 9 2013 19:18:30 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-10-30 15:42:34 +0100 (Wed, 30 Oct 2013) $ by $Author: schulte $
13  * $Revision: 14037 $
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  void update(const Search::Statistics& s);
371  Stop* enginestop(void) const;
373  bool enginestopped(void) const;
375  Statistics metastatistics(void) const;
377  ~MetaStop(void);
378  };
379 
380 }}
381 
382 #include <gecode/search/stop.hpp>
383 
384 namespace Gecode { namespace Search {
385 
390  public:
392  Cutoff(void);
394  virtual unsigned long int operator ()(void) = 0;
396  virtual ~Cutoff(void);
398  static Cutoff*
399  constant(unsigned long int scale=1U);
401  static Cutoff*
402  linear(unsigned long int scale=1U);
406  static Cutoff*
407  geometric(unsigned long int scale=1U, double base=1.5);
409  static Cutoff*
410  luby(unsigned long int scale=1U);
415  static Cutoff*
416  rnd(unsigned int seed,
417  unsigned long int min, unsigned long int max,
418  unsigned long int n);
420  static Cutoff*
421  append(Cutoff* c1, unsigned long int n, Cutoff* c2);
423  static Cutoff*
424  repeat(Cutoff* c, unsigned long int n);
426  static void* operator new(size_t s);
428  static void operator delete(void* p);
429  };
430 
431 }}
432 
433 #include <gecode/search/cutoff.hpp>
434 
435 namespace Gecode { namespace Search {
436 
440  class Engine {
441  public:
443  virtual Space* next(void) = 0;
445  virtual Statistics statistics(void) const = 0;
447  virtual bool stopped(void) const = 0;
449  virtual void reset(Space* s) = 0;
451  virtual NoGoods& nogoods(void) = 0;
453  virtual ~Engine(void) {}
454  };
455 
456 }}
457 
458 namespace Gecode {
459 
463  class EngineBase {
464  template<template<class>class,class> friend class ::Gecode::RBS;
465  protected:
469  ~EngineBase(void);
471  EngineBase(Search::Engine* e = NULL);
472  };
473 
474 }
475 
477 
478 namespace Gecode {
479 
480 
488  template<class T>
489  class DFS : public EngineBase {
490  public:
492  DFS(T* s, const Search::Options& o=Search::Options::def);
494  T* next(void);
496  Search::Statistics statistics(void) const;
498  bool stopped(void) const;
500  NoGoods& nogoods(void);
501  };
502 
504  template<class T>
505  T* dfs(T* s, const Search::Options& o=Search::Options::def);
506 
507 }
508 
509 #include <gecode/search/dfs.hpp>
510 
511 namespace Gecode {
512 
524  template<class T>
525  class BAB : public EngineBase {
526  public:
528  BAB(T* s, const Search::Options& o=Search::Options::def);
530  T* next(void);
532  Search::Statistics statistics(void) const;
534  bool stopped(void) const;
536  NoGoods& nogoods(void);
537  };
538 
551  template<class T>
552  T* bab(T* s, const Search::Options& o=Search::Options::def);
553 
554 }
555 
556 #include <gecode/search/bab.hpp>
557 
558 namespace Gecode {
559 
578  template<template<class> class E, class T>
579  class RBS : public EngineBase {
580  public:
582  RBS(T* s, const Search::Options& o);
584  T* next(void);
586  Search::Statistics statistics(void) const;
588  bool stopped(void) const;
589  };
590 
609  template<template<class> class E, class T>
610  T* rbs(T* s, const Search::Options& o);
611 
612 }
613 
614 #include <gecode/search/rbs.hpp>
615 
616 #endif
617 
618 // STATISTICS: search-other