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