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.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-03-08 11:11:37 +0100 (Fri, 08 Mar 2013) $ by $Author: schulte $
13
* $Revision: 13482 $
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
}
106
107
}}
108
109
namespace
Gecode {
namespace
Search {
110
116
117
class
GECODE_VTABLE_EXPORT
UninitializedCutoff
:
public
Exception
{
118
public
:
120
UninitializedCutoff
(
const
char
*
l
);
121
};
123
}}
124
125
#include <
gecode/search/exception.hpp
>
126
127
namespace
Gecode {
namespace
Search {
128
133
class
Statistics
:
public
StatusStatistics
{
134
public
:
136
unsigned
long
int
fail
;
138
unsigned
long
int
node
;
140
unsigned
long
int
depth
;
142
size_t
memory
;
144
unsigned
long
int
restart
;
146
Statistics
(
void
);
148
void
reset
(
void
);
150
Statistics
operator +
(
const
Statistics
& s);
152
Statistics
&
operator +=
(
const
Statistics
& s);
153
};
154
155
}}
156
157
#include <
gecode/search/statistics.hpp
>
158
159
namespace
Gecode {
namespace
Search {
160
161
class
Stop;
162
class
Cutoff;
163
201
class
Options
{
202
public
:
204
bool
clone
;
206
double
threads
;
208
unsigned
int
c_d
;
210
unsigned
int
a_d
;
212
Stop
*
stop
;
214
Cutoff
*
cutoff
;
216
GECODE_SEARCH_EXPORT
static
const
Options
def
;
218
Options
(
void
);
220
GECODE_SEARCH_EXPORT
Options
221
expand
(
void
)
const
;
222
};
223
224
}}
225
226
#include <
gecode/search/options.hpp
>
227
228
namespace
Gecode {
229
230
template
<
template
<
class
>
class
E,
class
T>
231
class
RBS
;
232
233
}
234
235
namespace
Gecode {
namespace
Search {
namespace
Meta {
236
237
class
RBS
;
238
239
}}}
240
241
namespace
Gecode {
namespace
Search {
242
257
class
GECODE_SEARCH_EXPORT
Stop
{
258
public
:
260
Stop
(
void
);
262
virtual
bool
stop
(
const
Statistics
& s,
const
Options
& o) = 0;
264
virtual
~
Stop
(
void
);
266
static
void
*
operator
new
(
size_t
s);
268
static
void
operator
delete
(
void
*
p
);
269
};
270
276
class
GECODE_SEARCH_EXPORT
MemoryStop
:
public
Stop
{
277
protected
:
279
size_t
l
;
280
public
:
282
MemoryStop
(
size_t
l
);
284
size_t
limit(
void
)
const
;
286
void
limit(
size_t
l
);
288
virtual
bool
stop
(
const
Statistics
& s,
const
Options
& o);
289
};
290
299
class
GECODE_SEARCH_EXPORT
NodeStop
:
public
Stop
{
300
protected
:
302
unsigned
long
int
l
;
303
public
:
305
NodeStop
(
unsigned
long
int
l
);
307
unsigned
long
int
limit(
void
)
const
;
309
void
limit(
unsigned
long
int
l
);
311
virtual
bool
stop
(
const
Statistics
& s,
const
Options
& o);
312
};
313
322
class
GECODE_SEARCH_EXPORT
FailStop
:
public
Stop
{
323
protected
:
325
unsigned
long
int
l
;
326
public
:
328
FailStop
(
unsigned
long
int
l
);
330
unsigned
long
int
limit(
void
)
const
;
332
void
limit(
unsigned
long
int
l
);
334
virtual
bool
stop
(
const
Statistics
& s,
const
Options
& o);
335
};
336
341
class
GECODE_SEARCH_EXPORT
TimeStop
:
public
Stop
{
342
protected
:
344
Support::Timer
t
;
346
unsigned
long
int
l
;
347
public
:
349
TimeStop
(
unsigned
long
int
l
);
351
unsigned
long
int
limit(
void
)
const
;
353
void
limit(
unsigned
long
int
l
);
355
void
reset(
void
);
357
virtual
bool
stop
(
const
Statistics
& s,
const
Options
& o);
358
};
359
364
class
GECODE_SEARCH_EXPORT
MetaStop
:
public
Stop
{
365
template
<
template
<
class
>
class
,
class
>
friend
class ::Gecode::RBS;
366
friend
class ::Gecode::Search::Meta::RBS;
367
private
:
369
FailStop
* e_stop;
371
Stop
* m_stop;
373
bool
e_stopped;
375
Statistics
m_stat;
376
public
:
378
MetaStop
(
Stop
* s);
380
virtual
bool
stop
(
const
Statistics
& s,
const
Options
& o);
382
void
limit(
const
Search::Statistics
& s,
unsigned
long
int
l
);
384
Stop
* enginestop(
void
)
const
;
386
bool
enginestopped(
void
)
const
;
388
Statistics
metastatistics(
void
)
const
;
390
~
MetaStop
(
void
);
391
};
392
393
}}
394
395
#include <
gecode/search/stop.hpp
>
396
397
namespace
Gecode {
namespace
Search {
398
402
class
GECODE_SEARCH_EXPORT
Cutoff
{
403
public
:
405
Cutoff
(
void
);
407
virtual
unsigned
long
int
operator ()(
void
) = 0;
409
virtual
~
Cutoff
(
void
);
411
static
Cutoff
*
412
constant(
unsigned
long
int
scale=1U);
414
static
Cutoff
*
415
linear
(
unsigned
long
int
scale=1U);
419
static
Cutoff
*
420
geometric(
unsigned
long
int
scale=1U,
double
base=1.5);
422
static
Cutoff
*
423
luby(
unsigned
long
int
scale=1U);
428
static
Cutoff
*
429
rnd(
unsigned
int
seed,
430
unsigned
long
int
min
,
unsigned
long
int
max
,
431
unsigned
long
int
n
);
433
static
Cutoff
*
434
append(
Cutoff
* c1,
unsigned
long
int
n,
Cutoff
* c2);
436
static
void
*
operator
new
(
size_t
s);
438
static
void
operator
delete
(
void
*
p
);
439
};
440
441
}}
442
443
#include <
gecode/search/cutoff.hpp
>
444
445
namespace
Gecode {
namespace
Search {
446
450
class
Engine
{
451
public
:
453
virtual
Space
*
next
(
void
) = 0;
455
virtual
Statistics
statistics
(
void
)
const
= 0;
457
virtual
bool
stopped
(
void
)
const
= 0;
459
virtual
void
reset
(
Space
* s) = 0;
461
virtual
~Engine
(
void
) {}
462
};
463
464
}}
465
466
namespace
Gecode {
467
471
class
EngineBase
{
472
template
<
template
<
class
>
class
,
class
>
friend
class ::Gecode::RBS;
473
protected
:
475
Search::Engine
*
e
;
477
~EngineBase
(
void
);
479
EngineBase
(
Search::Engine
*
e
= NULL);
480
};
481
482
}
483
484
#include <
gecode/search/engine-base.hpp
>
485
486
namespace
Gecode {
487
488
496
template
<
class
T>
497
class
DFS
:
public
EngineBase
{
498
public
:
500
DFS
(T* s,
const
Search::Options
& o=
Search::Options::def
);
502
T*
next
(
void
);
504
Search::Statistics
statistics
(
void
)
const
;
506
bool
stopped
(
void
)
const
;
507
};
508
510
template
<
class
T>
511
T*
dfs
(T* s,
const
Search::Options
& o=
Search::Options::def
);
512
513
}
514
515
#include <
gecode/search/dfs.hpp
>
516
517
namespace
Gecode {
518
530
template
<
class
T>
531
class
BAB
:
public
EngineBase
{
532
public
:
534
BAB
(T* s,
const
Search::Options
& o=
Search::Options::def
);
536
T*
next
(
void
);
538
Search::Statistics
statistics
(
void
)
const
;
540
bool
stopped
(
void
)
const
;
541
};
542
555
template
<
class
T>
556
T*
bab
(T* s,
const
Search::Options
& o=
Search::Options::def
);
557
558
}
559
560
#include <
gecode/search/bab.hpp
>
561
562
namespace
Gecode {
563
582
template
<
template
<
class
>
class
E,
class
T>
583
class
RBS :
public
EngineBase {
584
public
:
586
RBS
(T* s,
const
Search::Options& o);
588
T*
next
(
void
);
590
Search::Statistics
statistics
(
void
)
const
;
592
bool
stopped
(
void
)
const
;
593
};
594
613
template
<
template
<
class
>
class
E,
class
T>
614
T*
rbs
(T* s,
const
Search::Options& o);
615
616
}
617
618
#include <
gecode/search/rbs.hpp
>
619
620
#endif
621
622
// STATISTICS: search-other