main page
modules
namespaces
classes
files
Gecode home
Generated on Sat Nov 9 2013 19:18:30 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-10-30 15:42:34 +0100 (Wed, 30 Oct 2013) $ by $Author: schulte $
13
* $Revision: 14037 $
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
void
update(
const
Search::Statistics
& s);
371
Stop
* enginestop(
void
)
const
;
373
bool
enginestopped(
void
)
const
;
375
Statistics
metastatistics(
void
)
const
;
377
~
MetaStop
(
void
);
378
};
379
380
}}
381
382
#include <
gecode/search/stop.hpp
>
383
384
namespace
Gecode {
namespace
Search {
385
389
class
GECODE_SEARCH_EXPORT
Cutoff
{
390
public
:
392
Cutoff
(
void
);
394
virtual
unsigned
long
int
operator ()(
void
) = 0;
396
virtual
~
Cutoff
(
void
);
398
static
Cutoff
*
399
constant(
unsigned
long
int
scale=1U);
401
static
Cutoff
*
402
linear
(
unsigned
long
int
scale=1U);
406
static
Cutoff
*
407
geometric(
unsigned
long
int
scale=1U,
double
base=1.5);
409
static
Cutoff
*
410
luby(
unsigned
long
int
scale=1U);
415
static
Cutoff
*
416
rnd(
unsigned
int
seed,
417
unsigned
long
int
min
,
unsigned
long
int
max
,
418
unsigned
long
int
n
);
420
static
Cutoff
*
421
append(
Cutoff
* c1,
unsigned
long
int
n,
Cutoff
* c2);
423
static
Cutoff
*
424
repeat(
Cutoff
*
c
,
unsigned
long
int
n);
426
static
void
*
operator
new
(
size_t
s);
428
static
void
operator
delete
(
void
*
p
);
429
};
430
431
}}
432
433
#include <
gecode/search/cutoff.hpp
>
434
435
namespace
Gecode {
namespace
Search {
436
440
class
Engine
{
441
public
:
443
virtual
Space
*
next
(
void
) = 0;
445
virtual
Statistics
statistics
(
void
)
const
= 0;
447
virtual
bool
stopped
(
void
)
const
= 0;
449
virtual
void
reset
(
Space
* s) = 0;
451
virtual
NoGoods
&
nogoods
(
void
) = 0;
453
virtual
~Engine
(
void
) {}
454
};
455
456
}}
457
458
namespace
Gecode {
459
463
class
EngineBase
{
464
template
<
template
<
class
>
class
,
class
>
friend
class ::Gecode::RBS;
465
protected
:
467
Search::Engine
*
e
;
469
~EngineBase
(
void
);
471
EngineBase
(
Search::Engine
*
e
= NULL);
472
};
473
474
}
475
476
#include <
gecode/search/engine-base.hpp
>
477
478
namespace
Gecode {
479
480
488
template
<
class
T>
489
class
DFS
:
public
EngineBase
{
490
public
:
492
DFS
(T* s,
const
Search::Options
& o=
Search::Options::def
);
494
T*
next
(
void
);
496
Search::Statistics
statistics
(
void
)
const
;
498
bool
stopped
(
void
)
const
;
500
NoGoods
&
nogoods
(
void
);
501
};
502
504
template
<
class
T>
505
T*
dfs
(T* s,
const
Search::Options
& o=
Search::Options::def
);
506
507
}
508
509
#include <
gecode/search/dfs.hpp
>
510
511
namespace
Gecode {
512
524
template
<
class
T>
525
class
BAB
:
public
EngineBase
{
526
public
:
528
BAB
(T* s,
const
Search::Options
& o=
Search::Options::def
);
530
T*
next
(
void
);
532
Search::Statistics
statistics
(
void
)
const
;
534
bool
stopped
(
void
)
const
;
536
NoGoods
&
nogoods
(
void
);
537
};
538
551
template
<
class
T>
552
T*
bab
(T* s,
const
Search::Options
& o=
Search::Options::def
);
553
554
}
555
556
#include <
gecode/search/bab.hpp
>
557
558
namespace
Gecode {
559
578
template
<
template
<
class
>
class
E,
class
T>
579
class
RBS :
public
EngineBase {
580
public
:
582
RBS
(T* s,
const
Search::Options& o);
584
T*
next
(
void
);
586
Search::Statistics
statistics
(
void
)
const
;
588
bool
stopped
(
void
)
const
;
589
};
590
609
template
<
template
<
class
>
class
E,
class
T>
610
T*
rbs
(T* s,
const
Search::Options& o);
611
612
}
613
614
#include <
gecode/search/rbs.hpp
>
615
616
#endif
617
618
// STATISTICS: search-other