From 888bee2a13b0ab3cbf05adbda6479761b9973cfa Mon Sep 17 00:00:00 2001 From: "Steinar H. Gunderson" Date: Fri, 7 Apr 2006 12:41:21 +0000 Subject: [PATCH] Added a more-or-less naive travelling-salesman solver for finding the optimal switch routes. --- tsp/tsp.cpp | 193 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 193 insertions(+) create mode 100644 tsp/tsp.cpp diff --git a/tsp/tsp.cpp b/tsp/tsp.cpp new file mode 100644 index 0000000..40431e6 --- /dev/null +++ b/tsp/tsp.cpp @@ -0,0 +1,193 @@ +#include +#include +#include +#include + +int distance_switch(unsigned from, unsigned to) +{ + /* on the same side of the middle? 9.6m per switch. */ + if ((from > 3) == (to > 3)) { + return abs(from - to) * 96; + } + + /* have to cross the border? 25.8m from sw3->sw4 => 16.2m extra gap. */ + /* that's _got_ to be wrong. say it's 3m. */ + return abs(from - to) * 96 + 30; +} + +int distance_middle(unsigned sw, unsigned middle) +{ + /* symmetry: 4-5-6 are just mirrored 3-2-1. */ + if (middle == 2) { + if (sw > 3) + sw = 7 - sw; + + /* estimate 25.8m/2 = 12.9m from sw3 to the middle */ + return 129 + (3 - sw) * 96; + } + + /* more symmetry -- getting from 1-6 to the top is like getting from 6-1 to the bottom. */ + if (middle == 3) { + middle = 1; + sw = 7 - sw; + } + + /* guesstimate 4.8m extra to get to the bottom */ + if (sw > 3) + return 48 + 162 + (sw - 1) * 96; + else + return 48 + (sw - 1) * 96; +} + +int distance_row(unsigned from, unsigned to) +{ + /* don't calculate gaps here just yet, just estimate 4.1m per double row */ + return 41 * abs(from - to); +} + +int distance(int row_from, int switch_from, int side_from, int row_to, int switch_to, int side_to) +{ + /* can we just walk directly? */ + if (row_from == row_to && side_from == side_to) { + return distance_switch(switch_from, switch_to); + } + + /* can we just switch sides? */ + if (row_from + 1 == row_to && side_from == 1 && side_to == -1) { + return distance_switch(switch_from, switch_to); + } + if (row_from == row_to + 1 && side_from == -1 && side_to == 1) { + return distance_switch(switch_from, switch_to); + } + + /* we'll need to go to one of the three middles */ + int best1 = distance_middle(switch_from, 1) + distance_middle(switch_to, 1); + int best2 = distance_middle(switch_from, 2) + distance_middle(switch_to, 2); + int best3 = distance_middle(switch_from, 3) + distance_middle(switch_to, 3); + return std::min(std::min(best1, best2), best3) + distance_row(row_from, row_to); +} + +struct order { + unsigned pt; + int side; +}; +struct try_order { + order o; + int cost; + + bool operator< (const try_order &other) const + { + return (cost < other.cost); + } +}; + +static unsigned best_so_far = UINT_MAX; +order *best_tour; + +void print_tour(std::vector > &points) +{ + for (unsigned i = 0; i < points.size(); ++i) { + if (best_tour[i].side == -1) + printf("%2u-%u (left side) ", points[best_tour[i].pt].first, + points[best_tour[i].pt].second); + else + printf("%2u-%u (right side) ", points[best_tour[i].pt].first, + points[best_tour[i].pt].second); + if (i == 0) { + printf("\n"); + } else { + unsigned cost = distance( + points[best_tour[i-1].pt].first, + points[best_tour[i-1].pt].second, + best_tour[i-1].side, + points[best_tour[i].pt].first, + points[best_tour[i].pt].second, + best_tour[i].side); + printf("cost=%4u\n", cost); + } + } +} + +unsigned do_tsp(std::vector > &points, order *ord, try_order *temp, unsigned ind, unsigned cost_so_far) +{ + if (cost_so_far >= best_so_far) + return UINT_MAX; + if (ind == points.size()) { + memcpy(best_tour, ord, sizeof(order) * points.size()); + printf("\nNew best tour found! cost=%u\n", cost_so_far); + print_tour(points); + best_so_far = cost_so_far; + return 0; + } + + /* + * Simple heuristic: always search for the closest points from this one first; that + * will give us a sizable cutoff. + */ + unsigned toi = 0; + unsigned last_row = points[ord[ind-1].pt].first; + unsigned last_switch = points[ord[ind-1].pt].second; + unsigned last_side = ord[ind-1].side; + + for (unsigned i = 0; i < points.size(); ++i) { + /* taken earlier? */ + for (unsigned j = 0; j < ind; ++j) { + if (ord[j].pt == i) + goto taken; + } + + /* try both sides */ + temp[toi].o.pt = i; + temp[toi].o.side = -1; + temp[toi].cost = distance(last_row, last_switch, last_side, + points[i].first, points[i].second, -1); + ++toi; + + temp[toi].o.pt = i; + temp[toi].o.side = +1; + temp[toi].cost = distance(last_row, last_switch, last_side, + points[i].first, points[i].second, +1); + ++toi; + +taken: + 1; + } + + std::sort(temp, temp + toi); + + unsigned best_this_cost = UINT_MAX; + for (unsigned i = 0; i < toi; ++i) + { + ord[ind] = temp[i].o; + unsigned cost_rest = do_tsp(points, ord, temp + points.size() * 2, ind + 1, cost_so_far + temp[i].cost); + best_this_cost = std::min(best_this_cost, cost_rest); + } + + return best_this_cost; +} + +int main() +{ + std::vector > points; + + for ( ;; ) { + unsigned row, sw; + if (scanf("%u-%u", &row, &sw) != 2) + break; + + points.push_back(std::make_pair(row, sw)); + } + + order *ord = new order[points.size()]; + best_tour = new order[points.size()]; + try_order *temp = new try_order[points.size() * points.size() * 4]; + + /* always start at the first one, left side (hack) */ + ord[0].pt = 0; + ord[0].side = -1; + + do_tsp(points, ord, temp, 1, 0); + printf("All done.\n"); +} + + -- 2.39.2