Generated on Thu Apr 5 2018 19:44:19 for Gecode by doxygen 1.8.13
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  * Last modified:
10  * $Date$ by $Author$
11  * $Revision$
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 namespace Gecode { namespace Search { namespace Seq {
39 
40  /*
41  * Nodes for the probing engine (just remember next alternative
42  * to try)
43  *
44  */
45 
46  template<class Tracer>
49 
50  template<class Tracer>
52  Probe<Tracer>::Node::Node(Space* s, const Choice* c, unsigned int a,
53  unsigned int nid)
54  : _space(s), _choice(c), _alt(a), _nid(nid) {}
55 
56  template<class Tracer>
59  return _space;
60  }
61 
62  template<class Tracer>
63  forceinline const Choice*
65  return _choice;
66  }
67 
68  template<class Tracer>
69  forceinline unsigned int
71  return _alt;
72  }
73 
74  template<class Tracer>
75  forceinline unsigned int
77  return _nid;
78  }
79 
80  template<class Tracer>
81  forceinline void
83  _alt--;
84  }
85 
86 
87  /*
88  * The probing engine: computes all solutions with
89  * exact number of discrepancies (solutions with
90  * fewer discrepancies are discarded)
91  *
92  */
93 
94  template<class Tracer>
97  : tracer(opt.tracer), ds(heap) {
98  tracer.engine(SearchTracer::EngineType::LDS, 1U);
99  tracer.worker();
100  }
101 
102  template<class Tracer>
103  forceinline void
105  cur = s; d = 0U; exhausted = true;
106  if (tracer)
107  tracer.ei()->invalidate();
108  }
109 
110  template<class Tracer>
111  forceinline void
112  Probe<Tracer>::reset(Space* s, unsigned int d0) {
113  tracer.round();
114  delete cur;
115  while (!ds.empty())
116  delete ds.pop().space();
117  cur = s; d = d0; exhausted = true;
118  if (tracer)
119  tracer.ei()->invalidate();
120  Worker::reset(0);
121  }
122 
123  template<class Tracer>
126  return *this;
127  }
128 
129  template<class Tracer>
130  forceinline bool
131  Probe<Tracer>::done(void) const {
132  return exhausted;
133  }
134 
135  template<class Tracer>
138  tracer.done();
139  delete cur;
140  while (!ds.empty())
141  delete ds.pop().space();
142  }
143 
144  template<class Tracer>
147  start();
148  while (true) {
149  if (cur == NULL) {
150  backtrack:
151  if (ds.empty())
152  return NULL;
153  if (stop(opt))
154  return NULL;
155  unsigned int a = ds.top().alt();
156  const Choice* ch = ds.top().choice();
157  unsigned int nid = ds.top().nid();
158  if (a == 0) {
159  cur = ds.pop().space();
160  if (tracer)
161  tracer.ei()->init(tracer.wid(), nid, 0, *cur, *ch);
162  cur->commit(*ch,0);
163  delete ch;
164  } else {
165  ds.top().next();
166  cur = ds.top().space()->clone();
167  if (tracer)
168  tracer.ei()->init(tracer.wid(), nid, a, *cur, *ch);
169  cur->commit(*ch,a);
170  }
171  node++;
172  d++;
173  }
174  check_discrepancy:
175  if (d == 0) {
176  Space* s = cur;
177  while (s->status(*this) == SS_BRANCH) {
178  if (stop(opt)) {
179  cur = s;
180  return NULL;
181  }
182  const Choice* ch = s->choice();
183  if (ch->alternatives() > 1)
184  exhausted = false;
185  if (tracer) {
186  unsigned int nid = tracer.nid();
188  tracer.wid(), nid, *s, ch);
189  tracer.node(*tracer.ei(),ni);
190  if (tracer)
191  tracer.ei()->init(tracer.wid(), nid, 0, *cur, *ch);
192  }
193  s->commit(*ch,0);
194  node++;
195  delete ch;
196  }
197  cur = NULL;
198  if (s->failed()) {
199  if (tracer) {
201  tracer.wid(), tracer.nid(), *s);
202  tracer.node(*tracer.ei(),ni);
203  }
204  fail++;
205  delete s;
206  goto backtrack;
207  } else {
208  if (tracer) {
210  tracer.wid(), tracer.nid(), *s);
211  tracer.node(*tracer.ei(),ni);
212  }
213  // Deletes all pending branchings
214  (void) s->choice();
215  return s;
216  }
217  } else {
218  node++;
219  switch (cur->status(*this)) {
220  case SS_FAILED:
221  if (tracer) {
223  tracer.wid(), tracer.nid(), *cur);
224  tracer.node(*tracer.ei(),ni);
225  }
226  fail++;
227  delete cur;
228  cur = NULL;
229  goto backtrack;
230  case SS_SOLVED:
231  if (tracer) {
232  tracer.skip(*tracer.ei());
233  }
234  delete cur;
235  cur = NULL;
236  goto backtrack;
237  case SS_BRANCH:
238  {
239  const Choice* ch = cur->choice();
240  unsigned int alt = ch->alternatives();
241  unsigned int nid = tracer.nid();
242  if (tracer) {
244  tracer.wid(), nid, *cur, ch);
245  tracer.node(*tracer.ei(),ni);
246  }
247  if (alt > 1) {
248  if (d < alt-1)
249  exhausted = false;
250  unsigned int d_a = (d >= alt-1) ? alt-1 : d;
251  Space* cc = cur->clone();
252  Node sn(cc,ch,d_a-1,nid);
253  ds.push(sn);
254  stack_depth(static_cast<unsigned long int>(ds.entries()));
255  if (tracer)
256  tracer.ei()->init(tracer.wid(), nid, d_a, *cur, *ch);
257  cur->commit(*ch,d_a);
258  d -= d_a;
259  } else {
260  if (tracer)
261  tracer.ei()->init(tracer.wid(), nid, 0, *cur, *ch);
262  cur->commit(*ch,0);
263  node++;
264  delete ch;
265  }
266  goto check_discrepancy;
267  }
268  default: GECODE_NEVER;
269  }
270  }
271  }
272  }
273 
274  template<class Tracer>
277  : opt(o), e(opt), root(NULL), d(0) {
278  e.node = 1;
279  if (s->status(e) == SS_FAILED) {
280  e.fail++;
281  e.init(NULL);
282  } else {
283  Space* c = snapshot(s,opt);
284  if (opt.d_l > 0) {
285  root = c->clone();
286  }
287  e.init(c);
288  }
289  }
290 
291  template<class Tracer>
292  Space*
294  while (true) {
295  Space* s = e.next(opt);
296  if (s != NULL)
297  return s;
298  if (((s == NULL) && e.stopped()) || (++d > opt.d_l) || e.done())
299  break;
300  if (d == opt.d_l) {
301  if (root != NULL)
302  e.reset(root,d);
303  root = NULL;
304  } else if (root != NULL) {
305  e.reset(root->clone(),d);
306  }
307  }
308  return NULL;
309  }
310 
311  template<class Tracer>
312  bool
313  LDS<Tracer>::stopped(void) const {
314  return e.stopped();
315  }
316 
317  template<class Tracer>
318  Statistics
320  return e.statistics();
321  }
322 
323 
324  template<class Tracer>
325  forceinline void
327  delete root; root=NULL; d=0;
328  e.node = 1;
329  if ((s == NULL) || (s->status(e) == SS_FAILED)) {
330  delete s;
331  e.fail++;
332  e.reset(NULL,0);
333  } else {
334  if (opt.d_l > 0) {
335  root = s->clone();
336  }
337  e.reset(s,0);
338  }
339  }
340 
341  template<class Tracer>
342  forceinline void
344  (void) b;
345  assert(false);
346  }
347 
348  template<class Tracer>
350  delete root;
351  }
352 
353 }}}
354 
355 // STATISTICS: search-seq
Space * root
Root node for problem.
Definition: lds.hh:116
unsigned int alternatives(void) const
Return number of alternatives.
Definition: core.hpp:3640
Space must be branched (at least one brancher left)
Definition: core.hpp:1610
virtual Space * next(void)
Return next solution (NULL, if none exists or search has been stopped)
Definition: lds.hpp:293
Search engine statistics
Definition: search.hh:149
Node representing a branch.
Definition: spacenode.hh:51
void reset(Space *s)
Reset engine to restart at space s.
Definition: lds.hpp:326
Search engine options
Definition: search.hh:748
Probe engine for LDS
Definition: lds.hh:49
void stop(Support::Timer &timer, std::ostream &os)
Get time since start of timer and print user friendly time information.
Definition: script.cpp:46
unsigned int nid(void) const
Return node identifier.
Definition: lds.hpp:76
Space * space(void) const
Return space.
Definition: lds.hpp:58
Node(void)
Default constructor.
Definition: lds.hpp:48
Node representing failure.
Definition: spacenode.hh:50
#define forceinline
Definition: config.hpp:182
void next(void)
Set next alternative
Definition: lds.hpp:82
Computation spaces.
Definition: core.hpp:1668
unsigned int d_l
Discrepancy limit (for LDS)
Definition: search.hh:759
Gecode::IntSet d(v, 7)
Probe(const Options &opt)
Initialize.
Definition: lds.hpp:96
Gecode::FloatVal c(-8, 8)
virtual ~LDS(void)
Destructor.
Definition: lds.hpp:349
Options opt
The options.
Definition: test.cpp:101
Space * clone(CloneStatistics &stat=unused_clone) const
Clone space.
Definition: core.hpp:3144
unsigned int alt(void) const
Return next alternative.
Definition: lds.hpp:70
Node representing a solution.
Definition: spacenode.hh:49
bool failed(void) const
Check whether space is failed.
Definition: core.hpp:3914
void commit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
Commit choice c for alternative a.
Definition: core.hpp:3152
Support::DynamicStack< Node, Heap > ds
Stack storing current path in search tree
Definition: lds.hh:83
const Choice * choice(void) const
Return choice.
Definition: lds.hpp:64
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
Definition: core.hpp:1338
bool done(void) const
Test whether probing is done.
Definition: lds.hpp:131
Heap heap
The single global heap.
Definition: heap.cpp:48
virtual bool stopped(void) const
Check whether engine has been stopped.
Definition: lds.hpp:313
Tracer tracer
Search tracer.
Definition: lds.hh:81
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition: core.cpp:229
Node information.
Definition: search.hh:284
Probe< Tracer > e
The probe engine.
Definition: lds.hh:114
virtual Statistics statistics(void) const
Return statistics.
Definition: lds.hpp:319
unsigned int d
Current discrepancy.
Definition: lds.hh:118
Gecode toplevel namespace
Options opt
Search options.
Definition: lds.hh:112
void constrain(const Space &b)
Constrain future solutions to be better than b (should never be called)
Definition: lds.hpp:343
Space * snapshot(Space *s, const Options &o)
Clone space s dependening on options o.
Definition: support.hh:75
Space is failed
Definition: core.hpp:1608
const Choice * choice(void)
Create new choice for current brancher.
Definition: core.cpp:508
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60
Limited discrepancy search engine implementation.
Definition: lds.hh:109
Space is solved (no brancher left)
Definition: core.hpp:1609