main page
modules
namespaces
classes
files
Gecode home
Generated on Fri Aug 24 2012 04:52:12 for Gecode by
doxygen
1.8.1.1
examples
golomb-ruler.cpp
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
*
6
* Copyright:
7
* Christian Schulte, 2001
8
*
9
* Last modified:
10
* $Date: 2011-08-29 20:13:11 +1000 (Mon, 29 Aug 2011) $ by $Author: schulte $
11
* $Revision: 12357 $
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
#include <
gecode/driver.hh
>
39
#include <
gecode/int.hh
>
40
#include <
gecode/minimodel.hh
>
41
42
#include <iomanip>
43
44
using namespace
Gecode;
45
66
class
GolombRuler
:
public
MinimizeScript
{
67
protected
:
69
IntVarArray
m
;
70
public
:
72
enum
{
73
SEARCH_BAB
,
74
SEARCH_RESTART
75
};
77
GolombRuler
(
const
SizeOptions
&
opt
)
78
:
m
(*this,opt.
size
(),0,
79
(opt.
size
() < 31) ? (1 << (opt.
size
()-1))-1 : Int::Limits::
max
) {
80
81
// Assume first mark to be zero
82
rel
(*
this
,
m
[0],
IRT_EQ
, 0);
83
84
// Order marks
85
rel
(*
this
,
m
,
IRT_LE
);
86
87
// Number of marks and differences
88
const
int
n =
m
.size();
89
const
int
n_d = (n*n-n)/2;
90
91
// Array of differences
92
IntVarArgs
d
(n_d);
93
94
// Setup difference constraints
95
for
(
int
k=0,
i
=0;
i
<n-1;
i
++)
96
for
(
int
j=
i
+1; j<n; j++, k++)
97
// d[k] is m[j]-m[i] and must be at least sum of first j-i integers
98
rel
(*
this
, d[k] =
expr
(*
this
,
m
[j]-
m
[
i
]),
99
IRT_GQ
, (j-i)*(j-i+1)/2);
100
101
distinct
(*
this
, d, opt.
icl
());
102
103
// Symmetry breaking
104
if
(n > 2)
105
rel
(*
this
, d[0],
IRT_LE
, d[n_d-1]);
106
107
branch
(*
this
,
m
,
INT_VAR_NONE
,
INT_VAL_MIN
);
108
}
109
111
virtual
IntVar
cost
(
void
)
const
{
112
return
m
[
m
.size()-1];
113
}
114
116
virtual
void
117
print
(std::ostream& os)
const
{
118
os <<
"\tm["
<<
m
.size() <<
"] = "
<<
m
<< std::endl;
119
}
120
122
GolombRuler
(
bool
share,
GolombRuler
& s)
123
:
MinimizeScript
(share,s) {
124
m
.update(*
this
, share, s.
m
);
125
}
127
virtual
Space
*
128
copy
(
bool
share) {
129
return
new
GolombRuler
(share,*
this
);
130
}
131
};
132
136
int
137
main
(
int
argc,
char
* argv[]) {
138
SizeOptions
opt
(
"GolombRuler"
);
139
opt.
solutions
(0);
140
opt.
size
(10);
141
opt.
icl
(
ICL_BND
);
142
opt.
search
(
GolombRuler::SEARCH_BAB
);
143
opt.
search
(
GolombRuler::SEARCH_BAB
,
"bab"
);
144
opt.
search
(
GolombRuler::SEARCH_RESTART
,
"restart"
);
145
opt.
parse
(argc,argv);
146
if
(opt.
size
() > 0)
147
switch
(opt.
search
()) {
148
case
GolombRuler::SEARCH_BAB
:
149
MinimizeScript::run<GolombRuler,BAB,SizeOptions>(
opt
);
break
;
150
case
GolombRuler::SEARCH_RESTART
:
151
MinimizeScript::run<GolombRuler,Restart,SizeOptions>(
opt
);
break
;
152
}
153
return
0;
154
}
155
156
// STATISTICS: example-any
157