Check the MST before doing anything else.

diff --git a/tsp/tsp.cpp b/tsp/tsp.cpp
index 1a67eb352e42429e5bf8315dfb519a2bfec0ca7c..fb09e216497b3bbec3fa78fd25cd43862b69cb91 100644 (file)
--- a/tsp/tsp.cpp
+++ b/tsp/tsp.cpp
@@ -286,18 +286,28 @@ unsigned do_tsp(std::vector<std::pair<unsigned, unsigned> > &points, std::set<st
                best_so_far = cost_so_far;
                return 0;
        }
+       
+       unsigned last_row = ord[ind-1].row;
+       unsigned last_switch = ord[ind-1].num;
+       unsigned last_side = ord[ind-1].side;
+
+       /* 
+        * The minimum spanning tree gives us a reliable lower bound for what we can
+        * achieve for the rest of the graph, so check it before doing anything else.
+        */
+       std::set<std::pair<unsigned, unsigned> > mst_set = points_left;
+       mst_set.insert(std::make_pair(last_row, last_switch));
+       
+       unsigned min_rest_cost = prim_mst(mst_set);
+       if (cost_so_far + min_rest_cost >= best_so_far) {
+               return UINT_MAX;
+       }
 
        /* 
         * 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 = 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 = points_left;
-       mst_set.insert(std::make_pair(last_row, last_switch));
        
        for (std::set<std::pair<unsigned, unsigned> >::iterator i = points_left.begin(); i != points_left.end(); ++i) {
                /* try both sides */
@@ -313,12 +323,6 @@ unsigned do_tsp(std::vector<std::pair<unsigned, unsigned> > &points, std::set<st
                temp[toi].cost = cache(last_row, last_switch, last_side, i->first, i->second, 1);
                ++toi;
        }
-
-       unsigned min_rest_cost = prim_mst(mst_set);
-       if (cost_so_far + min_rest_cost >= best_so_far) {
-               return UINT_MAX;
-       }
-       
        std::sort(temp, temp + toi);
 
        unsigned best_this_cost = UINT_MAX;