small minimum hamilt. path improvement: during & after 2-opt refinement, rotate longest edge to border

1 files changed, 20 insertions, 0 deletions

diff --git a/src/tsp_approx.rs b/src/tsp_approx.rs
index d8c30fe..a23a726 100644
--- a/src/tsp_approx.rs
+++ b/src/tsp_approx.rs
@@ -377,6 +377,23 @@ fn refine_2_opt(dist_cache: &DistCache, tour: Vec<usize>) -> (bool, Vec<usize>)
     (improved, tour_flat)
 }
 
+fn rotate_towards_optimum(dist_cache: &DistCache, tour: &mut [usize]) {
+    let mut max_dist = dist_cache.dist(tour[0], tour[tour.len() - 1]);
+    let mut max_dist_at = tour.len() - 1;
+
+    for i in 0..tour.len() - 2 {
+        let next_dist = dist_cache.dist(tour[i], tour[i + 1]);
+        if next_dist > max_dist {
+            max_dist = next_dist;
+            max_dist_at = i;
+        }
+    }
+
+    if max_dist_at != tour.len() - 1 {
+        tour.rotate_left(max_dist_at + 1);
+    }
+}
+
 fn get_dist_cache<M>(embeds: &[M], hash_seed: &Option<u64>) -> DistCache
 where
     M: MetricElem,
@@ -424,6 +441,7 @@ where
     };
 
     for _ in 0..refinements {
+        rotate_towards_optimum(&dc, &mut tour);
         let res = refine_2_opt(&dc, tour);
         tour = res.1;
         if !res.0 {
@@ -431,6 +449,8 @@ where
         }
     }
 
+    rotate_towards_optimum(&dc, &mut tour);
+
     let mut total_dist = 0.;
     for i in 0..tour.len() - 1 {
         let (a, b) = (tour[i], tour[i + 1]);