From 84465cf43be0174f2fc5438ec31540259669c840 Mon Sep 17 00:00:00 2001 From: "Steinar H. Gunderson" Date: Fri, 7 Apr 2006 21:55:03 +0000 Subject: [PATCH] Make a slightly more realistic estimate for moving between facing rows (1m plus any gaps, instead of 0m regardless as before). Amazingly enough, this boosts the time enormously, as the optimistic bound becomes a lot better. --- tsp/tsp.cpp | 8 +++++--- 1 file changed, 5 insertions(+), 3 deletions(-) diff --git a/tsp/tsp.cpp b/tsp/tsp.cpp index 9fdeaed..469cede 100644 --- a/tsp/tsp.cpp +++ b/tsp/tsp.cpp @@ -132,10 +132,10 @@ int distance(int row_from, int switch_from, int side_from, int row_to, int switc /* can we just switch sides? */ if (row_from + 1 == row_to && side_from == 1 && side_to == 0) { - return distance_switch(switch_from, switch_to); + return pessimistic_distance(switch_from, row_from, switch_to, row_to) - 31; } if (row_from == row_to + 1 && side_from == 0 && side_to == 1) { - return distance_switch(switch_from, switch_to); + return pessimistic_distance(switch_from, row_from, switch_to, row_to) - 31; } return pessimistic_distance(row_from, switch_from, row_to, switch_to); @@ -143,8 +143,10 @@ int distance(int row_from, int switch_from, int side_from, int row_to, int switc int optimistic_distance(int row_from, int switch_from, int row_to, int switch_to) { - if (abs(row_from - row_to) <= 1) + if (row_from == row_to) return distance_switch(switch_from, switch_to); + else if (abs(row_from - row_to) == 1) + return pessimistic_distance(row_from, switch_from, row_to, switch_to) - 31; else return pessimistic_distance(row_from, switch_from, row_to, switch_to); } -- 2.39.2