Generated on Thu Mar 16 2017 03:24:23 for Gecode by doxygen 1.8.13
lds.hh
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: 2016-10-25 12:52:26 +0200 (Tue, 25 Oct 2016) $ by $Author: schulte $
11  * $Revision: 15233 $
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 #ifndef __GECODE_SEARCH_SEQUENTIAL_LDS_HH__
39 #define __GECODE_SEARCH_SEQUENTIAL_LDS_HH__
40 
41 #include <gecode/search.hh>
42 #include <gecode/search/support.hh>
43 #include <gecode/search/worker.hh>
44 
45 namespace Gecode { namespace Search { namespace Sequential {
46 
48  class Probe : public Worker {
49  protected:
51  class Node {
52  private:
54  Space* _space;
56  const Choice* _choice;
58  unsigned int _alt;
59  public:
61  Node(void);
63  Node(Space* s, const Choice* c, unsigned int a);
65  Space* space(void) const;
67  const Choice* choice(void) const;
69  unsigned int alt(void) const;
71  void next(void);
72  };
78  unsigned int d;
80  bool exhausted;
81  public:
83  Probe(void);
85  void init(Space* s);
87  void reset(Space* s, unsigned int d);
89  Statistics statistics(void) const;
91  ~Probe(void);
93  Space* next(const Options& o);
95  bool done(void) const;
96  };
97 
99  class LDS : public Engine {
100  protected:
108  unsigned int d;
111  public:
113  LDS(Space* s, const Options& o);
115  virtual Space* next(void);
117  virtual Statistics statistics(void) const;
119  void constrain(const Space& b);
121  void reset(Space* s);
123  virtual bool stopped(void) const;
125  virtual ~LDS(void);
126  };
127 
128  /*
129  * Nodes for the probing engine (just remember next alternative
130  * to try)
131  *
132  */
133 
136 
138  Probe::Node::Node(Space* s, const Choice* c, unsigned int a)
139  : _space(s), _choice(c), _alt(a) {}
140 
142  Probe::Node::space(void) const {
143  return _space;
144  }
145 
146  forceinline const Choice*
147  Probe::Node::choice(void) const {
148  return _choice;
149  }
150 
151  forceinline unsigned int
152  Probe::Node::alt(void) const {
153  return _alt;
154  }
155 
156  forceinline void
158  _alt--;
159  }
160 
161 
162  /*
163  * The probing engine: computes all solutions with
164  * exact number of discrepancies (solutions with
165  * fewer discrepancies are discarded)
166  *
167  */
168 
171  : ds(heap) {}
172 
173  forceinline void
175  cur = s; d = 0U; exhausted = true;
176  }
177 
178  forceinline void
179  Probe::reset(Space* s, unsigned int d0) {
180  delete cur;
181  while (!ds.empty())
182  delete ds.pop().space();
183  cur = s; d = d0; exhausted = true;
184  Worker::reset(0);
185  }
186 
188  Probe::statistics(void) const {
189  return *this;
190  }
191 
192  forceinline bool
193  Probe::done(void) const {
194  return exhausted;
195  }
196 
199  delete cur;
200  while (!ds.empty())
201  delete ds.pop().space();
202  }
203 
206  start();
207  while (true) {
208  if (cur == NULL) {
209  backtrack:
210  if (ds.empty())
211  return NULL;
212  if (stop(opt))
213  return NULL;
214  unsigned int a = ds.top().alt();
215  const Choice* ch = ds.top().choice();
216  if (a == 0) {
217  cur = ds.pop().space();
218  cur->commit(*ch,0);
219  delete ch;
220  } else {
221  ds.top().next();
222  cur = ds.top().space()->clone();
223  cur->commit(*ch,a);
224  }
225  node++;
226  d++;
227  }
228  check_discrepancy:
229  if (d == 0) {
230  Space* s = cur;
231  while (s->status(*this) == SS_BRANCH) {
232  if (stop(opt)) {
233  cur = s;
234  return NULL;
235  }
236  const Choice* ch = s->choice();
237  if (ch->alternatives() > 1)
238  exhausted = false;
239  s->commit(*ch,0);
240  node++;
241  delete ch;
242  }
243  cur = NULL;
244  if (s->failed()) {
245  fail++;
246  delete s;
247  goto backtrack;
248  }
249  // Deletes all pending branchings
250  (void) s->choice();
251  return s;
252  }
253  node++;
254  switch (cur->status(*this)) {
255  case SS_FAILED:
256  fail++;
257  case SS_SOLVED:
258  delete cur;
259  cur = NULL;
260  goto backtrack;
261  case SS_BRANCH:
262  {
263  const Choice* ch = cur->choice();
264  unsigned int alt = ch->alternatives();
265  if (alt > 1) {
266  if (d < alt-1)
267  exhausted = false;
268  unsigned int d_a = (d >= alt-1) ? alt-1 : d;
269  Space* cc = cur->clone();
270  Node sn(cc,ch,d_a-1);
271  ds.push(sn);
272  stack_depth(ds.entries());
273  cur->commit(*ch,d_a);
274  d -= d_a;
275  } else {
276  cur->commit(*ch,0);
277  node++;
278  delete ch;
279  }
280  goto check_discrepancy;
281  }
282  default: GECODE_NEVER;
283  }
284  }
285  }
286 
288  LDS::LDS(Space* s, const Options& o)
289  : opt(o), root(NULL), d(0) {
290  e.node = 1;
291  if (s->status(e) == SS_FAILED) {
292  e.fail++;
293  e.init(NULL);
294  } else {
295  Space* c = snapshot(s,opt);
296  if (opt.d_l > 0) {
297  root = c->clone();
298  }
299  e.init(c);
300  }
301  }
302 
303  forceinline void
305  delete root; root=NULL; d=0;
306  e.node = 1;
307  if ((s == NULL) || (s->status(e) == SS_FAILED)) {
308  delete s;
309  e.fail++;
310  e.reset(NULL,0);
311  } else {
312  if (opt.d_l > 0) {
313  root = s->clone();
314  }
315  e.reset(s,0);
316  }
317  }
318 
319  forceinline void
321  (void) b;
322  assert(false);
323  }
324 
325 }}}
326 
327 #endif
328 
329 // STATISTICS: search-sequential
unsigned int alternatives(void) const
Return number of alternatives.
Definition: core.hpp:3689
Search engine implementation interface
Definition: search.hh:601
Space must be branched (at least one brancher left)
Definition: core.hpp:1613
Search engine statistics
Definition: search.hh:140
Probe engine for LDS
Definition: lds.hh:48
Space * root
Root node for problem.
Definition: lds.hh:106
Search engine options
Definition: search.hh:446
Space * next(const Options &o)
Search for next solution
Definition: lds.hh:205
unsigned long int fail
Number of failed nodes in search tree.
Definition: search.hh:143
unsigned int d
Current discrepancy.
Definition: lds.hh:108
Space * clone(bool share_data=true, bool share_info=true, CloneStatistics &stat=unused_clone) const
Clone space.
Definition: core.hpp:3258
void reset(Space *s)
Reset engine to restart at space s.
Definition: lds.hh:304
bool stopped(void) const
Check whether engine has been stopped.
Definition: worker.hh:91
Computation spaces.
Definition: core.hpp:1672
unsigned int d_l
Discrepancy limit (for LDS)
Definition: search.hh:457
void start(void)
Reset stop information.
Definition: worker.hh:78
Gecode::FloatVal c(-8, 8)
struct Gecode::@554::NNF::@60::@62 a
For atomic nodes.
Options opt
The options.
Definition: test.cpp:101
void reset(Space *s, unsigned int d)
Reset with space s and discrepancy d.
Definition: lds.hh:179
Statistics statistics(void) const
Return statistics.
Definition: lds.hh:188
bool failed(void) const
Check whether space is failed.
Definition: core.hpp:3963
void commit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
Commit choice c for alternative a.
Definition: core.hpp:3266
Options opt
Search options.
Definition: lds.hh:102
Node(void)
Default constructor.
Definition: lds.hh:135
~Probe(void)
Destructor.
Definition: lds.hh:198
Node in the search tree for LDS
Definition: lds.hh:51
Space * space(void) const
Return space.
Definition: lds.hh:142
Search worker statistics
Definition: worker.hh:48
void constrain(const Space &b)
Constrain future solutions to be better than b (should never be called)
Definition: lds.hh:320
const Choice * choice(void) const
Return choice.
Definition: lds.hh:147
unsigned int alt(void) const
Return next alternative.
Definition: lds.hh:152
Probe(void)
Initialize.
Definition: lds.hh:170
void next(void)
Set next alternative
Definition: lds.hh:157
Choice for performing commit
Definition: core.hpp:1332
LDS(Space *s, const Options &o)
Initialize for space s with options o.
Definition: lds.hh:288
Probe e
The probe engine.
Definition: lds.hh:104
Heap heap
The single global heap.
Definition: heap.cpp:48
#define forceinline
Definition: config.hpp:173
bool exhausted
Whether entire search space has been exhausted.
Definition: lds.hh:80
Stack with arbitrary number of elements.
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition: core.cpp:234
Space * snapshot(Space *s, const Options &o, bool share=true)
Clone space s dependening on options o.
Definition: support.hh:75
void stack_depth(unsigned long int d)
Record stack depth d.
Definition: worker.hh:104
Gecode toplevel namespace
unsigned long int node
Number of nodes expanded.
Definition: search.hh:145
Support::DynamicStack< Node, Heap > ds
Stack storing current path in search tree
Definition: lds.hh:74
Space * cur
Current space.
Definition: lds.hh:76
Space is failed
Definition: core.hpp:1611
const Choice * choice(void)
Create new choice for current brancher.
Definition: core.cpp:354
struct Gecode::@554::NNF::@60::@61 b
For binary nodes (and, or, eqv)
bool done(void) const
Test whether probing is done.
Definition: lds.hh:193
unsigned int d
Current discrepancy.
Definition: lds.hh:78
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60
void init(Space *s)
Initialize with space s.
Definition: lds.hh:174
bool stop(const Options &o)
Check whether engine must be stopped.
Definition: worker.hh:83
void reset(void)
Reset.
Definition: statistics.hpp:43
Space is solved (no brancher left)
Definition: core.hpp:1612
Limited discrepancy search engine implementation.
Definition: lds.hh:99
bool no_solution
Solution found for current discrepancy.
Definition: lds.hh:110