50 const int PA_d[PA_n*PA_n] = {
51 0,205,677,581,461,878,345,
52 205,0,882,427,390,1105,540,
53 677,882,0,619,316,201,470,
54 581,427,619,0,412,592,570,
55 461,390,316,412,0,517,190,
56 878,1105,201,592,517,0,691,
57 345,540,470,570,190,691,0
62 const int PB_d[PB_n*PB_n] = {
63 2,4,4,1,9,2,4,4,1,9,
64 2,9,5,5,5,2,9,5,5,5,
65 1,5,2,3,3,1,5,2,3,3,
66 2,6,8,9,5,2,6,8,9,5,
67 3,7,1,6,4,3,7,1,6,4,
68 1,2,4,1,7,1,2,4,1,7,
69 3,5,2,7,6,3,5,2,7,6,
70 2,7,9,5,5,2,7,9,5,5,
71 3,9,7,3,4,3,9,7,3,4,
77 const int PC_d[PC_n*PC_n] = {
78 0,3,5,48,48,8,8,5,5,3,3,0,3,5,8,8,5,
79 3,0,3,48,48,8,8,5,5,0,0,3,0,3,8,8,5,
80 5,3,0,72,72,48,48,24,24,3,3,5,3,0,48,48,24,
81 48,48,74,0,0,6,6,12,12,48,48,48,48,74,6,6,12,
82 48,48,74,0,0,6,6,12,12,48,48,48,48,74,6,6,12,
83 8,8,50,6,6,0,0,8,8,8,8,8,8,50,0,0,8,
84 8,8,50,6,6,0,0,8,8,8,8,8,8,50,0,0,8,
85 5,5,26,12,12,8,8,0,0,5,5,5,5,26,8,8,0,
86 5,5,26,12,12,8,8,0,0,5,5,5,5,26,8,8,0,
87 3,0,3,48,48,8,8,5,5,0,0,3,0,3,8,8,5,
88 3,0,3,48,48,8,8,5,5,0,0,3,0,3,8,8,5,
89 0,3,5,48,48,8,8,5,5,3,3,0,3,5,8,8,5,
90 3,0,3,48,48,8,8,5,5,0,0,3,0,3,8,8,5,
91 5,3,0,72,72,48,48,24,24,3,3,5,3,0,48,48,24,
92 8,8,50,6,6,0,0,8,8,8,8,8,8,50,0,0,8,
93 8,8,50,6,6,0,0,8,8,8,8,8,8,50,0,0,8,
94 5,5,26,12,12,8,8,0,0,5,5,5,5,26,8,8,0
99 const int PD_d[PD_n*PD_n] = {
100 0,26,82,65,100,147,134,69,117,42,89,125,38,13,38,31,22,103,
101 143,94,104,123,98,58,38,30,67,120,149,100,93,162,62,66,66,0,
102 56,39,109,156,140,135,183,108,155,190,104,79,104,97,88,130,176,121,
103 131,150,125,85,65,57,94,147,160,80,67,189,128,40,43,57,0,16,
104 53,100,84,107,155,85,132,168,81,56,81,74,65,146,186,137,147,166,
105 141,101,81,73,110,163,164,102,71,205,105,62,27,41,62,0,97,144,
106 131,96,144,69,116,152,65,40,65,58,49,130,170,121,131,150,125,85,
107 65,57,94,147,166,86,73,189,89,46,109,135,161,174,0,47,34,54,
108 102,67,114,175,97,96,128,135,131,198,193,203,213,232,207,167,147,139,
109 176,229,222,204,148,235,60,175,157,171,114,130,60,0,40,114,162,127,
110 174,235,157,156,188,188,179,258,253,251,239,258,203,215,195,187,172,207,
111 175,157,101,295,120,133,143,169,132,148,34,31,0,88,133,101,148,209,
112 131,130,162,169,165,232,227,237,247,266,221,201,181,173,190,225,193,175,
113 119,269,94,151,95,121,177,160,54,101,88,0,48,53,100,158,83,82,
114 114,121,117,184,179,189,199,218,193,153,133,125,162,215,244,195,188,221,
115 46,161,79,105,161,144,91,138,125,37,0,37,53,114,67,66,98,105,
116 101,137,132,149,183,202,177,137,117,109,146,199,228,179,172,174,57,145,
117 42,68,124,107,67,114,101,27,75,0,47,108,30,29,61,68,64,131,
118 126,136,146,165,140,100,80,72,109,162,191,142,135,168,20,108,83,109,
119 165,148,108,155,142,68,88,41,0,61,71,70,102,109,105,84,79,96,
120 144,163,175,141,121,113,150,203,232,183,176,121,61,149,204,230,286,269,
121 216,255,237,162,125,162,123,0,192,191,223,230,226,144,139,156,184,165,
122 215,249,242,234,251,282,332,297,297,113,182,270,38,64,120,103,88,135,
123 122,57,105,30,77,87,0,25,31,38,47,110,105,122,142,161,136,96,
124 76,68,105,158,187,138,131,147,50,104,13,39,95,78,87,134,121,56,
125 104,29,76,112,25,0,32,39,35,116,130,107,117,136,111,71,51,43,
126 80,133,162,113,106,172,49,79,38,48,104,87,119,166,153,88,136,61,
127 108,118,31,32,0,7,16,123,136,114,124,143,118,78,58,50,87,140,
128 169,120,115,178,81,88,31,41,97,80,115,162,149,84,132,57,104,114,
129 27,28,7,0,9,116,132,107,117,136,111,71,51,43,80,133,162,113,
130 108,174,77,81,22,32,88,71,122,169,156,91,139,64,111,123,36,35,
131 16,9,0,107,141,98,108,127,102,62,42,34,71,124,153,104,99,166,
132 84,72,108,134,190,173,133,180,167,93,113,66,85,60,96,95,127,134,
133 130,0,46,63,116,135,147,166,146,138,175,221,257,208,201,120,86,174,
134 127,153,209,192,152,199,186,112,132,85,104,79,115,114,146,153,149,19,
135 0,17,70,89,101,135,148,157,137,175,219,183,220,85,105,193,153,179,
136 235,218,178,225,212,138,158,111,130,105,141,140,172,179,175,45,57,0,
137 53,72,84,118,131,183,120,158,202,166,241,68,131,214,179,165,199,204,
138 243,290,277,203,223,176,195,165,206,192,199,192,183,110,112,82,0,19,
139 31,65,78,149,67,105,149,113,188,95,196,161,212,205,239,244,237,284,
140 271,197,217,170,189,146,200,199,231,232,223,104,93,63,40,0,71,105,
141 118,189,107,117,167,153,228,76,190,201,148,134,168,173,212,259,246,172,
142 192,145,164,139,175,161,168,161,152,79,125,70,36,55,0,34,47,118,
143 36,89,118,82,157,131,165,130,153,146,180,185,178,225,212,138,158,111,
144 130,105,141,140,172,173,164,45,91,36,46,65,77,0,59,130,48,101,
145 130,94,169,104,131,142,173,166,200,205,198,245,232,158,178,131,150,125,
146 161,160,192,193,184,65,111,56,66,85,97,20,0,150,68,121,150,114,
147 189,124,151,162,30,16,72,55,125,172,156,99,147,72,119,133,68,43,
148 50,43,34,73,119,64,74,93,68,28,8,0,37,90,119,70,83,132,
149 92,56,112,98,132,137,185,232,216,181,223,154,195,170,150,125,132,125,
150 116,110,156,101,67,86,31,65,78,82,0,53,82,46,121,162,174,94,
151 144,130,164,169,217,256,225,213,261,186,233,234,182,157,164,157,148,174,
152 209,165,131,116,95,129,122,114,93,0,50,78,147,192,206,126,94,80,
153 114,119,167,214,198,163,211,136,183,197,132,107,114,107,98,137,183,128,
154 110,129,74,92,72,64,43,57,0,28,103,196,156,76,66,52,101,91,
155 154,201,185,135,183,108,155,169,104,79,86,79,70,109,155,100,82,101,
156 46,64,44,36,15,68,97,0,90,168,128,63,113,108,70,86,84,131,
157 115,138,186,151,198,225,151,126,142,135,126,165,211,156,138,157,102,120,
158 100,92,71,124,93,56,0,224,144,32,146,172,228,211,171,218,205,131,
159 151,104,123,80,134,133,165,172,168,38,27,44,75,76,106,140,153,176,
160 142,180,224,188,239,0,124,212,102,128,184,167,61,108,95,7,55,60,
161 107,165,90,89,121,128,124,191,186,196,206,225,200,160,140,132,169,222,
162 251,202,195,228,0,168,81,95,38,54,91,138,122,145,193,123,170,206,
163 119,94,119,112,103,184,224,175,165,184,129,139,119,111,98,151,120,83,
174 Problem(
const int n,
const int* d);
176 int size(
void)
const;
178 int d(
int i,
int j)
const;
180 const int*
d(
void)
const;
186 Problem::Problem(
const int n,
const int* d)
189 Problem::size(
void)
const {
193 Problem::d(
int i,
int j)
const {
197 Problem::d(
void)
const {
201 Problem::max(
void)
const {
203 for (
int i=0;
i<_n*_n;
i++)
204 m = std::max(m,_d[i]);
208 Problem PA(PA_n,PA_d);
209 Problem PB(PB_n,PB_d);
210 Problem PC(PC_n,PC_d);
211 Problem PD(PD_n,PD_d);
213 Problem ps[] = {PA,PB,PC,PD};
214 const unsigned int ps_n =
sizeof(ps) /
sizeof(Problem);
240 succ(*this,
p.size(), 0,
p.size()-1),
241 total(*this, 0,
p.
max()) {
248 for (
int i=0; i<
n; i++)
249 for (
int j=0; j<
n; j++)
257 circuit(*
this, c, succ, costs, total, opt.ipl());
284 return new TSP(*
this);
289 bool assigned =
true;
290 for (
int i=0; i<succ.
size(); i++) {
291 if (!succ[i].assigned()) {
303 os << 0 << std::endl;
304 os <<
"\tCost: " << total << std::endl;
306 os <<
"\tTour: " << std::endl;
307 for (
int i=0; i<succ.
size(); i++) {
308 os <<
"\t" << i <<
" -> " << succ[i] << std::endl;
310 os <<
"\tCost: " << total << std::endl;
325 opt.
parse(argc,argv);
327 if (opt.size() >= ps_n) {
328 std::cerr <<
"Error: size must be between 0 and "
329 << ps_n-1 << std::endl;
int p
Number of positive literals for node type.
int n
Number of negative literals for node type.
Parametric base-class for scripts.
static void run(const Options &opt, Script *s=NULL)
Passing integer arguments.
Passing integer variables.
unsigned int size(void) const
Return size (cardinality) of domain.
Options for scripts with additional size parameter
int size(void) const
Return size of array (number of elements)
void update(Space &home, VarArray< Var > &a)
Update array to be a clone of array a.
void update(Space &home, VarImpVar< VarImp > &y)
Update this variable to be a clone of variable y.
Example: Travelling salesman problem (TSP)
int main(int argc, char *argv[])
Main-function.
IntVar total
Total cost of travel.
TSP(const SizeOptions &opt)
Actual model.
virtual void print(std::ostream &os) const
Print solution.
TSP(TSP &s)
Constructor for cloning s.
IntVarArray succ
Successor edges.
virtual Space * copy(void)
Copy during cloning.
virtual IntVar cost(void) const
Return solution cost.
Problem p
Problem instance to be solved.
void parse(int argc, char *argv[])
Parse commandline arguments.
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Branch over x with variable selection vars and value selection vals.
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
@ IPL_DOM
Domain propagation Options: basic versus advanced propagation.
const int min
Smallest allowed integer value.
const int max
Largest allowed integer value.
unsigned int size(I &i)
Size of all ranges of range iterator i.
Gecode toplevel namespace
void element(Home home, IntSharedArray n, IntVar x0, IntVar x1, IntPropLevel ipl=IPL_DEF)
Post domain consistent propagator for .
IntVarBranch INT_VAR_REGRET_MAX_MAX(BranchTbl tbl=nullptr)
Select variable with largest max-regret.
IntValBranch INT_VAL_MIN(void)
Select smallest value.
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
void circuit(Home home, const IntVarArgs &x, IntPropLevel ipl=IPL_DEF)
Post propagator such that x forms a circuit.
IntVarBranch INT_VAR_MIN_MIN(BranchTbl tbl=nullptr)
Select variable with smallest min.
Gecode::IntArgs i({1, 2, 3, 4})
Multi _d(Gecode::IntArgs({3, 2, 1}))