34namespace 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) {
301 e.reset(root->clone(),
d);
307 template<
class Tracer>
313 template<
class Tracer>
316 return e.statistics();
320 template<
class Tracer>
323 delete root; root=NULL;
d=0;
337 template<
class Tracer>
344 template<
class Tracer>
struct Gecode::@603::NNF::@65::@66 b
For binary nodes (and, or, eqv)
struct Gecode::@603::NNF::@65::@67 a
For atomic nodes.
Choice for performing commit
unsigned int alternatives(void) const
Return number of alternatives.
unsigned int d_l
Discrepancy limit (for LDS)
Options opt
Search options.
void reset(Space *s)
Reset engine to restart at space s.
virtual Statistics statistics(void) const
Return statistics.
virtual Space * next(void)
Return next solution (NULL, if none exists or search has been stopped)
void constrain(const Space &b)
Constrain future solutions to be better than b (should never be called)
virtual bool stopped(void) const
Check whether engine has been stopped.
Space * root
Root node for problem.
Probe< Tracer > e
The probe engine.
virtual ~LDS(void)
Destructor.
LDS(Space *s, const Options &o)
Initialize for space s with options o.
Node in the search tree for LDS
Node(void)
Default constructor.
unsigned int nid(void) const
Return node identifier.
void next(void)
Set next alternative
const Choice * choice(void) const
Return choice.
unsigned int alt(void) const
Return next alternative.
Space * space(void) const
Return space.
Tracer tracer
Search tracer.
void init(Space *s)
Initialize with space s.
bool done(void) const
Test whether probing is done.
Support::DynamicStack< Node, Heap > ds
Stack storing current path in search tree
Probe(const Options &opt)
Initialize.
Space * next(const Options &o)
Search for next solution
Statistics statistics(void) const
Return statistics.
Heap heap
The single global heap.
bool failed(void) const
Check whether space is failed.
void fail(void)
Fail space.
const Choice * choice(void)
Create new choice for current brancher.
void commit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
Commit choice c for alternative a.
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Space * clone(CloneStatistics &stat=unused_clone) const
Clone space.
@ SS_BRANCH
Space must be branched (at least one brancher left)
@ SS_SOLVED
Space is solved (no brancher left)
@ SS_FAILED
Space is failed
void stop(Support::Timer &timer, std::ostream &os)
Get time since start of timer and print user friendly time information.
@ FAILED
Node representing failure.
@ SOLVED
Node representing a solution.
@ BRANCH
Node representing a branch.
Space * snapshot(Space *s, const Options &o)
Clone space s dependening on options o.
Gecode toplevel namespace
Gecode::FloatVal c(-8, 8)
#define GECODE_NEVER
Assert that this command is never executed.