Optimize the TSP solver by using the MST of the rest of the graph as a lower bound.

diff --git a/tsp/tsp.cpp b/tsp/tsp.cpp
index 40431e634f7e1ed1f325ec1eba64acd4440bed2f..a87585f6f321695ced5b6406bc08802df7daac09 100644 (file)
--- a/tsp/tsp.cpp
+++ b/tsp/tsp.cpp
@@ -1,8 +1,26 @@
 #include <stdio.h>
 #include <limits.h>
 #include <vector>
+#include <set>
 #include <algorithm>
 
+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;
+
 int distance_switch(unsigned from, unsigned to)
 {
        /* on the same side of the middle? 9.6m per switch. */
@@ -67,22 +85,50 @@ int distance(int row_from, int switch_from, int side_from, int row_to, int switc
        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;
+int optimistic_distance(int row_from, int switch_from, int row_to, int switch_to)
+{
+       if (abs(row_from - row_to) == 1)
+               return distance_switch(switch_from, switch_to);
+       else
+               return distance(row_from, switch_from, -1, row_to, switch_to, -1);
+}
 
-       bool operator< (const try_order &other) const
-       {
-               return (cost < other.cost);
+// extremely primitive O(V^2) prim
+int prim_mst(std::vector<std::pair<unsigned, unsigned> > &points, try_order *temp, unsigned toi)
+{
+       std::set<std::pair<unsigned, unsigned> > set1, set2;
+
+       for (unsigned i = 0; i < toi; ++i)
+               set1.insert(points[temp[i].o.pt]);
+
+       // pick the first one
+       std::set<std::pair<unsigned, unsigned> >::iterator start = set1.begin();
+       set2.insert(*start);
+       set1.erase(start);
+
+       unsigned total_cost = 0;
+       while (set1.size() > 0) {
+               unsigned best_this_cost = UINT_MAX;
+               std::set<std::pair<unsigned, unsigned> >::iterator best_set1;
+               
+               for (std::set<std::pair<unsigned, unsigned> >::iterator i = set1.begin(); i != set1.end(); ++i) {
+                       for (std::set<std::pair<unsigned, unsigned> >::iterator j = set2.begin(); j != set2.end(); ++j) {
+                               unsigned d = optimistic_distance(i->first, i->second, j->first, j->second);
+                               if (d < best_this_cost) {
+                                       best_this_cost = d;
+                                       best_set1 = i;
+                               }
+                       }
+               }
+
+               set2.insert(*best_set1);
+               set1.erase(best_set1);
+               total_cost += best_this_cost;
        }
-};
 
-static unsigned best_so_far = UINT_MAX;
-order *best_tour;
+       return total_cost;
+}
+
 
 void print_tour(std::vector<std::pair<unsigned, unsigned> > &points)
 {
@@ -153,6 +199,11 @@ taken:
                1;
        }
 
+       unsigned min_rest_cost = prim_mst(points, temp, toi);
+       if (cost_so_far + min_rest_cost >= best_so_far) {
+               return UINT_MAX;
+       }
+       
        std::sort(temp, temp + toi);
 
        unsigned best_this_cost = UINT_MAX;