From 392660c920b56ab785c4f664b5a287aef9be9f98 Mon Sep 17 00:00:00 2001
From: "Steinar H. Gunderson" <sesse@samfundet.no>
Date: Fri, 7 Apr 2006 20:21:48 +0000
Subject: [PATCH] Add a pessimistic distance to complement the optimistic one.

---
 tsp/tsp.cpp | 54 +++++++++++++++++++++++++++++++++++------------------
 1 file changed, 36 insertions(+), 18 deletions(-)

diff --git a/tsp/tsp.cpp b/tsp/tsp.cpp
index e7fbab0..1a67eb3 100644
--- a/tsp/tsp.cpp
+++ b/tsp/tsp.cpp
@@ -11,7 +11,9 @@
 #define HEAP_MST 0
 
 static const unsigned num_cache_elem = (MAX_ROW * MAX_SWITCH * 2) * (MAX_ROW * MAX_SWITCH * 2);
-static unsigned short dist_cache[(MAX_ROW * MAX_SWITCH * 2) * (MAX_ROW * MAX_SWITCH * 2)], opt_dist_cache[MAX_ROW * MAX_SWITCH * MAX_ROW * MAX_SWITCH];
+static unsigned short dist_cache[(MAX_ROW * MAX_SWITCH * 2) * (MAX_ROW * MAX_SWITCH * 2)],
+	opt_dist_cache[MAX_ROW * MAX_SWITCH * MAX_ROW * MAX_SWITCH],
+	pess_dist_cache[MAX_ROW * MAX_SWITCH * MAX_ROW * MAX_SWITCH];
 
 inline unsigned short &cache(
 	unsigned row_from, unsigned switch_from, unsigned side_from,
@@ -29,6 +31,14 @@ inline unsigned short &opt_cache(
 		row_to * MAX_SWITCH + switch_to];
 }
 
+inline unsigned short &pess_cache(
+	unsigned row_from, unsigned switch_from,
+	unsigned row_to, unsigned switch_to)
+{
+	return pess_dist_cache[(row_from * MAX_SWITCH + switch_from) * (MAX_ROW * MAX_SWITCH) +
+		row_to * MAX_SWITCH + switch_to];
+}
+
 struct order {
 	unsigned row, num;
 	int side;
@@ -85,21 +95,8 @@ int distance_row(unsigned from, unsigned to)
 	return 41 * abs(from - to);
 }
 
-int distance(int row_from, int switch_from, int side_from, int row_to, int switch_to, int side_to)
+int pessimistic_distance(int row_from, int switch_from, int row_to, int switch_to)
 {
-	/* can we just walk directly? */
-	if (row_from == row_to && side_from == side_to) {
-		return distance_switch(switch_from, switch_to);
-	}
-
-	/* can we just switch sides? */
-	if (row_from + 1 == row_to && side_from == 1 && side_to == 0) {
-		return distance_switch(switch_from, switch_to);
-	}
-	if (row_from == row_to + 1 && side_from == 0 && side_to == 1) {
-		return distance_switch(switch_from, switch_to);
-	}
-	
 	/* we'll need to go to one of the three middles */
 	int best2 = distance_middle(switch_from, 2) + distance_middle(switch_to, 2);
 	int distrow = distance_row(row_from, row_to);
@@ -114,12 +111,30 @@ int distance(int row_from, int switch_from, int side_from, int row_to, int switc
 	}
 }
 
+int distance(int row_from, int switch_from, int side_from, int row_to, int switch_to, int side_to)
+{
+	/* can we just walk directly? */
+	if (row_from == row_to && side_from == side_to) {
+		return distance_switch(switch_from, switch_to);
+	}
+	
+	/* can we just switch sides? */
+	if (row_from + 1 == row_to && side_from == 1 && side_to == 0) {
+		return distance_switch(switch_from, switch_to);
+	}
+	if (row_from == row_to + 1 && side_from == 0 && side_to == 1) {
+		return distance_switch(switch_from, switch_to);
+	}
+
+	return pessimistic_distance(row_from, switch_from, row_to, switch_to);
+}	
+
 int optimistic_distance(int row_from, int switch_from, int row_to, int switch_to)
 {
-	if (abs(row_from - row_to) == 1)
+	if (abs(row_from - row_to) <= 1)
 		return distance_switch(switch_from, switch_to);
 	else
-		return distance(row_from, switch_from, 0, row_to, switch_to, 0);
+		return pessimistic_distance(row_from, switch_from, row_to, switch_to);
 }
 
 #if HEAP_MST
@@ -359,9 +374,12 @@ int main()
 			
 			opt_cache(points[i].first, points[i].second, points[j].first, points[j].second) =
 				optimistic_distance(points[i].first, points[i].second, points[j].first, points[j].second);
+			
+			pess_cache(points[i].first, points[i].second, points[j].first, points[j].second) =
+				pessimistic_distance(points[i].first, points[i].second, points[j].first, points[j].second);
 		}
 	}
-
+	
 	order *ord = new order[points.size()];
 	best_tour = new order[points.size()];
 	order *temp = new order[points.size() * points.size() * 4];
-- 
2.39.2