Generated on Thu Apr 5 2018 19:44:19 for Gecode by doxygen 1.8.13
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  * Last modified:
14  * $Date$ by $Author$
15  * $Revision$
16  *
17  * This file is part of Gecode, the generic constraint
18  * development environment:
19  * http://www.gecode.org
20  *
21  * Permission is hereby granted, free of charge, to any person obtaining
22  * a copy of this software and associated documentation files (the
23  * "Software"), to deal in the Software without restriction, including
24  * without limitation the rights to use, copy, modify, merge, publish,
25  * distribute, sublicense, and/or sell copies of the Software, and to
26  * permit persons to whom the Software is furnished to do so, subject to
27  * the following conditions:
28  *
29  * The above copyright notice and this permission notice shall be
30  * included in all copies or substantial portions of the Software.
31  *
32  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
33  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
34  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
35  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
36  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
37  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
38  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
39  *
40  */
41 
42 namespace Gecode { namespace Search { namespace Seq {
43 
44  template<class Tracer>
47  : tracer(o.tracer), opt(o), path(opt.nogoods_limit), d(0), mark(0),
48  best(NULL) {
49  if (tracer) {
50  tracer.engine(SearchTracer::EngineType::BAB, 1U);
51  tracer.worker();
52  }
53  if ((s == NULL) || (s->status(*this) == SS_FAILED)) {
54  fail++;
55  cur = NULL;
56  if (!o.clone)
57  delete s;
58  } else {
59  cur = snapshot(s,opt);
60  }
61  }
62 
63  template<class Tracer>
66  /*
67  * The engine maintains the following invariant:
68  * - If the current space (cur) is not NULL, the path always points
69  * to exactly that space.
70  * - If the current space (cur) is NULL, the path always points
71  * to the next space (if there is any).
72  *
73  * This invariant is needed so that no-goods can be extracted properly
74  * when the engine is stopped or has found a solution.
75  *
76  * An additional invariant maintained by the engine is:
77  * For all nodes stored at a depth less than mark, there
78  * is no guarantee of betterness. For those above the mark,
79  * betterness is guaranteed.
80  *
81  */
82  start();
83  while (true) {
84  if (stop(opt))
85  return NULL;
86  // Recompute and add constraint if necessary
87  while (cur == NULL) {
88  if (path.empty())
89  return NULL;
90  cur = path.recompute(d,opt.a_d,*this,*best,mark,tracer);
91  if (cur != NULL)
92  break;
93  path.next();
94  }
95  node++;
97  if (tracer && (path.entries() > 0)) {
98  typename Path<Tracer>::Edge& top = path.top();
99  ei.init(tracer.wid(), top.nid(), top.truealt(), *cur, *top.choice());
100  }
101  unsigned int nid = tracer.nid();
102  switch (cur->status(*this)) {
103  case SS_FAILED:
104  if (tracer) {
106  tracer.wid(), nid, *cur);
107  tracer.node(ei,ni);
108  }
109  fail++;
110  delete cur;
111  cur = NULL;
112  path.next();
113  break;
114  case SS_SOLVED:
115  {
116  if (tracer) {
118  tracer.wid(), nid, *cur);
119  tracer.node(ei,ni);
120  }
121  // Deletes all pending branchers
122  (void) cur->choice();
123  delete best;
124  best = cur;
125  cur = NULL;
126  path.next();
127  mark = path.entries();
128  }
129  return best->clone();
130  case SS_BRANCH:
131  {
132  Space* c;
133  if ((d == 0) || (d >= opt.c_d)) {
134  c = cur->clone();
135  d = 1;
136  } else {
137  c = NULL;
138  d++;
139  }
140  const Choice* ch = path.push(*this,cur,c,nid);
141  if (tracer) {
143  tracer.wid(), nid, *cur, ch);
144  tracer.node(ei,ni);
145  }
146  cur->commit(*ch,0);
147  break;
148  }
149  default:
150  GECODE_NEVER;
151  }
152  }
153  GECODE_NEVER;
154  return NULL;
155  }
156 
157  template<class Tracer>
160  return *this;
161  }
162 
163  template<class Tracer>
164  forceinline void
166  if (best != NULL) {
167  // Check whether b is in fact better than best
168  best->constrain(b);
169  if (best->status(*this) != SS_FAILED)
170  return;
171  else
172  delete best;
173  }
174  best = b.clone();
175  if (cur != NULL)
176  cur->constrain(b);
177  mark = path.entries();
178  }
179 
180  template<class Tracer>
181  forceinline void
183  tracer.round();
184  delete best;
185  best = NULL;
186  path.reset();
187  d = 0;
188  mark = 0;
189  delete cur;
190  if ((s == NULL) || (s->status(*this) == SS_FAILED)) {
191  delete s;
192  cur = NULL;
193  } else {
194  cur = s;
195  }
196  Worker::reset();
197  }
198 
199  template<class Tracer>
202  return path;
203  }
204 
205  template<class Tracer>
208  tracer.done();
209  path.reset();
210  delete best;
211  delete cur;
212  }
213 
214 }}}
215 
216 // STATISTICS: search-seq
Edge information.
Definition: search.hh:244
unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance) ...
Definition: search.hh:757
Space must be branched (at least one brancher left)
Definition: core.hpp:1610
Search engine statistics
Definition: search.hh:149
Node representing a branch.
Definition: spacenode.hh:51
unsigned int c_d
Create a clone after every c_d commits (commit distance)
Definition: search.hh:755
Search engine options
Definition: search.hh:748
BAB(Space *s, const Options &o)
Initialize with space s and search options o.
Definition: bab.hpp:46
const Choice * choice(void) const
Return choice.
Definition: path.hpp:97
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:128
unsigned long int fail
Number of failed nodes in search tree.
Definition: search.hh:152
Node representing failure.
Definition: spacenode.hh:50
unsigned int nid(void) const
Return node identifier.
Definition: path.hpp:103
void constrain(const Space &b)
Constrain future solutions to be better than b.
Definition: bab.hpp:165
void * mark(void *p)
Return marked pointer for unmarked pointer p.
#define forceinline
Definition: config.hpp:182
Computation spaces.
Definition: core.hpp:1668
unsigned int truealt(void) const
Return true number for alternatives (excluding lao optimization)
Definition: path.hpp:71
~BAB(void)
Destructor.
Definition: bab.hpp:207
Gecode::IntSet d(v, 7)
void start(void)
Reset stop information.
Definition: worker.hh:78
Gecode::FloatVal c(-8, 8)
void init(unsigned int wid, unsigned int nid, unsigned int a)
Initialize.
Definition: tracer.hpp:111
Options opt
The options.
Definition: test.cpp:101
Space * clone(CloneStatistics &stat=unused_clone) const
Clone space.
Definition: core.hpp:3144
Node representing a solution.
Definition: spacenode.hh:49
void commit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
Commit choice c for alternative a.
Definition: core.hpp:3152
virtual void constrain(const Space &best)
Constrain function for best solution search.
Definition: core.cpp:807
Search tree edge for recomputation
Definition: path.hh:70
bool clone
Whether engines create a clone when being initialized.
Definition: search.hh:751
NoGoods & nogoods(void)
Return no-goods.
Definition: bab.hpp:201
struct Gecode::@585::NNF::@62::@63 b
For binary nodes (and, or, eqv)
Choice for performing commit
Definition: core.hpp:1338
No-goods recorded from restarts.
Definition: core.hpp:1514
Statistics statistics(void) const
Return statistics.
Definition: bab.hpp:159
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition: core.cpp:229
Node information.
Definition: search.hh:284
Space * next(void)
Search for next better solution
Definition: bab.hpp:65
Gecode toplevel namespace
unsigned long int node
Number of nodes expanded.
Definition: search.hh:154
const unsigned int nogoods_limit
Depth limit for no-good generation during search.
Definition: search.hh:133
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
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:1609