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