main page
modules
namespaces
classes
files
Gecode home
Generated on Thu Mar 7 2013 10:21:37 for Gecode by
doxygen
1.8.3.1
gecode
kernel
brancher-view.hpp
Go to the documentation of this file.
1
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2
/*
3
* Main author:
4
* Christian Schulte <schulte@gecode.org>
5
*
6
* Copyright:
7
* Christian Schulte, 2008
8
*
9
* Last modified:
10
* $Date: 2011-05-11 20:44:17 +1000 (Wed, 11 May 2011) $ by $Author: tack $
11
* $Revision: 12001 $
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 {
39
46
47
class
EmptyViewSelChoice
{
48
public
:
50
size_t
size
(
void
)
const
;
52
void
archive
(
Archive
& e)
const
;
53
};
54
58
template
<
class
_View>
59
class
ViewSelBase
{
60
public
:
62
typedef
_View
View
;
64
typedef
EmptyViewSelChoice
Choice
;
66
ViewSelBase
(
void
);
68
ViewSelBase
(
Space
& home,
const
VarBranchOptions
& vbo);
70
EmptyViewSelChoice
choice
(
Space
& home);
72
EmptyViewSelChoice
choice
(
const
Space
& home,
Archive
& e);
74
void
commit
(
Space
& home,
const
EmptyViewSelChoice
&
c
,
unsigned
a
);
76
void
update
(
Space
& home,
bool
share,
ViewSelBase
& vs);
78
void
dispose
(
Space
& home);
79
};
80
84
template
<
class
View>
85
class
ViewSelNone
:
public
ViewSelBase
<View> {
86
public
:
88
ViewSelNone
(
void
);
90
ViewSelNone
(
Space
& home,
const
VarBranchOptions
& vbo);
92
ViewSelStatus
init
(
Space
& home,
View
x);
94
ViewSelStatus
select
(
Space
& home,
View
x);
95
};
96
100
template
<
class
View>
101
class
ViewSelDegreeMin
:
public
ViewSelBase
<View> {
102
protected
:
104
unsigned
int
degree
;
105
public
:
107
ViewSelDegreeMin
(
void
);
109
ViewSelDegreeMin
(
Space
& home,
const
VarBranchOptions
& vbo);
111
ViewSelStatus
init
(
Space
& home,
View
x);
113
ViewSelStatus
select
(
Space
& home,
View
x);
114
};
115
119
template
<
class
View>
120
class
ViewSelDegreeMax
:
public
ViewSelBase
<View> {
121
protected
:
123
unsigned
int
degree
;
124
public
:
126
ViewSelDegreeMax
(
void
);
128
ViewSelDegreeMax
(
Space
& home,
const
VarBranchOptions
& vbo);
130
ViewSelStatus
init
(
Space
& home,
View
x);
132
ViewSelStatus
select
(
Space
& home,
View
x);
133
};
134
138
template
<
class
View>
139
class
ViewSelAfcMin
:
public
ViewSelBase
<View> {
140
protected
:
142
double
afc
;
143
public
:
145
ViewSelAfcMin
(
void
);
147
ViewSelAfcMin
(
Space
& home,
const
VarBranchOptions
& vbo);
149
ViewSelStatus
init
(
Space
& home,
View
x);
151
ViewSelStatus
select
(
Space
& home,
View
x);
152
};
153
157
template
<
class
View>
158
class
ViewSelAfcMax
:
public
ViewSelBase
<View> {
159
protected
:
161
double
afc
;
162
public
:
164
ViewSelAfcMax
(
void
);
166
ViewSelAfcMax
(
Space
& home,
const
VarBranchOptions
& vbo);
168
ViewSelStatus
init
(
Space
& home,
View
x);
170
ViewSelStatus
select
(
Space
& home,
View
x);
171
};
172
174
class
ArchivedRandomGenerator
:
public
Support::RandomGenerator
{
175
public
:
177
ArchivedRandomGenerator
(
void
);
179
ArchivedRandomGenerator
(
unsigned
int
seed
);
181
ArchivedRandomGenerator
(
const
Support::RandomGenerator
&
r
);
183
void
archive
(
Archive
& e)
const
;
184
};
185
189
template
<
class
_View>
190
class
ViewSelRnd
{
191
protected
:
193
ArchivedRandomGenerator
r
;
195
unsigned
int
n
;
196
public
:
198
typedef
_View
View
;
200
typedef
ArchivedRandomGenerator
Choice
;
202
ViewSelRnd
(
void
);
204
ViewSelRnd
(
Space
& home,
const
VarBranchOptions
& vbo);
206
ViewSelStatus
init
(
Space
& home, _View x);
208
ViewSelStatus
select
(
Space
& home, _View x);
210
Choice
choice
(
Space
& home);
212
Choice
choice
(
const
Space
& home,
Archive
& e);
214
void
commit
(
Space
& home,
const
Choice
&
c
,
unsigned
a
);
216
void
update
(
Space
& home,
bool
share,
ViewSelRnd
& vs);
218
void
dispose
(
Space
& home);
219
};
221
222
// Empty view selection choice
223
forceinline
size_t
224
EmptyViewSelChoice::size
(
void
)
const
{
225
return
sizeof
(
EmptyViewSelChoice
);
226
}
227
228
forceinline
void
229
EmptyViewSelChoice::archive
(
Archive
& e)
const
{ (void)e; }
230
231
// Selection base class
232
template
<
class
View>
233
forceinline
234
ViewSelBase<View>::ViewSelBase
(
void
) {}
235
template
<
class
View>
236
forceinline
237
ViewSelBase<View>::ViewSelBase
(
Space
&,
const
VarBranchOptions
&) {}
238
template
<
class
View>
239
forceinline
EmptyViewSelChoice
240
ViewSelBase<View>::choice
(
Space
&) {
241
EmptyViewSelChoice
c
;
return
c
;
242
}
243
template
<
class
View>
244
forceinline
EmptyViewSelChoice
245
ViewSelBase<View>::choice
(
const
Space
&,
Archive
&) {
246
EmptyViewSelChoice
c
;
return
c
;
247
}
248
template
<
class
View>
249
forceinline
void
250
ViewSelBase<View>::commit
(
Space
&,
const
EmptyViewSelChoice
&,
unsigned
int
) {}
251
template
<
class
View>
252
forceinline
void
253
ViewSelBase<View>::update
(
Space
&,
bool
,
ViewSelBase<View>
&) {}
254
template
<
class
View>
255
forceinline
void
256
ViewSelBase<View>::dispose
(
Space
&) {}
257
258
259
// Select first view
260
template
<
class
View>
261
forceinline
262
ViewSelNone<View>::ViewSelNone
(
void
) {}
263
template
<
class
View>
264
forceinline
265
ViewSelNone<View>::ViewSelNone
(
Space
& home,
const
VarBranchOptions
& vbo)
266
:
ViewSelBase
<
View
>(home,vbo) {}
267
template
<
class
View>
268
forceinline
ViewSelStatus
269
ViewSelNone<View>::init
(
Space
&,
View
) {
270
return
VSS_BEST
;
271
}
272
template
<
class
View>
273
forceinline
ViewSelStatus
274
ViewSelNone<View>::select
(
Space
&,
View
) {
275
return
VSS_BEST
;
276
}
277
278
279
// Select variable with smallest degree
280
template
<
class
View>
281
forceinline
282
ViewSelDegreeMin<View>::ViewSelDegreeMin
(
void
) : degree(0U) {}
283
template
<
class
View>
284
forceinline
285
ViewSelDegreeMin<View>::ViewSelDegreeMin
(
Space
& home,
286
const
VarBranchOptions
& vbo)
287
:
ViewSelBase
<
View
>(home,vbo), degree(0U) {}
288
template
<
class
View>
289
forceinline
ViewSelStatus
290
ViewSelDegreeMin<View>::init
(
Space
&,
View
x) {
291
degree = x.degree();
292
return
(degree == 0) ?
VSS_BEST
:
VSS_BETTER
;
293
}
294
template
<
class
View>
295
forceinline
ViewSelStatus
296
ViewSelDegreeMin<View>::select
(
Space
&,
View
x) {
297
if
(x.degree() < degree) {
298
degree = x.degree();
299
return
(degree == 0) ?
VSS_BEST
:
VSS_BETTER
;
300
}
else
if
(x.degree() > degree) {
301
return
VSS_WORSE
;
302
}
else
{
303
return
VSS_TIE
;
304
}
305
}
306
307
308
// Select variable with largest degree
309
template
<
class
View>
310
forceinline
311
ViewSelDegreeMax<View>::ViewSelDegreeMax
(
void
) : degree(0) {}
312
template
<
class
View>
313
forceinline
314
ViewSelDegreeMax<View>::ViewSelDegreeMax
(
Space
& home,
315
const
VarBranchOptions
& vbo)
316
:
ViewSelBase
<
View
>(home,vbo), degree(0U) {}
317
template
<
class
View>
318
forceinline
ViewSelStatus
319
ViewSelDegreeMax<View>::init
(
Space
&,
View
x) {
320
degree = x.degree();
321
return
VSS_BETTER
;
322
}
323
template
<
class
View>
324
forceinline
ViewSelStatus
325
ViewSelDegreeMax<View>::select
(
Space
&,
View
x) {
326
if
(x.degree() > degree) {
327
degree = x.degree();
328
return
VSS_BETTER
;
329
}
else
if
(x.degree() < degree) {
330
return
VSS_WORSE
;
331
}
else
{
332
return
VSS_TIE
;
333
}
334
}
335
336
337
// Select variable with smallest afc
338
template
<
class
View>
339
forceinline
340
ViewSelAfcMin<View>::ViewSelAfcMin
(
void
) :
afc
(0.0) {}
341
template
<
class
View>
342
forceinline
343
ViewSelAfcMin<View>::ViewSelAfcMin
(
Space
& home,
344
const
VarBranchOptions
& vbo)
345
:
ViewSelBase
<
View
>(home,vbo),
afc
(0.0) {}
346
template
<
class
View>
347
forceinline
ViewSelStatus
348
ViewSelAfcMin<View>::init
(
Space
&,
View
x) {
349
afc
= x.afc();
350
return
(
afc
== 0.0) ?
VSS_BEST
:
VSS_BETTER
;
351
}
352
template
<
class
View>
353
forceinline
ViewSelStatus
354
ViewSelAfcMin<View>::select
(
Space
&,
View
x) {
355
if
(x.afc() <
afc
) {
356
afc
= x.afc();
357
return
(
afc
== 0.0) ?
VSS_BEST
:
VSS_BETTER
;
358
}
else
if
(x.afc() >
afc
) {
359
return
VSS_WORSE
;
360
}
else
{
361
return
VSS_TIE
;
362
}
363
}
364
365
366
// Select variable with largest afc
367
template
<
class
View>
368
forceinline
369
ViewSelAfcMax<View>::ViewSelAfcMax
(
void
) :
afc
(0.0) {}
370
template
<
class
View>
371
forceinline
372
ViewSelAfcMax<View>::ViewSelAfcMax
(
Space
& home,
373
const
VarBranchOptions
& vbo)
374
:
ViewSelBase
<
View
>(home,vbo),
afc
(0.0) {}
375
template
<
class
View>
376
forceinline
ViewSelStatus
377
ViewSelAfcMax<View>::init
(
Space
&,
View
x) {
378
afc
= x.afc();
379
return
VSS_BETTER
;
380
}
381
template
<
class
View>
382
forceinline
ViewSelStatus
383
ViewSelAfcMax<View>::select
(
Space
&,
View
x) {
384
double
xafc = x.afc();
385
if
(xafc >
afc
) {
386
afc
= xafc;
387
return
VSS_BETTER
;
388
}
else
if
(xafc <
afc
) {
389
return
VSS_WORSE
;
390
}
else
{
391
return
VSS_TIE
;
392
}
393
}
394
395
396
// Archived random generator
397
forceinline
398
ArchivedRandomGenerator::ArchivedRandomGenerator
(
void
) {}
399
forceinline
400
ArchivedRandomGenerator::ArchivedRandomGenerator
(
unsigned
int
seed)
401
: Support::
RandomGenerator
(seed) {}
402
forceinline
403
ArchivedRandomGenerator::ArchivedRandomGenerator
404
(
const
Support::RandomGenerator
&
r
) :
Support::RandomGenerator
(r) {}
405
forceinline
void
406
ArchivedRandomGenerator::archive
(
Archive
& e)
const
{ e <<
seed
(); }
407
408
// Select variable by random
409
template
<
class
View>
410
forceinline
411
ViewSelRnd<View>::ViewSelRnd
(
void
) : n(0) {}
412
template
<
class
View>
413
forceinline
414
ViewSelRnd<View>::ViewSelRnd
(
Space
&,
const
VarBranchOptions
& vbo)
415
: r(vbo.seed), n(0) {}
416
template
<
class
View>
417
forceinline
ViewSelStatus
418
ViewSelRnd<View>::init
(
Space
&,
View
) {
419
n=1;
420
return
VSS_BETTER
;
421
}
422
template
<
class
View>
423
forceinline
ViewSelStatus
424
ViewSelRnd<View>::select
(
Space
&,
View
) {
425
n++;
426
return
(
r
(n) == (n-1)) ?
VSS_BETTER
:
VSS_WORSE
;
427
}
428
template
<
class
View>
429
forceinline
typename
ViewSelRnd<View>::Choice
430
ViewSelRnd<View>::choice
(
Space
&) {
431
return
r
;
432
}
433
template
<
class
View>
434
forceinline
typename
ViewSelRnd<View>::Choice
435
ViewSelRnd<View>::choice
(
const
Space
&,
Archive
& e) {
436
return
Choice
(e.
get
());
437
}
438
template
<
class
View>
439
forceinline
void
440
ViewSelRnd<View>::commit
(
Space
&,
const
Choice
&
c
,
unsigned
int
) {
441
r =
c
;
442
}
443
template
<
class
View>
444
forceinline
void
445
ViewSelRnd<View>::update
(
Space
&,
bool
,
ViewSelRnd<View>
& vs) {
446
r = vs.
r
;
447
}
448
template
<
class
View>
449
forceinline
void
450
ViewSelRnd<View>::dispose
(
Space
&) {
451
}
452
453
}
454
455
// STATISTICS: kernel-branch