Add a pessimistic distance to complement the optimistic one.

diff --git a/tsp/tsp.cpp b/tsp/tsp.cpp
index e7fbab05614c0577bcd9714347e700dafb3e5140..1a67eb352e42429e5bf8315dfb519a2bfec0ca7c 100644 (file)
--- 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];