main page
modules
namespaces
classes
files
Gecode home
Generated on Thu Feb 14 2013 20:59:45 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: 2010-10-09 22:58:12 +1100 (Sat, 09 Oct 2010) $ by $Author: schulte $
13
* $Revision: 11498 $
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 {
76
78
namespace
Search {
79
85
namespace
Config {
87
const
bool
clone
=
true
;
89
const
double
threads
= 1.0;
91
const
unsigned
int
c_d
= 8;
93
const
unsigned
int
a_d
= 2;
94
96
const
unsigned
int
steal_limit
= 3;
98
const
unsigned
int
initial_delay
= 5;
99
}
100
105
class
Statistics
:
public
StatusStatistics
{
106
public
:
108
unsigned
long
int
fail
;
110
unsigned
long
int
node
;
112
unsigned
long
int
depth
;
114
size_t
memory
;
116
Statistics
(
void
);
118
void
reset
(
void
);
120
Statistics
operator +
(
const
Statistics
& s);
122
Statistics
&
operator +=
(
const
Statistics
& s);
123
};
124
125
class
Stop
;
126
164
class
Options
{
165
public
:
167
bool
clone
;
169
double
threads
;
171
unsigned
int
c_d
;
173
unsigned
int
a_d
;
175
Stop
*
stop
;
177
GECODE_SEARCH_EXPORT
static
const
Options
def
;
179
Options
(
void
);
181
GECODE_SEARCH_EXPORT
Options
182
expand
(
void
)
const
;
183
};
184
199
class
GECODE_SEARCH_EXPORT
Stop
{
200
public
:
202
Stop
(
void
);
204
virtual
bool
stop
(
const
Statistics
& s,
const
Options
& o) = 0;
206
virtual
~
Stop
(
void
);
207
};
208
214
class
GECODE_SEARCH_EXPORT
MemoryStop
:
public
Stop
{
215
protected
:
217
size_t
l
;
218
public
:
220
MemoryStop
(
size_t
l);
222
size_t
limit(
void
)
const
;
224
void
limit(
size_t
l);
226
virtual
bool
stop
(
const
Statistics
& s,
const
Options
& o);
227
};
228
237
class
GECODE_SEARCH_EXPORT
NodeStop
:
public
Stop
{
238
protected
:
240
unsigned
long
int
l
;
241
public
:
243
NodeStop
(
unsigned
long
int
l);
245
unsigned
long
int
limit(
void
)
const
;
247
void
limit(
unsigned
long
int
l);
249
virtual
bool
stop
(
const
Statistics
& s,
const
Options
& o);
250
};
251
260
class
GECODE_SEARCH_EXPORT
FailStop
:
public
Stop
{
261
protected
:
263
unsigned
long
int
l
;
264
public
:
266
FailStop
(
unsigned
long
int
l);
268
unsigned
long
int
limit(
void
)
const
;
270
void
limit(
unsigned
long
int
l);
272
virtual
bool
stop
(
const
Statistics
& s,
const
Options
& o);
273
};
274
279
class
GECODE_SEARCH_EXPORT
TimeStop
:
public
Stop
{
280
protected
:
282
Support::Timer
t
;
284
unsigned
long
int
l
;
285
public
:
287
TimeStop
(
unsigned
long
int
l);
289
unsigned
long
int
limit(
void
)
const
;
291
void
limit(
unsigned
long
int
l);
293
void
reset(
void
);
295
virtual
bool
stop
(
const
Statistics
& s,
const
Options
& o);
296
};
297
298
302
class
Engine
{
303
public
:
305
virtual
Space
*
next
(
void
) = 0;
307
virtual
Search::Statistics
statistics
(
void
)
const
= 0;
309
virtual
bool
stopped
(
void
)
const
= 0;
311
virtual
~Engine
(
void
) {}
312
};
313
315
namespace
Sequential {}
316
318
namespace
Parallel {}
319
320
}
321
322
}
323
324
#include <
gecode/search/statistics.hpp
>
325
#include <
gecode/search/stop.hpp
>
326
#include <
gecode/search/options.hpp
>
327
328
namespace
Gecode {
329
337
template
<
class
T>
338
class
DFS
{
339
private
:
341
Search::Engine
* e;
342
public
:
344
DFS
(T* s,
const
Search::Options
& o=
Search::Options::def
);
346
T*
next
(
void
);
348
Search::Statistics
statistics
(
void
)
const
;
350
bool
stopped
(
void
)
const
;
352
~DFS
(
void
);
353
};
354
356
template
<
class
T>
357
T*
dfs
(T* s,
const
Search::Options
& o=
Search::Options::def
);
358
359
360
372
template
<
class
T>
373
class
BAB
{
374
private
:
376
Search::Engine
* e;
377
public
:
379
BAB
(T* s,
const
Search::Options
& o=
Search::Options::def
);
381
T*
next
(
void
);
383
Search::Statistics
statistics
(
void
)
const
;
385
bool
stopped
(
void
)
const
;
387
~BAB
(
void
);
388
};
389
402
template
<
class
T>
403
T*
bab
(T* s,
const
Search::Options
& o=
Search::Options::def
);
404
405
406
418
template
<
class
T>
419
class
Restart
{
420
private
:
422
Search::Engine
* e;
423
public
:
425
Restart
(T* s,
const
Search::Options
& o=
Search::Options::def
);
427
T*
next
(
void
);
429
Search::Statistics
statistics
(
void
)
const
;
431
bool
stopped
(
void
)
const
;
433
~Restart
(
void
);
434
};
435
447
template
<
class
T>
448
T*
restart
(T* s,
const
Search::Options
& o=
Search::Options::def
);
449
450
}
451
452
#include <
gecode/search/dfs.hpp
>
453
#include <
gecode/search/bab.hpp
>
454
#include <
gecode/search/restart.hpp
>
455
456
#endif
457
458
// STATISTICS: search-other