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.

diff --git a/tsp/tsp.cpp b/tsp/tsp.cpp
index 4ede3371cda48ca91a4b938439a9faf01e25b582..06fb7f0f1df7c0e13ca2450c48028e1e62fd2f7a 100644 (file)
--- a/tsp/tsp.cpp
+++ b/tsp/tsp.cpp
@@ -5,14 +5,11 @@
 #include <algorithm>
 
 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<std::pair<unsigned, unsigned> > &set1)
 
 void print_tour(std::vector<std::pair<unsigned, unsigned> > &points)
 {
+       std::set<std::pair<unsigned, unsigned> > 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<std::pair<unsigned, unsigned> > 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<std::pair<unsigned, unsigned> > 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<std::pair<unsigned, unsigned> >::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<std::pair<unsigned, unsigned> > &points, order *ord, try_order *temp, unsigned ind, unsigned cost_so_far)
+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)
 {
        if (cost_so_far >= best_so_far)
                return UINT_MAX;
@@ -202,37 +179,26 @@ unsigned do_tsp(std::vector<std::pair<unsigned, unsigned> > &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<std::pair<unsigned, unsigned> > mst_set;
+       std::set<std::pair<unsigned, unsigned> > 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<std::pair<unsigned, unsigned> >::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<std::pair<unsigned, unsigned> >::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<std::pair<unsigned, unsigned> > points;
+       std::set<std::pair<unsigned, unsigned> > 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");
 }