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