Generated on Mon Feb 8 2021 00:00:00 for Gecode by doxygen 1.8.20
lds.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  *
6  * Copyright:
7  * Christian Schulte, 2004, 2016
8  *
9  * This file is part of Gecode, the generic constraint
10  * development environment:
11  * http://www.gecode.org
12  *
13  * Permission is hereby granted, free of charge, to any person obtaining
14  * a copy of this software and associated documentation files (the
15  * "Software"), to deal in the Software without restriction, including
16  * without limitation the rights to use, copy, modify, merge, publish,
17  * distribute, sublicense, and/or sell copies of the Software, and to
18  * permit persons to whom the Software is furnished to do so, subject to
19  * the following conditions:
20  *
21  * The above copyright notice and this permission notice shall be
22  * included in all copies or substantial portions of the Software.
23  *
24  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31  *
32  */
33 
34 #ifndef __GECODE_SEARCH_SEQ_LDS_HH__
35 #define __GECODE_SEARCH_SEQ_LDS_HH__
36 
37 #include <gecode/search.hh>
38 #include <gecode/search/support.hh>
39 #include <gecode/search/worker.hh>
40 
41 namespace Gecode { namespace Search { namespace Seq {
42 
44  template<class Tracer>
45  class Probe : public Worker {
46  protected:
48  typedef typename Tracer::ID ID;
50  class Node {
51  private:
53  Space* _space;
55  const Choice* _choice;
57  unsigned int _alt;
59  ID _nid;
60  public:
62  Node(void);
64  Node(Space* s, const Choice* c, unsigned int a, unsigned int nid);
66  Space* space(void) const;
68  const Choice* choice(void) const;
70  unsigned int alt(void) const;
72  unsigned int nid(void) const;
74  void next(void);
75  };
83  unsigned int d;
85  bool exhausted;
86  public:
88  Probe(const Options& opt);
90  void init(Space* s);
92  void reset(Space* s, unsigned int d);
94  Statistics statistics(void) const;
96  ~Probe(void);
98  Space* next(const Options& o);
100  bool done(void) const;
101  };
102 
104  template<class Tracer>
105  class LDS : public Engine {
106  protected:
114  unsigned int d;
117  public:
119  LDS(Space* s, const Options& o);
121  virtual Space* next(void);
123  virtual Statistics statistics(void) const;
125  void constrain(const Space& b);
127  void reset(Space* s);
129  virtual bool stopped(void) const;
131  virtual ~LDS(void);
132  };
133 
134 }}}
135 
136 #include <gecode/search/seq/lds.hpp>
137 
138 #endif
139 
140 // STATISTICS: search-seq
unsigned int alt(void) const
Return next alternative.
Definition: lds.hpp:66
const Choice * choice(void) const
Return choice.
Definition: lds.hpp:60
Search worker statistics
Definition: worker.hh:44
Probe< Tracer > e
The probe engine.
Definition: lds.hh:110
Statistics statistics(void) const
Return statistics.
Definition: lds.hpp:121
LDS(Space *s, const Options &o)
Initialize for space s with options o.
Definition: lds.hpp:272
Search engine options
Definition: search.hh:746
~Probe(void)
Destructor.
Definition: lds.hpp:133
Space * cur
Current space.
Definition: lds.hh:81
Computation spaces.
Definition: core.hpp:1742
virtual ~LDS(void)
Destructor.
Definition: lds.hpp:345
bool done(void) const
Test whether probing is done.
Definition: lds.hpp:127
Node in the search tree for LDS
Definition: lds.hh:50
unsigned int d
Current discrepancy.
Definition: lds.hh:114
Gecode toplevel namespace
Space * root
Root node for problem.
Definition: lds.hh:112
Options opt
The options.
Definition: test.cpp:97
Space * next(const Options &o)
Search for next solution
Definition: lds.hpp:142
Search engine implementation interface
Definition: search.hh:899
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
bool no_solution
Solution found for current discrepancy.
Definition: lds.hh:116
Limited discrepancy search engine implementation.
Definition: lds.hh:105
Support::DynamicStack< Node, Heap > ds
Stack storing current path in search tree
Definition: lds.hh:79
bool exhausted
Whether entire search space has been exhausted.
Definition: lds.hh:85
Options opt
Search options.
Definition: lds.hh:108
Probe engine for LDS
Definition: lds.hh:45
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
Space * space(void) const
Return space.
Definition: lds.hpp:54
Tracer.
Definition: tracer.hpp:149
unsigned int nid(void) const
Return node identifier.
Definition: lds.hpp:72
virtual Statistics statistics(void) const
Return statistics.
Definition: lds.hpp:315
void reset(Space *s)
Reset engine to restart at space s.
Definition: lds.hpp:322
void init(Space *s)
Initialize with space s.
Definition: lds.hpp:100
Probe(const Options &opt)
Initialize.
Definition: lds.hpp:92
Tracer::ID ID
Node identity type.
Definition: lds.hh:48
Stack with arbitrary number of elements.
void next(void)
Set next alternative
Definition: lds.hpp:78
Gecode::FloatVal c(-8, 8)
void reset(void)
Reset.
Definition: statistics.hpp:39
Node(void)
Default constructor.
Definition: lds.hpp:44
virtual bool stopped(void) const
Check whether engine has been stopped.
Definition: lds.hpp:309
Choice for performing commit
Definition: core.hpp:1412
virtual Space * next(void)
Return next solution (NULL, if none exists or search has been stopped)
Definition: lds.hpp:289
Search engine statistics
Definition: search.hh:147
Tracer tracer
Search tracer.
Definition: lds.hh:77
void constrain(const Space &b)
Constrain future solutions to be better than b (should never be called)
Definition: lds.hpp:339
unsigned int d
Current discrepancy.
Definition: lds.hh:83