From b0050faec0fbda2b25aae62ae923841b90c396bf Mon Sep 17 00:00:00 2001
From: "Steinar H. Gunderson" <sesse@samfundet.no>
Date: Fri, 7 Apr 2006 21:20:45 +0000
Subject: [PATCH] Check the MST before doing anything else.

---
 tsp/tsp.cpp | 28 ++++++++++++++++------------
 1 file changed, 16 insertions(+), 12 deletions(-)

diff --git a/tsp/tsp.cpp b/tsp/tsp.cpp
index 1a67eb3..fb09e21 100644
--- 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;
-- 
2.39.5