Generated on for Gecode by doxygen 1.17.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.dev>
5 *
6 * Contributing authors:
7 * Guido Tack <tack@gecode.dev>
8 * Mikael Zayenz Lagerkvist <lagerkvist@gecode.dev>
9 *
10 * Copyright:
11 * Christian Schulte, 2004
12 * Guido Tack, 2004
13 * Mikael Zayenz Lagerkvist, 2026
14 *
15 * This file is part of Gecode, the generic constraint
16 * development environment:
17 * http://www.gecode.dev
18 *
19 * Permission is hereby granted, free of charge, to any person obtaining
20 * a copy of this software and associated documentation files (the
21 * "Software"), to deal in the Software without restriction, including
22 * without limitation the rights to use, copy, modify, merge, publish,
23 * distribute, sublicense, and/or sell copies of the Software, and to
24 * permit persons to whom the Software is furnished to do so, subject to
25 * the following conditions:
26 *
27 * The above copyright notice and this permission notice shall be
28 * included in all copies or substantial portions of the Software.
29 *
30 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37 *
38 */
39
40namespace Gecode { namespace Search { namespace Seq {
41
42 template<class Tracer>
45 : tracer(o.tracer), opt(o), path(opt.nogoods_limit), d(0), mark(0),
46 best(nullptr) {
47 if (tracer) {
48 tracer.engine(SearchTracer::EngineType::BAB, 1U);
49 tracer.worker();
50 }
51 if ((s == nullptr) || (s->status(*this) == SS_FAILED)) {
52 fail++;
53 cur = nullptr;
54 if (!o.clone)
55 delete s;
56 } else {
57 cur = snapshot(s,opt);
58 }
59 }
60
61 template<class Tracer>
64 /*
65 * The engine maintains the following invariant:
66 * - If the current space (cur) is not nullptr, the path always points
67 * to exactly that space.
68 * - If the current space (cur) is nullptr, the path always points
69 * to the next space (if there is any).
70 *
71 * This invariant is needed so that no-goods can be extracted properly
72 * when the engine is stopped or has found a solution.
73 *
74 * An additional invariant maintained by the engine is:
75 * For all nodes stored at a depth less than mark, there
76 * is no guarantee of betterness. For those above the mark,
77 * betterness is guaranteed.
78 *
79 */
80 start();
81 while (true) {
82 // An exhausted search is complete, even when a limit has been reached
83 if ((cur == nullptr) && path.empty())
84 return nullptr;
85 if (stop_seq(opt))
86 return nullptr;
87 // Recompute and add constraint if necessary
88 while (cur == nullptr) {
89 if (path.empty())
90 return nullptr;
91 cur = path.recompute(d,opt.a_d,*this,best,mark,tracer);
92 if (cur != nullptr)
93 break;
94 path.next();
95 }
96 node++;
98 if (tracer && (path.entries() > 0)) {
99 typename Path<Tracer>::Edge& top = path.top();
100 ei.init(tracer.wid(), top.nid(), top.truealt(), *cur, *top.choice());
101 }
102 unsigned int nid = tracer.nid();
103 switch (cur->status(*this)) {
104 case SS_FAILED:
105 if (tracer) {
107 tracer.wid(), nid, *cur);
108 tracer.node(ei,ni);
109 }
110 fail++;
111 delete cur;
112 cur = nullptr;
113 path.next();
114 break;
115 case SS_SOLVED:
116 {
117 if (tracer) {
119 tracer.wid(), nid, *cur);
120 tracer.node(ei,ni);
121 }
122 // Deletes all pending branchers
123 (void) cur->choice();
124 delete best;
125 best = cur;
126 cur = nullptr;
127 path.next();
128 mark = path.entries();
129 }
130 return best->clone();
131 case SS_BRANCH:
132 {
133 Space* c;
134 if ((d == 0) || (d >= opt.c_d)) {
135 c = cur->clone();
136 d = 1;
137 } else {
138 c = nullptr;
139 d++;
140 }
141 const Choice* ch = path.push(*this,cur,c,nid);
142 if (tracer) {
144 tracer.wid(), nid, *cur, ch);
145 tracer.node(ei,ni);
146 }
147 cur->commit(*ch,0);
148 break;
149 }
150 default:
152 }
153 }
155 return nullptr;
156 }
157
158 template<class Tracer>
161 return *this;
162 }
163
164 template<class Tracer>
165 forceinline void
167 if (best != nullptr) {
168 // Check whether b is in fact better than best
169 best->constrain(b);
170 if (best->status(*this) != SS_FAILED)
171 return;
172 else
173 delete best;
174 }
175 best = b.clone();
176 if (cur != nullptr)
177 cur->constrain(b);
178 mark = path.entries();
179 }
180
181 template<class Tracer>
182 forceinline void
184 tracer.round();
185 delete best;
186 best = nullptr;
187 path.reset();
188 d = 0;
189 mark = 0;
190 delete cur;
191 // Reset the statistics first, so that a failed root is counted
193 if (s == nullptr) {
194 cur = nullptr;
195 } else if (s->status(*this) == SS_FAILED) {
196 fail++;
197 delete s;
198 cur = nullptr;
199 } else {
200 cur = s;
201 }
202 }
203
204 template<class Tracer>
207 return path;
208 }
209
210 template<class Tracer>
213 tracer.done();
214 path.reset();
215 delete best;
216 delete cur;
217 }
218
219}}}
220
221// STATISTICS: search-seq
Choice for performing commit
Definition core.hpp:1430
No-goods recorded from restarts.
Definition core.hpp:1606
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:286
@ BRANCH
A failed node.
Definition search.hh:287
@ BAB
Engine is a BAB engine.
Definition search.hh:203
Search engine options
Definition search.hh:848
BAB(Space *s, const Options &o)
Initialize with space s and search options o.
Definition bab.hpp:44
~BAB(void)
Destructor.
Definition bab.hpp:212
NoGoods & nogoods(void)
Return no-goods.
Definition bab.hpp:206
Space * next(void)
Search for next better solution
Definition bab.hpp:63
void constrain(const Space &b)
Constrain future solutions to be better than b.
Definition bab.hpp:166
Statistics statistics(void) const
Return statistics.
Definition bab.hpp:160
Search tree edge for recomputation
Definition path.hh:70
unsigned int truealt(void) const
Return true number for alternatives (excluding lao optimization).
Definition path.hpp:71
unsigned int nid(void) const
Return node identifier.
Definition path.hpp:103
const Choice * choice(void) const
Return choice.
Definition path.hpp:97
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_seq(Options &o)
Check stop and wait for admission of a sequential worker.
Definition worker.hh:89
Computation spaces.
Definition core.hpp:1787
void reset(void)
Reset information.
Definition core.hpp:4974
SpaceStatus status(StatusStatistics &stat)
Query space status.
Definition core.cpp:281
@ 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