main page
modules
namespaces
classes
files
Gecode home
Generated on Tue Oct 22 2013 00:49:07 for Gecode by
doxygen
1.8.4
gecode
search.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
* Guido Tack <tack@gecode.org>
6
*
7
* Copyright:
8
* Christian Schulte, 2002
9
* Guido Tack, 2004
10
*
11
* Last modified:
12
* $Date: 2013-07-11 12:30:18 +0200 (Thu, 11 Jul 2013) $ by $Author: schulte $
13
* $Revision: 13840 $
14
*
15
* This file is part of Gecode, the generic constraint
16
* development environment:
17
* http://www.gecode.org
18
*
19
* Permission is hereby granted, free of charge, to any person obtaining
20
* a copy of this software and associated documentation files (the
21
* "Software"), to deal in the Software without restriction, including
22
* without limitation the rights to use, copy, modify, merge, publish,
23
* distribute, sublicense, and/or sell copies of the Software, and to
24
* permit persons to whom the Software is furnished to do so, subject to
25
* the following conditions:
26
*
27
* The above copyright notice and this permission notice shall be
28
* included in all copies or substantial portions of the Software.
29
*
30
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37
*
38
*/
39
40
#ifndef __GECODE_SEARCH_HH__
41
#define __GECODE_SEARCH_HH__
42
43
#include <
gecode/kernel.hh
>
44
45
/*
46
* Configure linking
47
*
48
*/
49
#if !defined(GECODE_STATIC_LIBS) && \
50
(defined(__CYGWIN__) || defined(__MINGW32__) || defined(_MSC_VER))
51
52
#ifdef GECODE_BUILD_SEARCH
53
#define GECODE_SEARCH_EXPORT __declspec( dllexport )
54
#else
55
#define GECODE_SEARCH_EXPORT __declspec( dllimport )
56
#endif
57
58
#else
59
60
#ifdef GECODE_GCC_HAS_CLASS_VISIBILITY
61
#define GECODE_SEARCH_EXPORT __attribute__ ((visibility("default")))
62
#else
63
#define GECODE_SEARCH_EXPORT
64
#endif
65
66
#endif
67
68
// Configure auto-linking
69
#ifndef GECODE_BUILD_SEARCH
70
#define GECODE_LIBRARY_NAME "Search"
71
#include <
gecode/support/auto-link.hpp
>
72
#endif
73
74
75
namespace
Gecode {
namespace
Search {
76
78
namespace
Sequential {}
79
81
namespace
Parallel {}
82
84
namespace
Meta {}
85
91
namespace
Config {
93
const
bool
clone
=
true
;
95
const
double
threads
= 1.0;
97
const
unsigned
int
c_d
= 8;
99
const
unsigned
int
a_d
= 2;
100
102
const
unsigned
int
steal_limit
= 3;
104
const
unsigned
int
initial_delay
= 5;
105
107
const
unsigned
int
nogoods_limit
= 128;
108
}
109
110
}}
111
112
namespace
Gecode {
namespace
Search {
113
119
class
GECODE_VTABLE_EXPORT
UninitializedCutoff :
public
Exception {
121
public
:
123
UninitializedCutoff(
const
char
*
l
);
124
};
126
}}
127
128
#include <
gecode/search/exception.hpp
>
129
130
namespace
Gecode {
namespace
Search {
131
136
class
Statistics
:
public
StatusStatistics
{
137
public
:
139
unsigned
long
int
fail
;
141
unsigned
long
int
node
;
143
unsigned
long
int
depth
;
145
unsigned
long
int
restart
;
147
unsigned
long
int
nogood
;
149
Statistics
(
void
);
151
void
reset
(
void
);
153
Statistics
operator +
(
const
Statistics
& s);
155
Statistics
&
operator +=
(
const
Statistics
& s);
156
};
157
158
}}
159
160
#include <
gecode/search/statistics.hpp
>
161
162
namespace
Gecode {
namespace
Search {
163
164
class
Stop;
165
class
Cutoff;
166
204
class
Options
{
205
public
:
207
bool
clone
;
209
double
threads
;
211
unsigned
int
c_d
;
213
unsigned
int
a_d
;
215
unsigned
int
nogoods_limit
;
217
Stop
*
stop
;
219
Cutoff
*
cutoff
;
221
GECODE_SEARCH_EXPORT
static
const
Options
def
;
223
Options
(
void
);
225
GECODE_SEARCH_EXPORT
Options
226
expand
(
void
)
const
;
227
};
228
229
}}
230
231
#include <
gecode/search/options.hpp
>
232
233
namespace
Gecode {
234
235
template
<
template
<
class
>
class
E,
class
T>
236
class
RBS
;
237
238
}
239
240
namespace
Gecode {
namespace
Search {
namespace
Meta {
241
242
class
RBS
;
243
244
}}}
245
246
namespace
Gecode {
namespace
Search {
247
262
class
GECODE_SEARCH_EXPORT
Stop
{
263
public
:
265
Stop
(
void
);
267
virtual
bool
stop
(
const
Statistics
& s,
const
Options
& o) = 0;
269
virtual
~
Stop
(
void
);
271
static
void
*
operator
new
(
size_t
s);
273
static
void
operator
delete
(
void
*
p
);
274
};
275
284
class
GECODE_SEARCH_EXPORT
NodeStop
:
public
Stop
{
285
protected
:
287
unsigned
long
int
l
;
288
public
:
290
NodeStop
(
unsigned
long
int
l
);
292
unsigned
long
int
limit(
void
)
const
;
294
void
limit(
unsigned
long
int
l
);
296
virtual
bool
stop
(
const
Statistics
& s,
const
Options
& o);
297
};
298
307
class
GECODE_SEARCH_EXPORT
FailStop
:
public
Stop
{
308
protected
:
310
unsigned
long
int
l
;
311
public
:
313
FailStop
(
unsigned
long
int
l
);
315
unsigned
long
int
limit(
void
)
const
;
317
void
limit(
unsigned
long
int
l
);
319
virtual
bool
stop
(
const
Statistics
& s,
const
Options
& o);
320
};
321
326
class
GECODE_SEARCH_EXPORT
TimeStop
:
public
Stop
{
327
protected
:
329
Support::Timer
t
;
331
unsigned
long
int
l
;
332
public
:
334
TimeStop
(
unsigned
long
int
l
);
336
unsigned
long
int
limit(
void
)
const
;
338
void
limit(
unsigned
long
int
l
);
340
void
reset(
void
);
342
virtual
bool
stop
(
const
Statistics
& s,
const
Options
& o);
343
};
344
349
class
GECODE_SEARCH_EXPORT
MetaStop
:
public
Stop
{
350
template
<
template
<
class
>
class
,
class
>
friend
class ::Gecode::RBS;
351
friend
class ::Gecode::Search::Meta::RBS;
352
private
:
354
FailStop
* e_stop;
356
Stop
* m_stop;
358
bool
e_stopped;
360
Statistics
m_stat;
361
public
:
363
MetaStop
(
Stop
* s);
365
virtual
bool
stop
(
const
Statistics
& s,
const
Options
& o);
367
void
limit(
const
Search::Statistics
& s,
unsigned
long
int
l
);
369
Stop
* enginestop(
void
)
const
;
371
bool
enginestopped(
void
)
const
;
373
Statistics
metastatistics(
void
)
const
;
375
~
MetaStop
(
void
);
376
};
377
378
}}
379
380
#include <
gecode/search/stop.hpp
>
381
382
namespace
Gecode {
namespace
Search {
383
387
class
GECODE_SEARCH_EXPORT
Cutoff
{
388
public
:
390
Cutoff
(
void
);
392
virtual
unsigned
long
int
operator ()(
void
) = 0;
394
virtual
~
Cutoff
(
void
);
396
static
Cutoff
*
397
constant(
unsigned
long
int
scale=1U);
399
static
Cutoff
*
400
linear
(
unsigned
long
int
scale=1U);
404
static
Cutoff
*
405
geometric(
unsigned
long
int
scale=1U,
double
base=1.5);
407
static
Cutoff
*
408
luby(
unsigned
long
int
scale=1U);
413
static
Cutoff
*
414
rnd(
unsigned
int
seed,
415
unsigned
long
int
min
,
unsigned
long
int
max
,
416
unsigned
long
int
n
);
418
static
Cutoff
*
419
append(
Cutoff
* c1,
unsigned
long
int
n,
Cutoff
* c2);
421
static
void
*
operator
new
(
size_t
s);
423
static
void
operator
delete
(
void
*
p
);
424
};
425
426
}}
427
428
#include <
gecode/search/cutoff.hpp
>
429
430
namespace
Gecode {
namespace
Search {
431
435
class
Engine
{
436
public
:
438
virtual
Space
*
next
(
void
) = 0;
440
virtual
Statistics
statistics
(
void
)
const
= 0;
442
virtual
bool
stopped
(
void
)
const
= 0;
444
virtual
void
reset
(
Space
* s) = 0;
446
virtual
NoGoods
&
nogoods
(
void
) = 0;
448
virtual
~Engine
(
void
) {}
449
};
450
451
}}
452
453
namespace
Gecode {
454
458
class
EngineBase
{
459
template
<
template
<
class
>
class
,
class
>
friend
class ::Gecode::RBS;
460
protected
:
462
Search::Engine
*
e
;
464
~EngineBase
(
void
);
466
EngineBase
(
Search::Engine
*
e
= NULL);
467
};
468
469
}
470
471
#include <
gecode/search/engine-base.hpp
>
472
473
namespace
Gecode {
474
475
483
template
<
class
T>
484
class
DFS
:
public
EngineBase
{
485
public
:
487
DFS
(T* s,
const
Search::Options
& o=
Search::Options::def
);
489
T*
next
(
void
);
491
Search::Statistics
statistics
(
void
)
const
;
493
bool
stopped
(
void
)
const
;
495
NoGoods
&
nogoods
(
void
);
496
};
497
499
template
<
class
T>
500
T*
dfs
(T* s,
const
Search::Options
& o=
Search::Options::def
);
501
502
}
503
504
#include <
gecode/search/dfs.hpp
>
505
506
namespace
Gecode {
507
519
template
<
class
T>
520
class
BAB
:
public
EngineBase
{
521
public
:
523
BAB
(T* s,
const
Search::Options
& o=
Search::Options::def
);
525
T*
next
(
void
);
527
Search::Statistics
statistics
(
void
)
const
;
529
bool
stopped
(
void
)
const
;
531
NoGoods
&
nogoods
(
void
);
532
};
533
546
template
<
class
T>
547
T*
bab
(T* s,
const
Search::Options
& o=
Search::Options::def
);
548
549
}
550
551
#include <
gecode/search/bab.hpp
>
552
553
namespace
Gecode {
554
573
template
<
template
<
class
>
class
E,
class
T>
574
class
RBS :
public
EngineBase {
575
public
:
577
RBS
(T* s,
const
Search::Options& o);
579
T*
next
(
void
);
581
Search::Statistics
statistics
(
void
)
const
;
583
bool
stopped
(
void
)
const
;
584
};
585
604
template
<
template
<
class
>
class
E,
class
T>
605
T*
rbs
(T* s,
const
Search::Options& o);
606
607
}
608
609
#include <
gecode/search/rbs.hpp
>
610
611
#endif
612
613
// STATISTICS: search-other