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