Generated on Thu Apr 5 2018 19:44:19 for Gecode by doxygen 1.8.13
dfs.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, 2009
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  template<class Tracer>
43  : tracer(o.tracer), opt(o), path(opt.nogoods_limit), d(0) {
44  if (tracer) {
45  tracer.engine(SearchTracer::EngineType::DFS, 1U);
46  tracer.worker();
47  }
48  if ((s == NULL) || (s->status(*this) == SS_FAILED)) {
49  fail++;
50  cur = NULL;
51  if (!opt.clone)
52  delete s;
53  } else {
54  cur = snapshot(s,opt);
55  }
56  }
57 
58  template<class Tracer>
59  forceinline void
61  tracer.round();
62  delete cur;
63  path.reset();
64  d = 0;
65  if ((s == NULL) || (s->status(*this) == SS_FAILED)) {
66  delete s;
67  cur = NULL;
68  } else {
69  cur = s;
70  }
71  Worker::reset();
72  }
73 
74  template<class Tracer>
77  return path;
78  }
79 
80  template<class Tracer>
83  /*
84  * The engine maintains the following invariant:
85  * - If the current space (cur) is not NULL, the path always points
86  * to exactly that space.
87  * - If the current space (cur) is NULL, the path always points
88  * to the next space (if there is any).
89  *
90  * This invariant is needed so that no-goods can be extracted properly
91  * when the engine is stopped or has found a solution.
92  *
93  */
94  start();
95  while (true) {
96  if (stop(opt))
97  return NULL;
98  while (cur == NULL) {
99  if (path.empty())
100  return NULL;
101  cur = path.recompute(d,opt.a_d,*this,tracer);
102  if (cur != NULL)
103  break;
104  path.next();
105  }
106  node++;
108  if (tracer && (path.entries() > 0)) {
109  typename Path<Tracer>::Edge& top = path.top();
110  ei.init(tracer.wid(), top.nid(), top.truealt(), *cur, *top.choice());
111  }
112  unsigned int nid = tracer.nid();
113  switch (cur->status(*this)) {
114  case SS_FAILED:
115  if (tracer) {
117  tracer.wid(), nid, *cur);
118  tracer.node(ei,ni);
119  }
120  fail++;
121  delete cur;
122  cur = NULL;
123  path.next();
124  break;
125  case SS_SOLVED:
126  {
127  if (tracer) {
129  tracer.wid(), nid, *cur);
130  tracer.node(ei,ni);
131  }
132  // Deletes all pending branchers
133  (void) cur->choice();
134  Space* s = cur;
135  cur = NULL;
136  path.next();
137  return s;
138  }
139  case SS_BRANCH:
140  {
141  Space* c;
142  if ((d == 0) || (d >= opt.c_d)) {
143  c = cur->clone();
144  d = 1;
145  } else {
146  c = NULL;
147  d++;
148  }
149  const Choice* ch = path.push(*this,cur,c,nid);
150  if (tracer) {
152  tracer.wid(), nid, *cur, ch);
153  tracer.node(ei,ni);
154  }
155  cur->commit(*ch,0);
156  break;
157  }
158  default:
159  GECODE_NEVER;
160  }
161  }
162  GECODE_NEVER;
163  return NULL;
164  }
165 
166  template<class Tracer>
169  return *this;
170  }
171 
172  template<class Tracer>
173  forceinline void
175  (void) b;
176  assert(false);
177  }
178 
179  template<class Tracer>
182  delete cur;
183  tracer.done();
184  path.reset();
185  }
186 
187 }}}
188 
189 // 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
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
~DFS(void)
Destructor.
Definition: dfs.hpp:181
unsigned int nid(void) const
Return node identifier.
Definition: path.hpp:103
#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
Gecode::IntSet d(v, 7)
DFS(Space *s, const Options &o)
Initialize for space s with options o.
Definition: dfs.hpp:42
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
NoGoods & nogoods(void)
Return no-goods.
Definition: dfs.hpp:76
Node representing a solution.
Definition: spacenode.hh:49
void constrain(const Space &b)
Constrain future solutions to be better than b (should never be called)
Definition: dfs.hpp:174
void commit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
Commit choice c for alternative a.
Definition: core.hpp:3152
Search tree edge for recomputation
Definition: path.hh:70
bool clone
Whether engines create a clone when being initialized.
Definition: search.hh:751
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
Space * next(void)
Search for next solution
Definition: dfs.hpp:82
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition: core.cpp:229
Node information.
Definition: search.hh:284
Statistics statistics(void) const
Return statistics.
Definition: dfs.hpp:168
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