Generated on Fri Jan 10 2020 11:38:25 for Gecode by doxygen 1.8.16
bab.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  * Contributing authors:
7  * Guido Tack <tack@gecode.org>
8  *
9  * Copyright:
10  * Christian Schulte, 2004
11  * Guido Tack, 2004
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  template<class Tracer>
43  : tracer(o.tracer), opt(o), path(opt.nogoods_limit), d(0), mark(0),
44  best(NULL) {
45  if (tracer) {
46  tracer.engine(SearchTracer::EngineType::BAB, 1U);
47  tracer.worker();
48  }
49  if ((s == NULL) || (s->status(*this) == SS_FAILED)) {
50  fail++;
51  cur = NULL;
52  if (!o.clone)
53  delete s;
54  } else {
55  cur = snapshot(s,opt);
56  }
57  }
58 
59  template<class Tracer>
62  /*
63  * The engine maintains the following invariant:
64  * - If the current space (cur) is not NULL, the path always points
65  * to exactly that space.
66  * - If the current space (cur) is NULL, the path always points
67  * to the next space (if there is any).
68  *
69  * This invariant is needed so that no-goods can be extracted properly
70  * when the engine is stopped or has found a solution.
71  *
72  * An additional invariant maintained by the engine is:
73  * For all nodes stored at a depth less than mark, there
74  * is no guarantee of betterness. For those above the mark,
75  * betterness is guaranteed.
76  *
77  */
78  start();
79  while (true) {
80  if (stop(opt))
81  return NULL;
82  // Recompute and add constraint if necessary
83  while (cur == NULL) {
84  if (path.empty())
85  return NULL;
86  cur = path.recompute(d,opt.a_d,*this,*best,mark,tracer);
87  if (cur != NULL)
88  break;
89  path.next();
90  }
91  node++;
93  if (tracer && (path.entries() > 0)) {
94  typename Path<Tracer>::Edge& top = path.top();
95  ei.init(tracer.wid(), top.nid(), top.truealt(), *cur, *top.choice());
96  }
97  unsigned int nid = tracer.nid();
98  switch (cur->status(*this)) {
99  case SS_FAILED:
100  if (tracer) {
102  tracer.wid(), nid, *cur);
103  tracer.node(ei,ni);
104  }
105  fail++;
106  delete cur;
107  cur = NULL;
108  path.next();
109  break;
110  case SS_SOLVED:
111  {
112  if (tracer) {
114  tracer.wid(), nid, *cur);
115  tracer.node(ei,ni);
116  }
117  // Deletes all pending branchers
118  (void) cur->choice();
119  delete best;
120  best = cur;
121  cur = NULL;
122  path.next();
123  mark = path.entries();
124  }
125  return best->clone();
126  case SS_BRANCH:
127  {
128  Space* c;
129  if ((d == 0) || (d >= opt.c_d)) {
130  c = cur->clone();
131  d = 1;
132  } else {
133  c = NULL;
134  d++;
135  }
136  const Choice* ch = path.push(*this,cur,c,nid);
137  if (tracer) {
139  tracer.wid(), nid, *cur, ch);
140  tracer.node(ei,ni);
141  }
142  cur->commit(*ch,0);
143  break;
144  }
145  default:
146  GECODE_NEVER;
147  }
148  }
149  GECODE_NEVER;
150  return NULL;
151  }
152 
153  template<class Tracer>
156  return *this;
157  }
158 
159  template<class Tracer>
160  forceinline void
162  if (best != NULL) {
163  // Check whether b is in fact better than best
164  best->constrain(b);
165  if (best->status(*this) != SS_FAILED)
166  return;
167  else
168  delete best;
169  }
170  best = b.clone();
171  if (cur != NULL)
172  cur->constrain(b);
173  mark = path.entries();
174  }
175 
176  template<class Tracer>
177  forceinline void
179  tracer.round();
180  delete best;
181  best = NULL;
182  path.reset();
183  d = 0;
184  mark = 0;
185  delete cur;
186  if ((s == NULL) || (s->status(*this) == SS_FAILED)) {
187  delete s;
188  cur = NULL;
189  } else {
190  cur = s;
191  }
192  Worker::reset();
193  }
194 
195  template<class Tracer>
198  return path;
199  }
200 
201  template<class Tracer>
204  tracer.done();
205  path.reset();
206  delete best;
207  delete cur;
208  }
209 
210 }}}
211 
212 // STATISTICS: search-seq
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
unsigned int truealt(void) const
Return true number for alternatives (excluding lao optimization)
Definition: path.hpp:67
Space is solved (no brancher left)
Definition: core.hpp:1683
BAB(Space *s, const Options &o)
Initialize with space s and search options o.
Definition: bab.hpp:42
Search engine options
Definition: search.hh:746
unsigned long int fail
Number of failed nodes in search tree.
Definition: search.hh:150
void * mark(void *p)
Return marked pointer for unmarked pointer p.
Space * next(void)
Search for next better solution
Definition: bab.hpp:61
NoGoods & nogoods(void)
Return no-goods.
Definition: bab.hpp:197
Space * snapshot(Space *s, const Options &o)
Clone space s dependening on options o.
Definition: support.hh:71
Space must be branched (at least one brancher left)
Definition: core.hpp:1684
Computation spaces.
Definition: core.hpp:1742
Gecode toplevel namespace
void constrain(const Space &b)
Constrain future solutions to be better than b.
Definition: bab.hpp:161
No-goods recorded from restarts.
Definition: core.hpp:1588
Options opt
The options.
Definition: test.cpp:97
unsigned int nid(void) const
Return node identifier.
Definition: path.hpp:99
void stop(Support::Timer &timer, std::ostream &os)
Get time since start of timer and print user friendly time information.
Definition: script.cpp:42
Search tree edge for recomputation
Definition: path.hh:66
~BAB(void)
Destructor.
Definition: bab.hpp:203
const Choice & choice(void) const
Return corresponding choice.
Definition: tracer.hpp:191
Node information.
Definition: search.hh:282
const unsigned int nogoods_limit
Depth limit for no-good generation during search.
Definition: search.hh:131
Node representing a branch.
Definition: spacenode.hh:47
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:56
const Choice * choice(void) const
Return choice.
Definition: path.hpp:93
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition: core.cpp:252
Statistics statistics(void) const
Return statistics.
Definition: bab.hpp:155
Edge information.
Definition: search.hh:242
Gecode::IntSet d(v, 7)
void init(unsigned int wid, unsigned int nid, unsigned int a)
Initialize.
Definition: tracer.hpp:107
void path(Home home, int offset, const IntVarArgs &x, IntVar s, IntVar e, IntPropLevel ipl)
Post propagator such that x forms a Hamiltonian path.
Definition: circuit.cpp:124
#define forceinline
Definition: config.hpp:185
Gecode::FloatVal c(-8, 8)
void reset(void)
Reset.
Definition: statistics.hpp:39
Choice for performing commit
Definition: core.hpp:1412
bool clone
Whether engines create a clone when being initialized.
Definition: search.hh:749
Node representing failure.
Definition: spacenode.hh:46
Search engine statistics
Definition: search.hh:147
Space is failed
Definition: core.hpp:1682
Node representing a solution.
Definition: spacenode.hh:45