Print out some diagnostics showing how well the MST bound works.

diff --git a/tsp/tsp.cpp b/tsp/tsp.cpp
index 5fd1dcb615becbf5e6b7142a1d4b4c36e2fff128..4ede3371cda48ca91a4b938439a9faf01e25b582 100644 (file)
--- a/tsp/tsp.cpp
+++ b/tsp/tsp.cpp
@@ -137,7 +137,7 @@ void print_tour(std::vector<std::pair<unsigned, unsigned> > &points)
                        printf("%2u-%u (right side) ", points[best_tour[i].pt].first,
                                points[best_tour[i].pt].second);
                if (i == 0) {
-                       printf("\n");
+                       printf("           ");
                } else {
                        unsigned cost = distance(
                                points[best_tour[i-1].pt].first,
@@ -146,8 +146,42 @@ void print_tour(std::vector<std::pair<unsigned, unsigned> > &points)
                                points[best_tour[i].pt].first,
                                points[best_tour[i].pt].second,
                                best_tour[i].side);
-                       printf("cost=%4u\n", cost);
+                       printf("cost=%4u  ", 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;
+                       }
+
+                       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);
+                       }
+                       
+                       printf("rest_cost=%5u", rest_cost);
+               }
+               printf("\n");
        }
 }