34 namespace Gecode {
namespace Search {
namespace Seq {
42 template<
class Tracer>
46 template<
class Tracer>
50 : _space(s), _choice(c), _alt(a), _nid(nid) {}
52 template<
class Tracer>
58 template<
class Tracer>
64 template<
class Tracer>
70 template<
class Tracer>
76 template<
class Tracer>
90 template<
class Tracer>
94 tracer.engine(SearchTracer::EngineType::LDS, 1U);
98 template<
class Tracer>
101 cur = s;
d = 0U; exhausted =
true;
103 tracer.ei()->invalidate();
106 template<
class Tracer>
112 delete ds.pop().space();
113 cur = s;
d = d0; exhausted =
true;
115 tracer.ei()->invalidate();
119 template<
class Tracer>
125 template<
class Tracer>
131 template<
class Tracer>
137 delete ds.pop().space();
140 template<
class Tracer>
151 unsigned int a = ds.top().alt();
152 const Choice* ch = ds.top().choice();
153 unsigned int nid = ds.top().nid();
155 cur = ds.pop().space();
157 tracer.ei()->init(tracer.wid(), nid, 0, *cur, *ch);
162 cur = ds.top().space()->clone();
164 tracer.ei()->init(tracer.wid(), nid,
a, *cur, *ch);
182 unsigned int nid = tracer.nid();
184 tracer.wid(), nid, *s, ch);
185 tracer.node(*tracer.ei(),ni);
187 tracer.ei()->init(tracer.wid(), nid, 0, *cur, *ch);
197 tracer.wid(), tracer.nid(), *s);
198 tracer.node(*tracer.ei(),ni);
206 tracer.wid(), tracer.nid(), *s);
207 tracer.node(*tracer.ei(),ni);
215 switch (cur->status(*
this)) {
219 tracer.wid(), tracer.nid(), *cur);
220 tracer.node(*tracer.ei(),ni);
228 tracer.skip(*tracer.ei());
235 const Choice* ch = cur->choice();
237 unsigned int nid = tracer.nid();
240 tracer.wid(), nid, *cur, ch);
241 tracer.node(*tracer.ei(),ni);
246 unsigned int d_a = (
d >= alt-1) ? alt-1 :
d;
248 Node sn(cc,ch,d_a-1,nid);
250 stack_depth(static_cast<unsigned long int>(ds.entries()));
252 tracer.ei()->init(tracer.wid(), nid, d_a, *cur, *ch);
253 cur->commit(*ch,d_a);
257 tracer.ei()->init(tracer.wid(), nid, 0, *cur, *ch);
262 goto check_discrepancy;
270 template<
class Tracer>
273 :
opt(o), e(
opt), root(NULL),
d(0) {
287 template<
class Tracer>
294 if (((s == NULL) &&
e.stopped()) || (++
d >
opt.
d_l) ||
e.done())
300 }
else if (
root != NULL) {
307 template<
class Tracer>
313 template<
class Tracer>
316 return e.statistics();
320 template<
class Tracer>
337 template<
class Tracer>
344 template<
class Tracer>
Space * root
Root node for problem.
unsigned int alternatives(void) const
Return number of alternatives.
Space must be branched (at least one brancher left)
virtual Space * next(void)
Return next solution (NULL, if none exists or search has been stopped)
Node representing a branch.
void reset(Space *s)
Reset engine to restart at space s.
void stop(Support::Timer &timer, std::ostream &os)
Get time since start of timer and print user friendly time information.
unsigned int nid(void) const
Return node identifier.
Space * space(void) const
Return space.
Node(void)
Default constructor.
Node representing failure.
void next(void)
Set next alternative
unsigned int d_l
Discrepancy limit (for LDS)
Probe(const Options &opt)
Initialize.
Gecode::FloatVal c(-8, 8)
virtual ~LDS(void)
Destructor.
Space * clone(CloneStatistics &stat=unused_clone) const
Clone space.
unsigned int alt(void) const
Return next alternative.
Node representing a solution.
bool failed(void) const
Check whether space is failed.
void commit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
Commit choice c for alternative a.
Support::DynamicStack< Node, Heap > ds
Stack storing current path in search tree
const Choice * choice(void) const
Return choice.
struct Gecode::@585::NNF::@62::@63 b
For binary nodes (and, or, eqv)
struct Gecode::@585::NNF::@62::@64 a
For atomic nodes.
Choice for performing commit
bool done(void) const
Test whether probing is done.
Heap heap
The single global heap.
virtual bool stopped(void) const
Check whether engine has been stopped.
Tracer tracer
Search tracer.
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Probe< Tracer > e
The probe engine.
virtual Statistics statistics(void) const
Return statistics.
unsigned int d
Current discrepancy.
Gecode toplevel namespace
Options opt
Search options.
void constrain(const Space &b)
Constrain future solutions to be better than b (should never be called)
Space * snapshot(Space *s, const Options &o)
Clone space s dependening on options o.
const Choice * choice(void)
Create new choice for current brancher.
#define GECODE_NEVER
Assert that this command is never executed.
Limited discrepancy search engine implementation.
Space is solved (no brancher left)