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(*this, n, Int::Limits::min, Int::Limits::max);
00258
00259
00260 circuit(*this, c, succ, costs, total, opt.icl());
00261
00262
00263 {
00264 IntVar p0(*this, 0, n-1);
00265 element(*this, succ, p0, 0);
00266 rel(*this, p0, IRT_LE, succ[0]);
00267 }
00268
00269
00270 branch(*this, costs, INT_VAR_REGRET_MAX_MAX, INT_VAL_SPLIT_MIN);
00271
00272
00273 branch(*this, succ, INT_VAR_MIN_MIN, INT_VAL_MIN);
00274 }
00276 virtual IntVar cost(void) const {
00277 return total;
00278 }
00280 TSP(bool share, TSP& s) : MinimizeScript(share,s), p(s.p) {
00281 succ.update(*this, share, s.succ);
00282 total.update(*this, share, s.total);
00283 }
00285 virtual Space*
00286 copy(bool share) {
00287 return new TSP(share,*this);
00288 }
00290 virtual void
00291 print(std::ostream& os) const {
00292 bool assigned = true;
00293 for (int i=0; i<succ.size(); i++) {
00294 if (!succ[i].assigned()) {
00295 assigned = false;
00296 break;
00297 }
00298 }
00299 if (assigned) {
00300 os << "\tTour: ";
00301 int i=0;
00302 do {
00303 os << i << " -> ";
00304 i=succ[i].val();
00305 } while (i != 0);
00306 os << 0 << std::endl;
00307 os << "\tCost: " << total << std::endl;
00308 } else {
00309 os << "\tTour: " << std::endl;
00310 for (int i=0; i<succ.size(); i++) {
00311 os << "\t" << i << " -> " << succ[i] << std::endl;
00312 }
00313 os << "\tCost: " << total << std::endl;
00314 }
00315 }
00316 };
00317
00318
00319
00323 int
00324 main(int argc, char* argv[]) {
00325 SizeOptions opt("TSP");
00326 opt.solutions(0);
00327 opt.icl(ICL_DOM);
00328 opt.parse(argc,argv);
00329
00330 if (opt.size() >= ps_n) {
00331 std::cerr << "Error: size must be between 0 and "
00332 << ps_n-1 << std::endl;
00333 return 1;
00334 }
00335
00336 MinimizeScript::run<TSP,BAB,SizeOptions>(opt);
00337 return 0;
00338 }
00339
00340