main page
modules
namespaces
classes
files
Gecode home
Generated on Sun Aug 9 2020 05:34:08 for Gecode by
doxygen
1.8.18
gecode
search
seq
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
38
namespace
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(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>
60
forceinline
Space
*
61
BAB<Tracer>::next
(
void
) {
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++;
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 = NULL;
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 = 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) {
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
NULL;
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 != 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
178
BAB<Tracer>::reset
(
Space
* s) {
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
}
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
Gecode::Search::Seq::Path::Edge::truealt
unsigned int truealt(void) const
Return true number for alternatives (excluding lao optimization)
Definition:
path.hpp:67
Gecode::SS_SOLVED
@ SS_SOLVED
Space is solved (no brancher left)
Definition:
core.hpp:1683
Gecode::Search::Seq::BAB::BAB
BAB(Space *s, const Options &o)
Initialize with space s and search options o.
Definition:
bab.hpp:42
Gecode::Search::Options
Search engine options
Definition:
search.hh:746
Gecode::Search::Statistics::fail
unsigned long int fail
Number of failed nodes in search tree.
Definition:
search.hh:150
Gecode::Support::mark
void * mark(void *p)
Return marked pointer for unmarked pointer p.
Definition:
marked-pointer.hpp:58
Gecode::Search::Seq::BAB::next
Space * next(void)
Search for next better solution
Definition:
bab.hpp:61
Gecode::Search::Seq::BAB::nogoods
NoGoods & nogoods(void)
Return no-goods.
Definition:
bab.hpp:197
Gecode::Search::snapshot
Space * snapshot(Space *s, const Options &o)
Clone space s dependening on options o.
Definition:
support.hh:71
Gecode::SS_BRANCH
@ SS_BRANCH
Space must be branched (at least one brancher left)
Definition:
core.hpp:1684
Gecode::Space
Computation spaces.
Definition:
core.hpp:1742
Gecode
Gecode toplevel namespace
Gecode::Search::Seq::BAB::constrain
void constrain(const Space &b)
Constrain future solutions to be better than b.
Definition:
bab.hpp:161
Gecode::NoGoods
No-goods recorded from restarts.
Definition:
core.hpp:1588
Test::opt
Options opt
The options.
Definition:
test.cpp:97
Gecode::Search::Seq::Path::Edge::nid
unsigned int nid(void) const
Return node identifier.
Definition:
path.hpp:99
Gecode::Driver::stop
void stop(Support::Timer &timer, std::ostream &os)
Get time since start of timer and print user friendly time information.
Definition:
script.cpp:42
Gecode::Search::Seq::Path::Edge
Search tree edge for recomputation
Definition:
path.hh:66
Gecode::Search::Seq::BAB::~BAB
~BAB(void)
Destructor.
Definition:
bab.hpp:203
Gecode::SearchTracer::NodeInfo
Node information.
Definition:
search.hh:282
Gecode::Search::Config::nogoods_limit
const unsigned int nogoods_limit
Depth limit for no-good generation during search.
Definition:
search.hh:131
b
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
Gecode::Gist::BRANCH
@ BRANCH
Node representing a branch.
Definition:
spacenode.hh:47
GECODE_NEVER
#define GECODE_NEVER
Assert that this command is never executed.
Definition:
macros.hpp:56
Gecode::Search::Seq::Path::Edge::choice
const Choice * choice(void) const
Return choice.
Definition:
path.hpp:93
Gecode::Space::status
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition:
core.cpp:252
Gecode::Search::Seq::BAB::statistics
Statistics statistics(void) const
Return statistics.
Definition:
bab.hpp:155
Gecode::SearchTracer::EdgeInfo
Edge information.
Definition:
search.hh:242
Test::Int::Distinct::d
Gecode::IntSet d(v, 7)
Gecode::SearchTracer::EdgeInfo::init
void init(unsigned int wid, unsigned int nid, unsigned int a)
Initialize.
Definition:
tracer.hpp:107
Gecode::path
void path(Home home, int offset, const IntVarArgs &x, IntVar s, IntVar e, IntPropLevel ipl)
Post propagator such that x forms a Hamiltonian path.
Definition:
circuit.cpp:124
forceinline
#define forceinline
Definition:
config.hpp:185
Test::Float::Arithmetic::c
Gecode::FloatVal c(-8, 8)
Gecode::Search::Statistics::reset
void reset(void)
Reset.
Definition:
statistics.hpp:39
Gecode::Choice
Choice for performing commit
Definition:
core.hpp:1412
Gecode::Search::Options::clone
bool clone
Whether engines create a clone when being initialized.
Definition:
search.hh:749
Gecode::Gist::FAILED
@ FAILED
Node representing failure.
Definition:
spacenode.hh:46
Gecode::Search::Statistics
Search engine statistics
Definition:
search.hh:147
Gecode::SS_FAILED
@ SS_FAILED
Space is failed
Definition:
core.hpp:1682
Gecode::Gist::SOLVED
@ SOLVED
Node representing a solution.
Definition:
spacenode.hh:45