00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037 #include <gecode/driver.hh>
00038 #include <gecode/int.hh>
00039 #include <gecode/minimodel.hh>
00040
00041 #include <algorithm>
00042
00043 using namespace Gecode;
00044
00046 namespace {
00047
00049 const int PA_n = 7;
00050 const int PA_d[PA_n*PA_n] = {
00051 0,205,677,581,461,878,345,
00052 205,0,882,427,390,1105,540,
00053 677,882,0,619,316,201,470,
00054 581,427,619,0,412,592,570,
00055 461,390,316,412,0,517,190,
00056 878,1105,201,592,517,0,691,
00057 345,540,470,570,190,691,0
00058 };
00059
00061 const int PB_n = 10;
00062 const int PB_d[PB_n*PB_n] = {
00063 2,4,4,1,9,2,4,4,1,9,
00064 2,9,5,5,5,2,9,5,5,5,
00065 1,5,2,3,3,1,5,2,3,3,
00066 2,6,8,9,5,2,6,8,9,5,
00067 3,7,1,6,4,3,7,1,6,4,
00068 1,2,4,1,7,1,2,4,1,7,
00069 3,5,2,7,6,3,5,2,7,6,
00070 2,7,9,5,5,2,7,9,5,5,
00071 3,9,7,3,4,3,9,7,3,4,
00072 4,1,5,9,2,4,1,5,9,2
00073 };
00074
00076 const int PC_n = 17;
00077 const int PC_d[PC_n*PC_n] = {
00078 0,3,5,48,48,8,8,5,5,3,3,0,3,5,8,8,5,
00079 3,0,3,48,48,8,8,5,5,0,0,3,0,3,8,8,5,
00080 5,3,0,72,72,48,48,24,24,3,3,5,3,0,48,48,24,
00081 48,48,74,0,0,6,6,12,12,48,48,48,48,74,6,6,12,
00082 48,48,74,0,0,6,6,12,12,48,48,48,48,74,6,6,12,
00083 8,8,50,6,6,0,0,8,8,8,8,8,8,50,0,0,8,
00084 8,8,50,6,6,0,0,8,8,8,8,8,8,50,0,0,8,
00085 5,5,26,12,12,8,8,0,0,5,5,5,5,26,8,8,0,
00086 5,5,26,12,12,8,8,0,0,5,5,5,5,26,8,8,0,
00087 3,0,3,48,48,8,8,5,5,0,0,3,0,3,8,8,5,
00088 3,0,3,48,48,8,8,5,5,0,0,3,0,3,8,8,5,
00089 0,3,5,48,48,8,8,5,5,3,3,0,3,5,8,8,5,
00090 3,0,3,48,48,8,8,5,5,0,0,3,0,3,8,8,5,
00091 5,3,0,72,72,48,48,24,24,3,3,5,3,0,48,48,24,
00092 8,8,50,6,6,0,0,8,8,8,8,8,8,50,0,0,8,
00093 8,8,50,6,6,0,0,8,8,8,8,8,8,50,0,0,8,
00094 5,5,26,12,12,8,8,0,0,5,5,5,5,26,8,8,0
00095 };
00096
00098 const int PD_n = 34;
00099 const int PD_d[PD_n*PD_n] = {
00100 0,26,82,65,100,147,134,69,117,42,89,125,38,13,38,31,22,103,
00101 143,94,104,123,98,58,38,30,67,120,149,100,93,162,62,66,66,0,
00102 56,39,109,156,140,135,183,108,155,190,104,79,104,97,88,130,176,121,
00103 131,150,125,85,65,57,94,147,160,80,67,189,128,40,43,57,0,16,
00104 53,100,84,107,155,85,132,168,81,56,81,74,65,146,186,137,147,166,
00105 141,101,81,73,110,163,164,102,71,205,105,62,27,41,62,0,97,144,
00106 131,96,144,69,116,152,65,40,65,58,49,130,170,121,131,150,125,85,
00107 65,57,94,147,166,86,73,189,89,46,109,135,161,174,0,47,34,54,
00108 102,67,114,175,97,96,128,135,131,198,193,203,213,232,207,167,147,139,
00109 176,229,222,204,148,235,60,175,157,171,114,130,60,0,40,114,162,127,
00110 174,235,157,156,188,188,179,258,253,251,239,258,203,215,195,187,172,207,
00111 175,157,101,295,120,133,143,169,132,148,34,31,0,88,133,101,148,209,
00112 131,130,162,169,165,232,227,237,247,266,221,201,181,173,190,225,193,175,
00113 119,269,94,151,95,121,177,160,54,101,88,0,48,53,100,158,83,82,
00114 114,121,117,184,179,189,199,218,193,153,133,125,162,215,244,195,188,221,
00115 46,161,79,105,161,144,91,138,125,37,0,37,53,114,67,66,98,105,
00116 101,137,132,149,183,202,177,137,117,109,146,199,228,179,172,174,57,145,
00117 42,68,124,107,67,114,101,27,75,0,47,108,30,29,61,68,64,131,
00118 126,136,146,165,140,100,80,72,109,162,191,142,135,168,20,108,83,109,
00119 165,148,108,155,142,68,88,41,0,61,71,70,102,109,105,84,79,96,
00120 144,163,175,141,121,113,150,203,232,183,176,121,61,149,204,230,286,269,
00121 216,255,237,162,125,162,123,0,192,191,223,230,226,144,139,156,184,165,
00122 215,249,242,234,251,282,332,297,297,113,182,270,38,64,120,103,88,135,
00123 122,57,105,30,77,87,0,25,31,38,47,110,105,122,142,161,136,96,
00124 76,68,105,158,187,138,131,147,50,104,13,39,95,78,87,134,121,56,
00125 104,29,76,112,25,0,32,39,35,116,130,107,117,136,111,71,51,43,
00126 80,133,162,113,106,172,49,79,38,48,104,87,119,166,153,88,136,61,
00127 108,118,31,32,0,7,16,123,136,114,124,143,118,78,58,50,87,140,
00128 169,120,115,178,81,88,31,41,97,80,115,162,149,84,132,57,104,114,
00129 27,28,7,0,9,116,132,107,117,136,111,71,51,43,80,133,162,113,
00130 108,174,77,81,22,32,88,71,122,169,156,91,139,64,111,123,36,35,
00131 16,9,0,107,141,98,108,127,102,62,42,34,71,124,153,104,99,166,
00132 84,72,108,134,190,173,133,180,167,93,113,66,85,60,96,95,127,134,
00133 130,0,46,63,116,135,147,166,146,138,175,221,257,208,201,120,86,174,
00134 127,153,209,192,152,199,186,112,132,85,104,79,115,114,146,153,149,19,
00135 0,17,70,89,101,135,148,157,137,175,219,183,220,85,105,193,153,179,
00136 235,218,178,225,212,138,158,111,130,105,141,140,172,179,175,45,57,0,
00137 53,72,84,118,131,183,120,158,202,166,241,68,131,214,179,165,199,204,
00138 243,290,277,203,223,176,195,165,206,192,199,192,183,110,112,82,0,19,
00139 31,65,78,149,67,105,149,113,188,95,196,161,212,205,239,244,237,284,
00140 271,197,217,170,189,146,200,199,231,232,223,104,93,63,40,0,71,105,
00141 118,189,107,117,167,153,228,76,190,201,148,134,168,173,212,259,246,172,
00142 192,145,164,139,175,161,168,161,152,79,125,70,36,55,0,34,47,118,
00143 36,89,118,82,157,131,165,130,153,146,180,185,178,225,212,138,158,111,
00144 130,105,141,140,172,173,164,45,91,36,46,65,77,0,59,130,48,101,
00145 130,94,169,104,131,142,173,166,200,205,198,245,232,158,178,131,150,125,
00146 161,160,192,193,184,65,111,56,66,85,97,20,0,150,68,121,150,114,
00147 189,124,151,162,30,16,72,55,125,172,156,99,147,72,119,133,68,43,
00148 50,43,34,73,119,64,74,93,68,28,8,0,37,90,119,70,83,132,
00149 92,56,112,98,132,137,185,232,216,181,223,154,195,170,150,125,132,125,
00150 116,110,156,101,67,86,31,65,78,82,0,53,82,46,121,162,174,94,
00151 144,130,164,169,217,256,225,213,261,186,233,234,182,157,164,157,148,174,
00152 209,165,131,116,95,129,122,114,93,0,50,78,147,192,206,126,94,80,
00153 114,119,167,214,198,163,211,136,183,197,132,107,114,107,98,137,183,128,
00154 110,129,74,92,72,64,43,57,0,28,103,196,156,76,66,52,101,91,
00155 154,201,185,135,183,108,155,169,104,79,86,79,70,109,155,100,82,101,
00156 46,64,44,36,15,68,97,0,90,168,128,63,113,108,70,86,84,131,
00157 115,138,186,151,198,225,151,126,142,135,126,165,211,156,138,157,102,120,
00158 100,92,71,124,93,56,0,224,144,32,146,172,228,211,171,218,205,131,
00159 151,104,123,80,134,133,165,172,168,38,27,44,75,76,106,140,153,176,
00160 142,180,224,188,239,0,124,212,102,128,184,167,61,108,95,7,55,60,
00161 107,165,90,89,121,128,124,191,186,196,206,225,200,160,140,132,169,222,
00162 251,202,195,228,0,168,81,95,38,54,91,138,122,145,193,123,170,206,
00163 119,94,119,112,103,184,224,175,165,184,129,139,119,111,98,151,120,83,
00164 27,243,143,0
00165 };
00166
00168 class Problem {
00169 private:
00170 const int _n;
00171 const int* _d;
00172 public:
00174 Problem(const int n, const int* d);
00176 int size(void) const;
00178 int d(int i, int j) const;
00180 const int* d(void) const;
00182 int max(void) const;
00183 };
00184
00185 inline
00186 Problem::Problem(const int n, const int* d)
00187 : _n(n), _d(d) {}
00188 inline int
00189 Problem::size(void) const {
00190 return _n;
00191 }
00192 inline int
00193 Problem::d(int i, int j) const {
00194 return _d[i*_n+j];
00195 }
00196 inline const int*
00197 Problem::d(void) const {
00198 return _d;
00199 }
00200 inline int
00201 Problem::max(void) const {
00202 int m=0;
00203 for (int i=0; i<_n*_n; i++)
00204 m = std::max(m,_d[i]);
00205 return m*_n;
00206 }
00207
00208 Problem PA(PA_n,PA_d);
00209 Problem PB(PB_n,PB_d);
00210 Problem PC(PC_n,PC_d);
00211 Problem PD(PD_n,PD_d);
00212
00213 Problem ps[] = {PA,PB,PC,PD};
00214 const unsigned int ps_n = sizeof(ps) / sizeof(Problem);
00215
00216 }
00217
00227 class TSP : public IntMinimizeScript {
00228 protected:
00230 Problem p;
00232 IntVarArray succ;
00234 IntVar total;
00235 public:
00237 TSP(const SizeOptions& opt)
00238 : IntMinimizeScript(opt),
00239 p(ps[opt.size()]),
00240 succ(*this, p.size(), 0, p.size()-1),
00241 total(*this, 0, p.max()) {
00242 int n = p.size();
00243
00244
00245 IntArgs c(n*n, p.d());
00246
00247
00248 for (int i=0; i<n; i++)
00249 for (int j=0; j<n; j++)
00250 if (p.d(i,j) == 0)
00251 rel(*this, succ[i], IRT_NQ, j);
00252
00253
00254 IntVarArgs costs(*this, n, Int::Limits::min, Int::Limits::max);
00255
00256
00257 circuit(*this, c, succ, costs, total, opt.ipl());
00258
00259
00260 {
00261 IntVar p0(*this, 0, n-1);
00262 element(*this, succ, p0, 0);
00263 rel(*this, p0, IRT_LE, succ[0]);
00264 }
00265
00266
00267 branch(*this, costs, INT_VAR_REGRET_MAX_MAX(), INT_VAL_MIN());
00268
00269
00270 branch(*this, succ, INT_VAR_MIN_MIN(), INT_VAL_MIN());
00271 }
00273 virtual IntVar cost(void) const {
00274 return total;
00275 }
00277 TSP(TSP& s) : IntMinimizeScript(s), p(s.p) {
00278 succ.update(*this, s.succ);
00279 total.update(*this, s.total);
00280 }
00282 virtual Space*
00283 copy(void) {
00284 return new TSP(*this);
00285 }
00287 virtual void
00288 print(std::ostream& os) const {
00289 bool assigned = true;
00290 for (int i=0; i<succ.size(); i++) {
00291 if (!succ[i].assigned()) {
00292 assigned = false;
00293 break;
00294 }
00295 }
00296 if (assigned) {
00297 os << "\tTour: ";
00298 int i=0;
00299 do {
00300 os << i << " -> ";
00301 i=succ[i].val();
00302 } while (i != 0);
00303 os << 0 << std::endl;
00304 os << "\tCost: " << total << std::endl;
00305 } else {
00306 os << "\tTour: " << std::endl;
00307 for (int i=0; i<succ.size(); i++) {
00308 os << "\t" << i << " -> " << succ[i] << std::endl;
00309 }
00310 os << "\tCost: " << total << std::endl;
00311 }
00312 }
00313 };
00314
00315
00316
00320 int
00321 main(int argc, char* argv[]) {
00322 SizeOptions opt("TSP");
00323 opt.solutions(0);
00324 opt.ipl(IPL_DOM);
00325 opt.parse(argc,argv);
00326
00327 if (opt.size() >= ps_n) {
00328 std::cerr << "Error: size must be between 0 and "
00329 << ps_n-1 << std::endl;
00330 return 1;
00331 }
00332
00333 IntMinimizeScript::run<TSP,BAB,SizeOptions>(opt);
00334 return 0;
00335 }
00336
00337