From 19bc8938f3298412f9e1bc295cae941f802951a5 Mon Sep 17 00:00:00 2001
From: "Steinar H. Gunderson" <sesse@samfundet.no>
Date: Fri, 7 Apr 2006 13:10:38 +0000
Subject: [PATCH] Optimize the TSP solver by using the MST of the rest of the
 graph as a lower bound.

---
 tsp/tsp.cpp | 77 ++++++++++++++++++++++++++++++++++++++++++++---------
 1 file changed, 64 insertions(+), 13 deletions(-)

diff --git a/tsp/tsp.cpp b/tsp/tsp.cpp
index 40431e6..a87585f 100644
--- 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;
-- 
2.39.2