From abf0c1bf40a09aa9f6e1bff36c3afb82490f33e6 Mon Sep 17 00:00:00 2001 From: "Steinar H. Gunderson" Date: Fri, 7 Apr 2006 13:50:41 +0000 Subject: [PATCH] Some restructuring. Highlights - merge try_order and order - no longer keep pointers to points[] around, just copy (row,num) - keep a std::set "points_left" at all times instead of scanning for those we haven't found yet; this is also nicely feeded to the Prim algorithm which already needs such a set. All this gains us a few percent extra, it seems. --- tsp/tsp.cpp | 111 ++++++++++++++++++++-------------------------------- 1 file changed, 43 insertions(+), 68 deletions(-) diff --git a/tsp/tsp.cpp b/tsp/tsp.cpp index 4ede337..06fb7f0 100644 --- a/tsp/tsp.cpp +++ b/tsp/tsp.cpp @@ -5,14 +5,11 @@ #include struct order { - unsigned pt; + unsigned row, num; int side; -}; -struct try_order { - order o; int cost; - bool operator< (const try_order &other) const + bool operator< (const order &other) const { return (cost < other.cost); } @@ -129,63 +126,43 @@ int prim_mst(std::set > &set1) void print_tour(std::vector > &points) { + std::set > points_left; + for (unsigned i = 0; i < points.size(); ++i) { + points_left.insert(points[i]); + } + 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); + printf("%2u-%u (left side) ", best_tour[i].row, best_tour[i].num); else - printf("%2u-%u (right side) ", points[best_tour[i].pt].first, - points[best_tour[i].pt].second); + printf("%2u-%u (right side) ", best_tour[i].row, best_tour[i].num); if (i == 0) { printf(" "); } 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 ", cost); + printf("cost=%4u ", best_tour[i].cost); } // let's see how good the MST heuristics are if (i != points.size() - 1) { - std::set > mst_tree; - - mst_tree.insert(points[best_tour[i].pt]); - - for (unsigned j = 0; j < points.size(); ++j) { - for (unsigned k = 0; k < i; ++k) - if (best_tour[k].pt == j) - goto taken; - - mst_tree.insert(points[j]); - -taken: - 1; - } - + std::set > mst_tree = points_left; printf("mst_bound=%5u, ", prim_mst(mst_tree)); unsigned rest_cost = 0; for (unsigned j = i + 1; j < points.size(); ++j) { - rest_cost += distance( - points[best_tour[j-1].pt].first, - points[best_tour[j-1].pt].second, - best_tour[j-1].side, - points[best_tour[j].pt].first, - points[best_tour[j].pt].second, - best_tour[j].side); + rest_cost += best_tour[j].cost; } printf("rest_cost=%5u", rest_cost); } + printf("\n"); + + std::set >::iterator j = points_left.find(std::make_pair(best_tour[i].row, best_tour[i].num)); + points_left.erase(j); } } -unsigned do_tsp(std::vector > &points, order *ord, try_order *temp, unsigned ind, unsigned cost_so_far) +unsigned do_tsp(std::vector > &points, std::set > &points_left, order *ord, order *temp, unsigned ind, unsigned cost_so_far) { if (cost_so_far >= best_so_far) return UINT_MAX; @@ -202,37 +179,26 @@ unsigned do_tsp(std::vector > &points, order *ord, * 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_row = ord[ind-1].row; + unsigned last_switch = ord[ind-1].num; unsigned last_side = ord[ind-1].side; - std::set > mst_set; + std::set > mst_set = points_left; mst_set.insert(std::make_pair(last_row, last_switch)); - for (unsigned i = 0; i < points.size(); ++i) { - /* taken earlier? */ - for (unsigned j = 0; j < ind; ++j) { - if (ord[j].pt == i) - goto taken; - } - + for (std::set >::iterator i = points_left.begin(); i != points_left.end(); ++i) { /* 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); + temp[toi].row = i->first; + temp[toi].num = i->second; + temp[toi].side = -1; + temp[toi].cost = distance(last_row, last_switch, last_side, i->first, 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); + temp[toi].row = i->first; + temp[toi].num = i->second; + temp[toi].side = +1; + temp[toi].cost = distance(last_row, last_switch, last_side, i->first, i->second, +1); ++toi; - - mst_set.insert(points[i]); - -taken: - 1; } unsigned min_rest_cost = prim_mst(mst_set); @@ -245,8 +211,13 @@ taken: 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); + ord[ind] = temp[i]; + + std::set >::iterator j = points_left.find(std::make_pair(temp[i].row, temp[i].num)); + points_left.erase(j); + unsigned cost_rest = do_tsp(points, points_left, ord, temp + points.size() * 2, ind + 1, cost_so_far + temp[i].cost); + points_left.insert(std::make_pair(temp[i].row, temp[i].num)); + best_this_cost = std::min(best_this_cost, cost_rest); } @@ -256,6 +227,7 @@ taken: int main() { std::vector > points; + std::set > points_left; for ( ;; ) { unsigned row, sw; @@ -263,17 +235,20 @@ int main() break; points.push_back(std::make_pair(row, sw)); + if (points.size() != 1) + points_left.insert(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]; + order *temp = new order[points.size() * points.size() * 4]; /* always start at the first one, left side (hack) */ - ord[0].pt = 0; + ord[0].row = points[0].first; + ord[0].num = points[0].second; ord[0].side = -1; - do_tsp(points, ord, temp, 1, 0); + do_tsp(points, points_left, ord, temp, 1, 0); printf("All done.\n"); } -- 2.39.5