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