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

   1 #include <stdio.h>
   2 #include <limits.h>
   3 #include <vector>
   4 #include <algorithm>
   5
   6 int distance_switch(unsigned from, unsigned to)
   7 {
   8         /* on the same side of the middle? 9.6m per switch. */
   9         if ((from > 3) == (to > 3)) {
  10                 return abs(from - to) * 96;
  11         }
  12
  13         /* have to cross the border? 25.8m from sw3->sw4 => 16.2m extra gap. */
  14         /* that's _got_ to be wrong. say it's 3m. */
  15         return abs(from - to) * 96 + 30;
  16 }
  17
  18 int distance_middle(unsigned sw, unsigned middle)
  19 {
  20         /* symmetry: 4-5-6 are just mirrored 3-2-1. */
  21         if (middle == 2) {
  22                 if (sw > 3)
  23                         sw = 7 - sw;
  24
  25                 /* estimate 25.8m/2 = 12.9m from sw3 to the middle */
  26                 return 129 + (3 - sw) * 96;
  27         }
  28
  29         /* more symmetry -- getting from 1-6 to the top is like getting from 6-1 to the bottom. */
  30         if (middle == 3) {
  31                 middle = 1;
  32                 sw = 7 - sw;
  33         }
  34
  35         /* guesstimate 4.8m extra to get to the bottom */
  36         if (sw > 3)
  37                 return 48 + 162 + (sw - 1) * 96;
  38         else
  39                 return 48 + (sw - 1) * 96;
  40 }
  41
  42 int distance_row(unsigned from, unsigned to)
  43 {
  44         /* don't calculate gaps here just yet, just estimate 4.1m per double row */
  45         return 41 * abs(from - to);
  46 }
  47
  48 int distance(int row_from, int switch_from, int side_from, int row_to, int switch_to, int side_to)
  49 {
  50         /* can we just walk directly? */
  51         if (row_from == row_to && side_from == side_to) {
  52                 return distance_switch(switch_from, switch_to);
  53         }
  54
  55         /* can we just switch sides? */
  56         if (row_from + 1 == row_to && side_from == 1 && side_to == -1) {
  57                 return distance_switch(switch_from, switch_to);
  58         }
  59         if (row_from == row_to + 1 && side_from == -1 && side_to == 1) {
  60                 return distance_switch(switch_from, switch_to);
  61         }
  62
  63         /* we'll need to go to one of the three middles */
  64         int best1 = distance_middle(switch_from, 1) + distance_middle(switch_to, 1);
  65         int best2 = distance_middle(switch_from, 2) + distance_middle(switch_to, 2);
  66         int best3 = distance_middle(switch_from, 3) + distance_middle(switch_to, 3);
  67         return std::min(std::min(best1, best2), best3) + distance_row(row_from, row_to);
  68 }
  69
  70 struct order {
  71         unsigned pt;
  72         int side;
  73 };
  74 struct try_order {
  75         order o;
  76         int cost;
  77
  78         bool operator< (const try_order &other) const
  79         {
  80                 return (cost < other.cost);
  81         }
  82 };
  83
  84 static unsigned best_so_far = UINT_MAX;
  85 order *best_tour;
  86
  87 void print_tour(std::vector<std::pair<unsigned, unsigned> > &points)
  88 {
  89         for (unsigned i = 0; i < points.size(); ++i) {
  90                 if (best_tour[i].side == -1)
  91                         printf("%2u-%u (left side)  ", points[best_tour[i].pt].first,
  92                                 points[best_tour[i].pt].second);
  93                 else
  94                         printf("%2u-%u (right side) ", points[best_tour[i].pt].first,
  95                                 points[best_tour[i].pt].second);
  96                 if (i == 0) {
  97                         printf("\n");
  98                 } else {
  99                         unsigned cost = distance(
 100                                 points[best_tour[i-1].pt].first,
 101                                 points[best_tour[i-1].pt].second,
 102                                 best_tour[i-1].side,
 103                                 points[best_tour[i].pt].first,
 104                                 points[best_tour[i].pt].second,
 105                                 best_tour[i].side);
 106                         printf("cost=%4u\n", cost);
 107                 }
 108         }
 109 }
 110
 111 unsigned do_tsp(std::vector<std::pair<unsigned, unsigned> > &points, order *ord, try_order *temp, unsigned ind, unsigned cost_so_far)
 112 {
 113         if (cost_so_far >= best_so_far)
 114                 return UINT_MAX;
 115         if (ind == points.size()) {
 116                 memcpy(best_tour, ord, sizeof(order) * points.size());
 117                 printf("\nNew best tour found! cost=%u\n", cost_so_far);
 118                 print_tour(points);
 119                 best_so_far = cost_so_far;
 120                 return 0;
 121         }
 122
 123         /*
 124          * Simple heuristic: always search for the closest points from this one first; that
 125          * will give us a sizable cutoff.
 126          */
 127         unsigned toi = 0;
 128         unsigned last_row = points[ord[ind-1].pt].first;
 129         unsigned last_switch = points[ord[ind-1].pt].second;
 130         unsigned last_side = ord[ind-1].side;
 131
 132         for (unsigned i = 0; i < points.size(); ++i) {
 133                 /* taken earlier? */
 134                 for (unsigned j = 0; j < ind; ++j) {
 135                         if (ord[j].pt == i)
 136                                 goto taken;
 137                 }
 138
 139                 /* try both sides */
 140                 temp[toi].o.pt = i;
 141                 temp[toi].o.side = -1;
 142                 temp[toi].cost = distance(last_row, last_switch, last_side,
 143                         points[i].first, points[i].second, -1);
 144                 ++toi;
 145
 146                 temp[toi].o.pt = i;
 147                 temp[toi].o.side = +1;
 148                 temp[toi].cost = distance(last_row, last_switch, last_side,
 149                         points[i].first, points[i].second, +1);
 150                 ++toi;
 151
 152 taken:
 153                 1;
 154         }
 155
 156         std::sort(temp, temp + toi);
 157
 158         unsigned best_this_cost = UINT_MAX;
 159         for (unsigned i = 0; i < toi; ++i)
 160         {
 161                 ord[ind] = temp[i].o;
 162                 unsigned cost_rest = do_tsp(points, ord, temp + points.size() * 2, ind + 1, cost_so_far + temp[i].cost);
 163                 best_this_cost = std::min(best_this_cost, cost_rest);
 164         }
 165
 166         return best_this_cost;
 167 }
 168
 169 int main()
 170 {
 171         std::vector<std::pair<unsigned, unsigned> > points;
 172
 173         for ( ;; ) {
 174                 unsigned row, sw;
 175                 if (scanf("%u-%u", &row, &sw) != 2)
 176                         break;
 177
 178                 points.push_back(std::make_pair(row, sw));
 179         }
 180
 181         order *ord = new order[points.size()];
 182         best_tour = new order[points.size()];
 183         try_order *temp = new try_order[points.size() * points.size() * 4];
 184
 185         /* always start at the first one, left side (hack) */
 186         ord[0].pt = 0;
 187         ord[0].side = -1;
 188
 189         do_tsp(points, ord, temp, 1, 0);
 190         printf("All done.\n");
 191 }
 192
 193