git.sesse.net Git - nms/blob - tsp/tsp.cpp

   1 #include <stdio.h>
   2 #include <limits.h>
   3 #include <vector>
   4 #include <set>
   5 #include <algorithm>
   6
   7 #define MIN_ROW 1
   8 #define MAX_ROW 75
   9 #define MIN_SWITCH 1
  10 #define MAX_SWITCH 6
  11
  12 static const unsigned num_cache_elem = (MAX_ROW * MAX_SWITCH * 2) * (MAX_ROW * MAX_SWITCH * 2);
  13 static unsigned short dist_cache[(MAX_ROW * MAX_SWITCH * 2) * (MAX_ROW * MAX_SWITCH * 2)], opt_dist_cache[MAX_ROW * MAX_SWITCH * MAX_ROW * MAX_SWITCH];
  14
  15 inline unsigned short &cache(
  16         unsigned row_from, unsigned switch_from, unsigned side_from,
  17         unsigned row_to, unsigned switch_to, unsigned side_to)
  18 {
  19         return dist_cache[(row_from * MAX_SWITCH * 2 + switch_from * 2 + side_from) * (MAX_ROW * MAX_SWITCH * 2) +
  20                 row_to * MAX_SWITCH * 2 + switch_to * 2 + side_to];
  21 }
  22
  23 inline unsigned short &opt_cache(
  24         unsigned row_from, unsigned switch_from,
  25         unsigned row_to, unsigned switch_to)
  26 {
  27         return opt_dist_cache[(row_from * MAX_SWITCH + switch_from) * (MAX_ROW * MAX_SWITCH) +
  28                 row_to * MAX_SWITCH + switch_to];
  29 }
  30
  31 struct order {
  32         unsigned row, num;
  33         int side;
  34         int cost;
  35
  36         bool operator< (const order &other) const
  37         {
  38                 return (cost < other.cost);
  39         }
  40 };
  41
  42 static unsigned best_so_far = UINT_MAX;
  43 order *best_tour;
  44
  45 int distance_switch(unsigned from, unsigned to)
  46 {
  47         /* on the same side of the middle? 9.6m per switch. */
  48         if ((from > 3) == (to > 3)) {
  49                 return abs(from - to) * 96;
  50         }
  51
  52         /* have to cross the border? 25.8m from sw3->sw4 => 16.2m extra gap. */
  53         /* that's _got_ to be wrong. say it's 3m. */
  54         return abs(from - to) * 96 + 30;
  55 }
  56
  57 int distance_middle(unsigned sw, unsigned middle)
  58 {
  59         /* symmetry: 4-5-6 are just mirrored 3-2-1. */
  60         if (middle == 2) {
  61                 if (sw > 3)
  62                         sw = 7 - sw;
  63
  64                 /* estimate 25.8m/2 = 12.9m from sw3 to the middle */
  65                 return 129 + (3 - sw) * 96;
  66         }
  67
  68         /* more symmetry -- getting from 1-6 to the top is like getting from 6-1 to the bottom. */
  69         if (middle == 3) {
  70                 middle = 1;
  71                 sw = 7 - sw;
  72         }
  73
  74         /* guesstimate 4.8m extra to get to the bottom */
  75         if (sw > 3)
  76                 return 48 + 162 + (sw - 1) * 96;
  77         else
  78                 return 48 + (sw - 1) * 96;
  79 }
  80
  81 int distance_row(unsigned from, unsigned to)
  82 {
  83         /* don't calculate gaps here just yet, just estimate 4.1m per double row */
  84         return 41 * abs(from - to);
  85 }
  86
  87 int distance(int row_from, int switch_from, int side_from, int row_to, int switch_to, int side_to)
  88 {
  89         /* can we just walk directly? */
  90         if (row_from == row_to && side_from == side_to) {
  91                 return distance_switch(switch_from, switch_to);
  92         }
  93
  94         /* can we just switch sides? */
  95         if (row_from + 1 == row_to && side_from == 1 && side_to == 0) {
  96                 return distance_switch(switch_from, switch_to);
  97         }
  98         if (row_from == row_to + 1 && side_from == 0 && side_to == 1) {
  99                 return distance_switch(switch_from, switch_to);
 100         }
 101
 102         /* we'll need to go to one of the three middles */
 103         int best2 = distance_middle(switch_from, 2) + distance_middle(switch_to, 2);
 104         int distrow = distance_row(row_from, row_to);
 105         if ((switch_from > 3) != (switch_to > 3))
 106                 return best2 + distrow;
 107         if (switch_from > 3) {
 108                 int best3 = distance_middle(switch_from, 3) + distance_middle(switch_to, 3);
 109                 return std::min(best2, best3) + distrow;
 110         } else {
 111                 int best1 = distance_middle(switch_from, 1) + distance_middle(switch_to, 1);
 112                 return std::min(best2, best1) + distrow;
 113         }
 114 }
 115
 116 int optimistic_distance(int row_from, int switch_from, int row_to, int switch_to)
 117 {
 118         if (abs(row_from - row_to) == 1)
 119                 return distance_switch(switch_from, switch_to);
 120         else
 121                 return distance(row_from, switch_from, 0, row_to, switch_to, 0);
 122 }
 123
 124 // extremely primitive O(V^3) prim
 125 int prim_mst(std::set<std::pair<unsigned, unsigned> > &set1)
 126 {
 127         std::set<std::pair<unsigned, unsigned> > set2;
 128
 129         // pick the first one
 130         std::set<std::pair<unsigned, unsigned> >::iterator start = set1.begin();
 131         set2.insert(*start);
 132         set1.erase(start);
 133
 134         unsigned total_cost = 0;
 135         while (set1.size() > 0) {
 136                 unsigned best_this_cost = UINT_MAX;
 137                 std::set<std::pair<unsigned, unsigned> >::iterator best_set1;
 138
 139                 for (std::set<std::pair<unsigned, unsigned> >::iterator i = set1.begin(); i != set1.end(); ++i) {
 140                         for (std::set<std::pair<unsigned, unsigned> >::iterator j = set2.begin(); j != set2.end(); ++j) {
 141                                 unsigned d = opt_cache(i->first, i->second, j->first, j->second);
 142                                 if (d < best_this_cost) {
 143                                         best_this_cost = d;
 144                                         best_set1 = i;
 145                                 }
 146                         }
 147                 }
 148
 149                 set2.insert(*best_set1);
 150                 set1.erase(best_set1);
 151                 total_cost += best_this_cost;
 152         }
 153
 154         return total_cost;
 155 }
 156
 157
 158 void print_tour(std::vector<std::pair<unsigned, unsigned> > &points)
 159 {
 160         std::set<std::pair<unsigned, unsigned> > points_left;
 161         for (unsigned i = 0; i < points.size(); ++i) {
 162                 points_left.insert(points[i]);
 163         }
 164
 165         for (unsigned i = 0; i < points.size(); ++i) {
 166                 if (best_tour[i].side == 0)
 167                         printf("%2u-%u (left side)  ", best_tour[i].row, best_tour[i].num);
 168                 else
 169                         printf("%2u-%u (right side) ", best_tour[i].row, best_tour[i].num);
 170                 if (i == 0) {
 171                         printf("           ");
 172                 } else {
 173                         printf("cost=%4u  ", best_tour[i].cost);
 174                 }
 175
 176                 // let's see how good the MST heuristics are
 177                 if (i != points.size() - 1) {
 178                         std::set<std::pair<unsigned, unsigned> > mst_tree = points_left;
 179                         printf("mst_bound=%5u, ", prim_mst(mst_tree));
 180
 181                         unsigned rest_cost = 0;
 182                         for (unsigned j = i + 1; j < points.size(); ++j) {
 183                                 rest_cost += best_tour[j].cost;
 184                         }
 185
 186                         printf("rest_cost=%5u", rest_cost);
 187                 }
 188
 189                 printf("\n");
 190
 191                 std::set<std::pair<unsigned, unsigned> >::iterator j = points_left.find(std::make_pair(best_tour[i].row, best_tour[i].num));
 192                 points_left.erase(j);
 193         }
 194 }
 195
 196 unsigned do_tsp(std::vector<std::pair<unsigned, unsigned> > &points, std::set<std::pair<unsigned, unsigned> > &points_left, order *ord, order *temp, unsigned ind, unsigned cost_so_far)
 197 {
 198         if (cost_so_far >= best_so_far)
 199                 return UINT_MAX;
 200         if (ind == points.size()) {
 201                 memcpy(best_tour, ord, sizeof(order) * points.size());
 202                 printf("\nNew best tour found! cost=%u\n", cost_so_far);
 203                 print_tour(points);
 204                 best_so_far = cost_so_far;
 205                 return 0;
 206         }
 207
 208         /*
 209          * Simple heuristic: always search for the closest points from this one first; that
 210          * will give us a sizable cutoff.
 211          */
 212         unsigned toi = 0;
 213         unsigned last_row = ord[ind-1].row;
 214         unsigned last_switch = ord[ind-1].num;
 215         unsigned last_side = ord[ind-1].side;
 216
 217         std::set<std::pair<unsigned, unsigned> > mst_set = points_left;
 218         mst_set.insert(std::make_pair(last_row, last_switch));
 219
 220         for (std::set<std::pair<unsigned, unsigned> >::iterator i = points_left.begin(); i != points_left.end(); ++i) {
 221                 /* try both sides */
 222                 temp[toi].row = i->first;
 223                 temp[toi].num = i->second;
 224                 temp[toi].side = 0;
 225                 temp[toi].cost = cache(last_row, last_switch, last_side, i->first, i->second, 0);
 226                 ++toi;
 227
 228                 temp[toi].row = i->first;
 229                 temp[toi].num = i->second;
 230                 temp[toi].side = 1;
 231                 temp[toi].cost = cache(last_row, last_switch, last_side, i->first, i->second, 1);
 232                 ++toi;
 233         }
 234
 235         unsigned min_rest_cost = prim_mst(mst_set);
 236         if (cost_so_far + min_rest_cost >= best_so_far) {
 237                 return UINT_MAX;
 238         }
 239
 240         std::sort(temp, temp + toi);
 241
 242         unsigned best_this_cost = UINT_MAX;
 243         for (unsigned i = 0; i < toi; ++i)
 244         {
 245                 ord[ind] = temp[i];
 246
 247                 std::set<std::pair<unsigned, unsigned> >::iterator j = points_left.find(std::make_pair(temp[i].row, temp[i].num));
 248                 points_left.erase(j);
 249                 unsigned cost_rest = do_tsp(points, points_left, ord, temp + points.size() * 2, ind + 1, cost_so_far + temp[i].cost);
 250                 points_left.insert(std::make_pair(temp[i].row, temp[i].num));
 251
 252                 best_this_cost = std::min(best_this_cost, cost_rest);
 253         }
 254
 255         return best_this_cost;
 256 }
 257
 258 int main()
 259 {
 260         std::vector<std::pair<unsigned, unsigned> > points;
 261         std::set<std::pair<unsigned, unsigned> > points_left;
 262
 263         for ( ;; ) {
 264                 unsigned row, sw;
 265                 if (scanf("%u-%u", &row, &sw) != 2)
 266                         break;
 267
 268                 if (row < MIN_ROW || row > MAX_ROW || sw < MIN_SWITCH || sw > MAX_SWITCH) {
 269                         fprintf(stderr, "%u-%u is out of bounds!\n", row, sw);
 270                         exit(1);
 271                 }
 272
 273                 points.push_back(std::make_pair(row, sw));
 274                 if (points.size() != 1)
 275                         points_left.insert(std::make_pair(row, sw));
 276         }
 277
 278         // precalculate all distances
 279         for (unsigned i = 0; i < points.size(); ++i) {
 280                 for (unsigned j = 0; j < points.size(); ++j) {
 281                         cache(points[i].first, points[i].second, 0, points[j].first, points[j].second, 0) =
 282                                 distance(points[i].first, points[i].second, 0, points[j].first, points[j].second, 0);
 283
 284                         cache(points[i].first, points[i].second, 0, points[j].first, points[j].second, 1) =
 285                                 distance(points[i].first, points[i].second, 0, points[j].first, points[j].second, 1);
 286
 287                         cache(points[i].first, points[i].second, 1, points[j].first, points[j].second, 0) =
 288                                 distance(points[i].first, points[i].second, 1, points[j].first, points[j].second, 0);
 289
 290                         cache(points[i].first, points[i].second, 1, points[j].first, points[j].second, 1) =
 291                                 distance(points[i].first, points[i].second, 1, points[j].first, points[j].second, 1);
 292
 293                         opt_cache(points[i].first, points[i].second, points[j].first, points[j].second) =
 294                                 optimistic_distance(points[i].first, points[i].second, points[j].first, points[j].second);
 295                 }
 296         }
 297
 298         order *ord = new order[points.size()];
 299         best_tour = new order[points.size()];
 300         order *temp = new order[points.size() * points.size() * 4];
 301
 302         /* always start at the first one, left side (hack) */
 303         ord[0].row = points[0].first;
 304         ord[0].num = points[0].second;
 305         ord[0].side = 0;
 306
 307         do_tsp(points, points_left, ord, temp, 1, 0);
 308         printf("All done.\n");
 309 }
 310
 311