Generated on Sun Aug 9 2020 05:34:08 for Gecode by doxygen 1.8.18
lds.hpp
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 namespace Gecode { namespace Search { namespace Seq {
35 
36  /*
37  * Nodes for the probing engine (just remember next alternative
38  * to try)
39  *
40  */
41 
42  template<class Tracer>
45 
46  template<class Tracer>
48  Probe<Tracer>::Node::Node(Space* s, const Choice* c, unsigned int a,
49  unsigned int nid)
50  : _space(s), _choice(c), _alt(a), _nid(nid) {}
51 
52  template<class Tracer>
55  return _space;
56  }
57 
58  template<class Tracer>
59  forceinline const Choice*
61  return _choice;
62  }
63 
64  template<class Tracer>
65  forceinline unsigned int
67  return _alt;
68  }
69 
70  template<class Tracer>
71  forceinline unsigned int
73  return _nid;
74  }
75 
76  template<class Tracer>
77  forceinline void
79  _alt--;
80  }
81 
82 
83  /*
84  * The probing engine: computes all solutions with
85  * exact number of discrepancies (solutions with
86  * fewer discrepancies are discarded)
87  *
88  */
89 
90  template<class Tracer>
93  : tracer(opt.tracer), ds(heap) {
94  tracer.engine(SearchTracer::EngineType::LDS, 1U);
95  tracer.worker();
96  }
97 
98  template<class Tracer>
99  forceinline void
101  cur = s; d = 0U; exhausted = true;
102  if (tracer)
103  tracer.ei()->invalidate();
104  }
105 
106  template<class Tracer>
107  forceinline void
108  Probe<Tracer>::reset(Space* s, unsigned int d0) {
109  tracer.round();
110  delete cur;
111  while (!ds.empty())
112  delete ds.pop().space();
113  cur = s; d = d0; exhausted = true;
114  if (tracer)
115  tracer.ei()->invalidate();
116  Worker::reset(0);
117  }
118 
119  template<class Tracer>
122  return *this;
123  }
124 
125  template<class Tracer>
126  forceinline bool
127  Probe<Tracer>::done(void) const {
128  return exhausted;
129  }
130 
131  template<class Tracer>
134  tracer.done();
135  delete cur;
136  while (!ds.empty())
137  delete ds.pop().space();
138  }
139 
140  template<class Tracer>
143  start();
144  while (true) {
145  if (cur == NULL) {
146  backtrack:
147  if (ds.empty())
148  return NULL;
149  if (stop(opt))
150  return NULL;
151  unsigned int a = ds.top().alt();
152  const Choice* ch = ds.top().choice();
153  unsigned int nid = ds.top().nid();
154  if (a == 0) {
155  cur = ds.pop().space();
156  if (tracer)
157  tracer.ei()->init(tracer.wid(), nid, 0, *cur, *ch);
158  cur->commit(*ch,0);
159  delete ch;
160  } else {
161  ds.top().next();
162  cur = ds.top().space()->clone();
163  if (tracer)
164  tracer.ei()->init(tracer.wid(), nid, a, *cur, *ch);
165  cur->commit(*ch,a);
166  }
167  node++;
168  d++;
169  }
170  check_discrepancy:
171  if (d == 0) {
172  Space* s = cur;
173  while (s->status(*this) == SS_BRANCH) {
174  if (stop(opt)) {
175  cur = s;
176  return NULL;
177  }
178  const Choice* ch = s->choice();
179  if (ch->alternatives() > 1)
180  exhausted = false;
181  if (tracer) {
182  unsigned int nid = tracer.nid();
184  tracer.wid(), nid, *s, ch);
185  tracer.node(*tracer.ei(),ni);
186  if (tracer)
187  tracer.ei()->init(tracer.wid(), nid, 0, *cur, *ch);
188  }
189  s->commit(*ch,0);
190  node++;
191  delete ch;
192  }
193  cur = NULL;
194  if (s->failed()) {
195  if (tracer) {
197  tracer.wid(), tracer.nid(), *s);
198  tracer.node(*tracer.ei(),ni);
199  }
200  fail++;
201  delete s;
202  goto backtrack;
203  } else {
204  if (tracer) {
206  tracer.wid(), tracer.nid(), *s);
207  tracer.node(*tracer.ei(),ni);
208  }
209  // Deletes all pending branchings
210  (void) s->choice();
211  return s;
212  }
213  } else {
214  node++;
215  switch (cur->status(*this)) {
216  case SS_FAILED:
217  if (tracer) {
219  tracer.wid(), tracer.nid(), *cur);
220  tracer.node(*tracer.ei(),ni);
221  }
222  fail++;
223  delete cur;
224  cur = NULL;
225  goto backtrack;
226  case SS_SOLVED:
227  if (tracer) {
228  tracer.skip(*tracer.ei());
229  }
230  delete cur;
231  cur = NULL;
232  goto backtrack;
233  case SS_BRANCH:
234  {
235  const Choice* ch = cur->choice();
236  unsigned int alt = ch->alternatives();
237  unsigned int nid = tracer.nid();
238  if (tracer) {
240  tracer.wid(), nid, *cur, ch);
241  tracer.node(*tracer.ei(),ni);
242  }
243  if (alt > 1) {
244  if (d < alt-1)
245  exhausted = false;
246  unsigned int d_a = (d >= alt-1) ? alt-1 : d;
247  Space* cc = cur->clone();
248  Node sn(cc,ch,d_a-1,nid);
249  ds.push(sn);
250  stack_depth(static_cast<unsigned long int>(ds.entries()));
251  if (tracer)
252  tracer.ei()->init(tracer.wid(), nid, d_a, *cur, *ch);
253  cur->commit(*ch,d_a);
254  d -= d_a;
255  } else {
256  if (tracer)
257  tracer.ei()->init(tracer.wid(), nid, 0, *cur, *ch);
258  cur->commit(*ch,0);
259  node++;
260  delete ch;
261  }
262  goto check_discrepancy;
263  }
264  default: GECODE_NEVER;
265  }
266  }
267  }
268  }
269 
270  template<class Tracer>
273  : opt(o), e(opt), root(NULL), d(0) {
274  e.node = 1;
275  if (s->status(e) == SS_FAILED) {
276  e.fail++;
277  e.init(NULL);
278  } else {
279  Space* c = snapshot(s,opt);
280  if (opt.d_l > 0) {
281  root = c->clone();
282  }
283  e.init(c);
284  }
285  }
286 
287  template<class Tracer>
288  Space*
290  while (true) {
291  Space* s = e.next(opt);
292  if (s != NULL)
293  return s;
294  if (((s == NULL) && e.stopped()) || (++d > opt.d_l) || e.done())
295  break;
296  if (d == opt.d_l) {
297  if (root != NULL)
298  e.reset(root,d);
299  root = NULL;
300  } else if (root != NULL) {
301  e.reset(root->clone(),d);
302  }
303  }
304  return NULL;
305  }
306 
307  template<class Tracer>
308  bool
309  LDS<Tracer>::stopped(void) const {
310  return e.stopped();
311  }
312 
313  template<class Tracer>
314  Statistics
316  return e.statistics();
317  }
318 
319 
320  template<class Tracer>
321  forceinline void
323  delete root; root=NULL; d=0;
324  e.node = 1;
325  if ((s == NULL) || (s->status(e) == SS_FAILED)) {
326  delete s;
327  e.fail++;
328  e.reset(NULL,0);
329  } else {
330  if (opt.d_l > 0) {
331  root = s->clone();
332  }
333  e.reset(s,0);
334  }
335  }
336 
337  template<class Tracer>
338  forceinline void
340  (void) b;
341  assert(false);
342  }
343 
344  template<class Tracer>
346  delete root;
347  }
348 
349 }}}
350 
351 // 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
@ SS_SOLVED
Space is solved (no brancher left)
Definition: core.hpp:1683
Probe< Tracer > e
The probe engine.
Definition: lds.hh:110
Search engine options
Definition: search.hh:746
const Choice * choice(void)
Create new choice for current brancher.
Definition: core.cpp:537
unsigned int alternatives(void) const
Return number of alternatives.
Definition: core.hpp:3770
Space * snapshot(Space *s, const Options &o)
Clone space s dependening on options o.
Definition: support.hh:71
@ SS_BRANCH
Space must be branched (at least one brancher left)
Definition: core.hpp:1684
void commit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
Commit choice c for alternative a.
Definition: core.hpp:3232
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
Gecode toplevel namespace
Space * clone(CloneStatistics &stat=unused_clone) const
Clone space.
Definition: core.hpp:3224
Space * root
Root node for problem.
Definition: lds.hh:112
Options opt
The options.
Definition: test.cpp:97
void stop(Support::Timer &timer, std::ostream &os)
Get time since start of timer and print user friendly time information.
Definition: script.cpp:42
Node information.
Definition: search.hh:282
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
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
Options opt
Search options.
Definition: lds.hh:108
@ BRANCH
Node representing a branch.
Definition: spacenode.hh:47
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:56
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
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition: core.cpp:252
unsigned int nid(void) const
Return node identifier.
Definition: lds.hpp:72
Heap heap
The single global heap.
Definition: heap.cpp:44
virtual Statistics statistics(void) const
Return statistics.
Definition: lds.hpp:315
bool failed(void) const
Check whether space is failed.
Definition: core.hpp:4044
void fail(void)
Fail space.
Definition: core.hpp:4030
Gecode::IntSet d(v, 7)
void reset(Space *s)
Reset engine to restart at space s.
Definition: lds.hpp:322
Probe(const Options &opt)
Initialize.
Definition: lds.hpp:92
#define forceinline
Definition: config.hpp:185
void next(void)
Set next alternative
Definition: lds.hpp:78
Gecode::FloatVal c(-8, 8)
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
unsigned int d_l
Discrepancy limit (for LDS)
Definition: search.hh:757
virtual Space * next(void)
Return next solution (NULL, if none exists or search has been stopped)
Definition: lds.hpp:289
@ FAILED
Node representing failure.
Definition: spacenode.hh:46
Search engine statistics
Definition: search.hh:147
@ SS_FAILED
Space is failed
Definition: core.hpp:1682
Tracer tracer
Search tracer.
Definition: lds.hh:77
@ SOLVED
Node representing a solution.
Definition: spacenode.hh:45
void constrain(const Space &b)
Constrain future solutions to be better than b (should never be called)
Definition: lds.hpp:339