Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
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
38namespace 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:
147 }
148 }
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 }
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::@603::NNF::@65::@66 b
For binary nodes (and, or, eqv)
Choice for performing commit
Definition core.hpp:1412
No-goods recorded from restarts.
Definition core.hpp:1588
void init(unsigned int wid, unsigned int nid, unsigned int a)
Initialize.
Definition tracer.hpp:107
unsigned int nid(void) const
Return parent node id.
Definition tracer.hpp:142
@ FAILED
A solution node.
Definition search.hh:278
@ BRANCH
A failed node.
Definition search.hh:279
@ BAB
Engine is a BAB engine.
Definition search.hh:195
Search engine options
Definition search.hh:746
BAB(Space *s, const Options &o)
Initialize with space s and search options o.
Definition bab.hpp:42
~BAB(void)
Destructor.
Definition bab.hpp:203
NoGoods & nogoods(void)
Return no-goods.
Definition bab.hpp:197
Space * next(void)
Search for next better solution
Definition bab.hpp:61
void constrain(const Space &b)
Constrain future solutions to be better than b.
Definition bab.hpp:161
Statistics statistics(void) const
Return statistics.
Definition bab.hpp:155
Search tree edge for recomputation
Definition path.hh:66
unsigned int truealt(void) const
Return true number for alternatives (excluding lao optimization)
Definition path.hpp:67
unsigned int nid(void) const
Return node identifier.
Definition path.hpp:99
const Choice * choice(void) const
Return choice.
Definition path.hpp:93
Search engine statistics
Definition search.hh:147
Computation spaces.
Definition core.hpp:1742
void reset(void)
Reset information.
Definition core.hpp:4690
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition core.cpp:252
@ 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
void path(Home home, const IntVarArgs &x, IntVar s, IntVar e, IntPropLevel ipl=IPL_DEF)
Post propagator such that x forms a Hamiltonian path.
Definition circuit.cpp:169
#define forceinline
Definition config.hpp:187
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56