Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.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.org>
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.org
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 delete ds.pop().space();
113 cur = s; d = d0; exhausted = true;
114 if (tracer)
115 tracer.ei()->invalidate();
116 Worker::reset(0);
117 }
118
119 template<class Tracer>
122 return *this;
123 }
124
125 template<class Tracer>
126 forceinline bool
128 return exhausted;
129 }
130
131 template<class Tracer>
134 tracer.done();
135 delete cur;
136 while (!ds.empty())
137 delete ds.pop().space();
138 }
139
140 template<class Tracer>
143 start();
144 while (true) {
145 if (cur == NULL) {
146 backtrack:
147 if (ds.empty())
148 return NULL;
149 if (stop(opt))
150 return NULL;
151 unsigned int a = ds.top().alt();
152 const Choice* ch = ds.top().choice();
153 unsigned int nid = ds.top().nid();
154 if (a == 0) {
155 cur = ds.pop().space();
156 if (tracer)
157 tracer.ei()->init(tracer.wid(), nid, 0, *cur, *ch);
158 cur->commit(*ch,0);
159 delete ch;
160 } else {
161 ds.top().next();
162 cur = ds.top().space()->clone();
163 if (tracer)
164 tracer.ei()->init(tracer.wid(), nid, a, *cur, *ch);
165 cur->commit(*ch,a);
166 }
167 node++;
168 d++;
169 }
170 check_discrepancy:
171 if (d == 0) {
172 Space* s = cur;
173 while (s->status(*this) == SS_BRANCH) {
174 if (stop(opt)) {
175 cur = s;
176 return NULL;
177 }
178 const Choice* ch = s->choice();
179 if (ch->alternatives() > 1)
180 exhausted = false;
181 if (tracer) {
182 unsigned int nid = tracer.nid();
184 tracer.wid(), nid, *s, ch);
185 tracer.node(*tracer.ei(),ni);
186 if (tracer)
187 tracer.ei()->init(tracer.wid(), nid, 0, *cur, *ch);
188 }
189 s->commit(*ch,0);
190 node++;
191 delete ch;
192 }
193 cur = NULL;
194 if (s->failed()) {
195 if (tracer) {
197 tracer.wid(), tracer.nid(), *s);
198 tracer.node(*tracer.ei(),ni);
199 }
200 fail++;
201 delete s;
202 goto backtrack;
203 } else {
204 if (tracer) {
206 tracer.wid(), tracer.nid(), *s);
207 tracer.node(*tracer.ei(),ni);
208 }
209 // Deletes all pending branchings
210 (void) s->choice();
211 return s;
212 }
213 } else {
214 node++;
215 switch (cur->status(*this)) {
216 case SS_FAILED:
217 if (tracer) {
219 tracer.wid(), tracer.nid(), *cur);
220 tracer.node(*tracer.ei(),ni);
221 }
222 fail++;
223 delete cur;
224 cur = NULL;
225 goto backtrack;
226 case SS_SOLVED:
227 if (tracer) {
228 tracer.skip(*tracer.ei());
229 }
230 delete cur;
231 cur = NULL;
232 goto backtrack;
233 case SS_BRANCH:
234 {
235 const Choice* ch = cur->choice();
236 unsigned int alt = ch->alternatives();
237 unsigned int nid = tracer.nid();
238 if (tracer) {
240 tracer.wid(), nid, *cur, ch);
241 tracer.node(*tracer.ei(),ni);
242 }
243 if (alt > 1) {
244 if (d < alt-1)
245 exhausted = false;
246 unsigned int d_a = (d >= alt-1) ? alt-1 : d;
247 Space* cc = cur->clone();
248 Node sn(cc,ch,d_a-1,nid);
249 ds.push(sn);
250 stack_depth(static_cast<unsigned long int>(ds.entries()));
251 if (tracer)
252 tracer.ei()->init(tracer.wid(), nid, d_a, *cur, *ch);
253 cur->commit(*ch,d_a);
254 d -= d_a;
255 } else {
256 if (tracer)
257 tracer.ei()->init(tracer.wid(), nid, 0, *cur, *ch);
258 cur->commit(*ch,0);
259 node++;
260 delete ch;
261 }
262 goto check_discrepancy;
263 }
264 default: GECODE_NEVER;
265 }
266 }
267 }
268 }
269
270 template<class Tracer>
273 : opt(o), e(opt), root(NULL), d(0) {
274 e.node = 1;
275 if (s->status(e) == SS_FAILED) {
276 e.fail++;
277 e.init(NULL);
278 } else {
279 Space* c = snapshot(s,opt);
280 if (opt.d_l > 0) {
281 root = c->clone();
282 }
283 e.init(c);
284 }
285 }
286
287 template<class Tracer>
288 Space*
290 while (true) {
291 Space* s = e.next(opt);
292 if (s != NULL)
293 return s;
294 if (((s == NULL) && e.stopped()) || (++d > opt.d_l) || e.done())
295 break;
296 if (d == opt.d_l) {
297 if (root != NULL)
298 e.reset(root,d);
299 root = NULL;
300 } else if (root != NULL) {
301 e.reset(root->clone(),d);
302 }
303 }
304 return NULL;
305 }
306
307 template<class Tracer>
308 bool
310 return e.stopped();
311 }
312
313 template<class Tracer>
316 return e.statistics();
317 }
318
319
320 template<class Tracer>
321 forceinline void
323 delete root; root=NULL; d=0;
324 e.node = 1;
325 if ((s == NULL) || (s->status(e) == SS_FAILED)) {
326 delete s;
327 e.fail++;
328 e.reset(NULL,0);
329 } else {
330 if (opt.d_l > 0) {
331 root = s->clone();
332 }
333 e.reset(s,0);
334 }
335 }
336
337 template<class Tracer>
338 forceinline void
340 (void) b;
341 assert(false);
342 }
343
344 template<class Tracer>
346 delete root;
347 }
348
349}}}
350
351// STATISTICS: search-seq
struct Gecode::@603::NNF::@65::@66 b
For binary nodes (and, or, eqv)
struct Gecode::@603::NNF::@65::@67 a
For atomic nodes.
Choice for performing commit
Definition core.hpp:1412
unsigned int alternatives(void) const
Return number of alternatives.
Definition core.hpp:3770
@ FAILED
A solution node.
Definition search.hh:278
@ BRANCH
A failed node.
Definition search.hh:279
@ LDS
Engine is a LDS engine.
Definition search.hh:196
virtual bool stopped(void) const
Check whether engine has been stopped.
Definition base.hpp:56
virtual T * next(void)
Return next solution (NULL, 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:746
unsigned int d_l
Discrepancy limit (for LDS)
Definition search.hh:757
Limited discrepancy search engine implementation.
Definition lds.hh:105
Probe< Tracer > e
The probe engine.
Definition lds.hh:110
LDS(Space *s, const Options &o)
Initialize for space s with options o.
Definition lds.hpp:272
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:127
~Probe(void)
Destructor.
Definition lds.hpp:133
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:142
Statistics statistics(void) const
Return statistics.
Definition lds.hpp:121
Search engine statistics
Definition search.hh:147
Computation spaces.
Definition core.hpp:1742
void reset(void)
Reset information.
Definition core.hpp:4690
Heap heap
The single global heap.
Definition heap.cpp:44
bool failed(void) const
Check whether space is failed.
Definition core.hpp:4044
void fail(void)
Fail space.
Definition core.hpp:4030
const Choice * choice(void)
Create new choice for current brancher.
Definition core.cpp:537
void commit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
Commit choice c for alternative a.
Definition core.hpp:3232
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition core.cpp:252
Space * clone(CloneStatistics &stat=unused_clone) const
Clone space.
Definition core.hpp:3224
@ SS_BRANCH
Space must be branched (at least one brancher left)
Definition core.hpp:1684
@ SS_SOLVED
Space is solved (no brancher left)
Definition core.hpp:1683
@ SS_FAILED
Space is failed
Definition core.hpp:1682
Gecode toplevel namespace
#define forceinline
Definition config.hpp:187
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56