this repo has no description
dekker.one
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>
41 forceinline
42 BAB<Tracer>::BAB(Space* s, const Options& o)
43 : tracer(o.tracer), opt(o), path(opt.nogoods_limit), d(0), mark(0),
44 best(nullptr) {
45 if (tracer) {
46 tracer.engine(SearchTracer::EngineType::BAB, 1U);
47 tracer.worker();
48 }
49 if ((s == nullptr) || (s->status(*this) == SS_FAILED)) {
50 fail++;
51 cur = nullptr;
52 if (!o.clone)
53 delete s;
54 } else {
55 cur = snapshot(s,opt);
56 }
57 }
58
59 template<class Tracer>
60 forceinline Space*
61 BAB<Tracer>::next(void) {
62 /*
63 * The engine maintains the following invariant:
64 * - If the current space (cur) is not nullptr, the path always points
65 * to exactly that space.
66 * - If the current space (cur) is nullptr, 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 nullptr;
82 // Recompute and add constraint if necessary
83 while (cur == nullptr) {
84 if (path.empty())
85 return nullptr;
86 cur = path.recompute(d,opt.a_d,*this,*best,mark,tracer);
87 if (cur != nullptr)
88 break;
89 path.next();
90 }
91 node++;
92 SearchTracer::EdgeInfo ei;
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) {
101 SearchTracer::NodeInfo ni(SearchTracer::NodeType::FAILED,
102 tracer.wid(), nid, *cur);
103 tracer.node(ei,ni);
104 }
105 fail++;
106 delete cur;
107 cur = nullptr;
108 path.next();
109 break;
110 case SS_SOLVED:
111 {
112 if (tracer) {
113 SearchTracer::NodeInfo ni(SearchTracer::NodeType::SOLVED,
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 = nullptr;
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 = nullptr;
134 d++;
135 }
136 const Choice* ch = path.push(*this,cur,c,nid);
137 if (tracer) {
138 SearchTracer::NodeInfo ni(SearchTracer::NodeType::BRANCH,
139 tracer.wid(), nid, *cur, ch);
140 tracer.node(ei,ni);
141 }
142 cur->commit(*ch,0);
143 break;
144 }
145 default:
146 GECODE_NEVER;
147 }
148 }
149 GECODE_NEVER;
150 return nullptr;
151 }
152
153 template<class Tracer>
154 forceinline Statistics
155 BAB<Tracer>::statistics(void) const {
156 return *this;
157 }
158
159 template<class Tracer>
160 forceinline void
161 BAB<Tracer>::constrain(const Space& b) {
162 if (best != nullptr) {
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 != nullptr)
172 cur->constrain(b);
173 mark = path.entries();
174 }
175
176 template<class Tracer>
177 forceinline void
178 BAB<Tracer>::reset(Space* s) {
179 tracer.round();
180 delete best;
181 best = nullptr;
182 path.reset();
183 d = 0;
184 mark = 0;
185 delete cur;
186 if ((s == nullptr) || (s->status(*this) == SS_FAILED)) {
187 delete s;
188 cur = nullptr;
189 } else {
190 cur = s;
191 }
192 Worker::reset();
193 }
194
195 template<class Tracer>
196 forceinline NoGoods&
197 BAB<Tracer>::nogoods(void) {
198 return path;
199 }
200
201 template<class Tracer>
202 forceinline
203 BAB<Tracer>::~BAB(void) {
204 tracer.done();
205 path.reset();
206 delete best;
207 delete cur;
208 }
209
210}}}
211
212// STATISTICS: search-seq