main page
modules
namespaces
classes
files
Gecode home
Generated on Thu Feb 21 2013 23:11:48 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: 2011-09-02 19:00:55 +1000 (Fri, 02 Sep 2011) $ by $Author: tack $
15
* $Revision: 12387 $
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
~BAB
(
void
);
76
};
77
78
forceinline
79
BAB::BAB
(
Space
* s,
size_t
sz,
const
Options
& o)
80
:
Worker
(sz),
opt
(o),
d
(0),
mark
(0), best(NULL) {
81
current
(s);
82
if
(s->
status
(*
this
) ==
SS_FAILED
) {
83
fail
++;
84
cur = NULL;
85
if
(!o.
clone
)
86
delete
s;
87
}
else
{
88
cur =
snapshot
(s,opt);
89
}
90
current
(NULL);
91
current
(cur);
92
}
93
94
forceinline
Space
*
95
BAB::next
(
void
) {
96
/*
97
* The invariant maintained by the engine is:
98
* For all nodes stored at a depth less than mark, there
99
* is no guarantee of betterness. For those above the mark,
100
* betterness is guaranteed.
101
*
102
* The engine maintains the path on the stack for the current
103
* node to be explored.
104
*
105
*/
106
start
();
107
while
(
true
) {
108
while
(cur) {
109
if
(
stop
(opt,path.
size
()))
110
return
NULL;
111
node
++;
112
switch
(cur->
status
(*
this
)) {
113
case
SS_FAILED
:
114
fail
++;
115
delete
cur;
116
cur = NULL;
117
Worker::current
(NULL);
118
break
;
119
case
SS_SOLVED
:
120
// Deletes all pending branchers
121
(void) cur->
choice
();
122
delete
best;
123
best = cur;
124
cur = NULL;
125
mark = path.
entries
();
126
Worker::current
(NULL);
127
return
best->
clone
();
128
case
SS_BRANCH
:
129
{
130
Space
*
c
;
131
if
((d == 0) || (d >= opt.
c_d
)) {
132
c = cur->
clone
();
133
d = 1;
134
}
else
{
135
c = NULL;
136
d++;
137
}
138
const
Choice
* ch = path.
push
(*
this
,cur,c);
139
Worker::push
(c,ch);
140
cur->
commit
(*ch,0);
141
break
;
142
}
143
default
:
144
GECODE_NEVER
;
145
}
146
}
147
// Recompute and add constraint if necessary
148
do
{
149
if
(!path.
next
(*
this
))
150
return
NULL;
151
cur = path.
recompute
(d,opt.
a_d
,*
this
,best,mark);
152
}
while
(cur == NULL);
153
Worker::current
(cur);
154
}
155
GECODE_NEVER
;
156
return
NULL;
157
}
158
159
forceinline
Statistics
160
BAB::statistics
(
void
)
const
{
161
Statistics
s = *
this
;
162
s.
memory
+= path.
size
();
163
return
s;
164
}
165
166
forceinline
167
BAB::~BAB
(
void
) {
168
path.
reset
();
169
delete
best;
170
delete
cur;
171
}
172
173
}}}
174
175
#endif
176
177
// STATISTICS: search-sequential