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