38 namespace Gecode {
namespace Search {
namespace Seq {
46 template<
class Tracer>
50 template<
class Tracer>
54 : _space(s), _choice(c), _alt(a), _nid(nid) {}
56 template<
class Tracer>
62 template<
class Tracer>
68 template<
class Tracer>
74 template<
class Tracer>
80 template<
class Tracer>
94 template<
class Tracer>
98 tracer.engine(SearchTracer::EngineType::LDS, 1U);
102 template<
class Tracer>
105 cur = s;
d = 0U; exhausted =
true;
107 tracer.ei()->invalidate();
110 template<
class Tracer>
116 delete ds.pop().space();
117 cur = s;
d = d0; exhausted =
true;
119 tracer.ei()->invalidate();
123 template<
class Tracer>
129 template<
class Tracer>
135 template<
class Tracer>
141 delete ds.pop().space();
144 template<
class Tracer>
155 unsigned int a = ds.top().alt();
156 const Choice* ch = ds.top().choice();
157 unsigned int nid = ds.top().nid();
159 cur = ds.pop().space();
161 tracer.ei()->init(tracer.wid(), nid, 0, *cur, *ch);
166 cur = ds.top().space()->clone();
168 tracer.ei()->init(tracer.wid(), nid,
a, *cur, *ch);
186 unsigned int nid = tracer.nid();
188 tracer.wid(), nid, *s, ch);
189 tracer.node(*tracer.ei(),ni);
191 tracer.ei()->init(tracer.wid(), nid, 0, *cur, *ch);
201 tracer.wid(), tracer.nid(), *s);
202 tracer.node(*tracer.ei(),ni);
210 tracer.wid(), tracer.nid(), *s);
211 tracer.node(*tracer.ei(),ni);
219 switch (cur->status(*
this)) {
223 tracer.wid(), tracer.nid(), *cur);
224 tracer.node(*tracer.ei(),ni);
232 tracer.skip(*tracer.ei());
239 const Choice* ch = cur->choice();
241 unsigned int nid = tracer.nid();
244 tracer.wid(), nid, *cur, ch);
245 tracer.node(*tracer.ei(),ni);
250 unsigned int d_a = (
d >= alt-1) ? alt-1 :
d;
252 Node sn(cc,ch,d_a-1,nid);
254 stack_depth(static_cast<unsigned long int>(ds.entries()));
256 tracer.ei()->init(tracer.wid(), nid, d_a, *cur, *ch);
257 cur->commit(*ch,d_a);
261 tracer.ei()->init(tracer.wid(), nid, 0, *cur, *ch);
266 goto check_discrepancy;
274 template<
class Tracer>
277 :
opt(o), e(
opt), root(NULL),
d(0) {
291 template<
class Tracer>
298 if (((s == NULL) &&
e.stopped()) || (++
d >
opt.
d_l) ||
e.done())
304 }
else if (
root != NULL) {
311 template<
class Tracer>
317 template<
class Tracer>
320 return e.statistics();
324 template<
class Tracer>
341 template<
class Tracer>
348 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)