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