main page
modules
namespaces
classes
files
Gecode home
Generated on Sat May 25 2013 18:00:40 for Gecode by
doxygen
1.8.3.1
gecode
search
sequential
bab.hh
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
* Last modified:
14
* $Date: 2013-03-07 20:56:21 +0100 (Thu, 07 Mar 2013) $ by $Author: schulte $
15
* $Revision: 13463 $
16
*
17
* This file is part of Gecode, the generic constraint
18
* development environment:
19
* http://www.gecode.org
20
*
21
* Permission is hereby granted, free of charge, to any person obtaining
22
* a copy of this software and associated documentation files (the
23
* "Software"), to deal in the Software without restriction, including
24
* without limitation the rights to use, copy, modify, merge, publish,
25
* distribute, sublicense, and/or sell copies of the Software, and to
26
* permit persons to whom the Software is furnished to do so, subject to
27
* the following conditions:
28
*
29
* The above copyright notice and this permission notice shall be
30
* included in all copies or substantial portions of the Software.
31
*
32
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
33
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
34
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
35
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
36
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
37
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
38
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
39
*
40
*/
41
42
#ifndef __GECODE_SEARCH_SEQUENTIAL_BAB_HH__
43
#define __GECODE_SEARCH_SEQUENTIAL_BAB_HH__
44
45
#include <
gecode/search.hh
>
46
#include <
gecode/search/support.hh
>
47
#include <
gecode/search/worker.hh
>
48
#include <
gecode/search/sequential/path.hh
>
49
50
namespace
Gecode {
namespace
Search {
namespace
Sequential {
51
53
class
BAB
:
public
Worker
{
54
private
:
56
Options
opt;
58
Path
path;
60
Space
* cur;
62
unsigned
int
d;
64
int
mark;
66
Space
* best;
67
public
:
69
BAB
(
Space
* s,
size_t
sz,
const
Options
& o);
71
Space
*
next
(
void
);
73
Statistics
statistics
(
void
)
const
;
75
void
reset
(
Space
* s);
77
~BAB
(
void
);
78
};
79
80
forceinline
81
BAB::BAB
(
Space
* s,
size_t
sz,
const
Options
& o)
82
:
Worker
(sz),
opt
(o),
d
(0),
mark
(0), best(NULL) {
83
current
(s);
84
if
(s->
status
(*
this
) ==
SS_FAILED
) {
85
fail
++;
86
cur = NULL;
87
if
(!o.
clone
)
88
delete
s;
89
}
else
{
90
cur =
snapshot
(s,opt);
91
}
92
current
(NULL);
93
current
(cur);
94
}
95
96
forceinline
Space
*
97
BAB::next
(
void
) {
98
/*
99
* The invariant maintained by the engine is:
100
* For all nodes stored at a depth less than mark, there
101
* is no guarantee of betterness. For those above the mark,
102
* betterness is guaranteed.
103
*
104
* The engine maintains the path on the stack for the current
105
* node to be explored.
106
*
107
*/
108
start
();
109
while
(
true
) {
110
while
(cur) {
111
if
(
stop
(opt,path.
size
()))
112
return
NULL;
113
node
++;
114
switch
(cur->
status
(*
this
)) {
115
case
SS_FAILED
:
116
fail
++;
117
delete
cur;
118
cur = NULL;
119
Worker::current
(NULL);
120
break
;
121
case
SS_SOLVED
:
122
// Deletes all pending branchers
123
(void) cur->
choice
();
124
delete
best;
125
best = cur;
126
cur = NULL;
127
mark = path.
entries
();
128
Worker::current
(NULL);
129
return
best->
clone
();
130
case
SS_BRANCH
:
131
{
132
Space
*
c
;
133
if
((d == 0) || (d >= opt.
c_d
)) {
134
c = cur->
clone
();
135
d = 1;
136
}
else
{
137
c = NULL;
138
d++;
139
}
140
const
Choice
* ch = path.
push
(*
this
,cur,c);
141
Worker::push
(c,ch);
142
cur->
commit
(*ch,0);
143
break
;
144
}
145
default
:
146
GECODE_NEVER
;
147
}
148
}
149
// Recompute and add constraint if necessary
150
do
{
151
if
(!path.
next
(*
this
))
152
return
NULL;
153
cur = path.
recompute
(d,opt.
a_d
,*
this
,best,mark);
154
}
while
(cur == NULL);
155
Worker::current
(cur);
156
}
157
GECODE_NEVER
;
158
return
NULL;
159
}
160
161
forceinline
Statistics
162
BAB::statistics
(
void
)
const
{
163
Statistics
s = *
this
;
164
s.
memory
+= path.
size
();
165
return
s;
166
}
167
168
forceinline
void
169
BAB::reset
(
Space
* s) {
170
delete
best;
171
best = NULL;
172
path.
reset
();
173
d = mark = 0;
174
delete
cur;
175
if
(s->
status
(*
this
) ==
SS_FAILED
) {
176
cur = NULL;
177
Worker::reset
();
178
}
else
{
179
cur = s;
180
Worker::reset
(cur);
181
}
182
}
183
184
forceinline
185
BAB::~BAB
(
void
) {
186
path.
reset
();
187
delete
best;
188
delete
cur;
189
}
190
191
}}}
192
193
#endif
194
195
// STATISTICS: search-sequential