oxicuda_graphalg/tsp/
two_opt.rs

1//! 2-opt local search improvement for TSP tours.
2
3use crate::error::{GraphalgError, GraphalgResult};
4
5pub fn two_opt_improve(
6    tour: &[usize],
7    dist: &[f64],
8    n: usize,
9    max_iter: usize,
10) -> GraphalgResult<Vec<usize>> {
11    if dist.len() != n * n {
12        return Err(GraphalgError::DimensionMismatch {
13            a: dist.len(),
14            b: n * n,
15        });
16    }
17    if tour.len() != n {
18        return Err(GraphalgError::DimensionMismatch {
19            a: tour.len(),
20            b: n,
21        });
22    }
23    let mut t = tour.to_vec();
24    let mut iters = 0usize;
25    let mut improved = true;
26    while improved && iters < max_iter {
27        improved = false;
28        iters += 1;
29        for i in 0..n - 1 {
30            for j in i + 1..n {
31                let a = t[i];
32                let b = t[(i + 1) % n];
33                let c = t[j];
34                let d = t[(j + 1) % n];
35                if a == c || b == d {
36                    continue;
37                }
38                let old_cost = dist[a * n + b] + dist[c * n + d];
39                let new_cost = dist[a * n + c] + dist[b * n + d];
40                if new_cost + 1e-12 < old_cost {
41                    t[i + 1..=j].reverse();
42                    improved = true;
43                }
44            }
45        }
46    }
47    Ok(t)
48}
49
50#[cfg(test)]
51mod tests {
52    use super::*;
53
54    #[test]
55    fn two_opt_runs() {
56        let pts: [(f64, f64); 4] = [(0.0, 0.0), (1.0, 0.0), (1.0, 1.0), (0.0, 1.0)];
57        let n = 4;
58        let mut d = vec![0.0; n * n];
59        for i in 0..n {
60            for j in 0..n {
61                let dx = pts[i].0 - pts[j].0;
62                let dy = pts[i].1 - pts[j].1;
63                d[i * n + j] = (dx * dx + dy * dy).sqrt();
64            }
65        }
66        let init = vec![0, 2, 1, 3];
67        let t = two_opt_improve(&init, &d, n, 50).expect("ok");
68        let cost: f64 = (0..n).map(|i| d[t[i] * n + t[(i + 1) % n]]).sum();
69        assert!(cost <= 4.0 + 1e-9);
70    }
71}
oxicuda_graphalg/tsp/two_opt.rs

oxicuda_graphalg/tsp/
two_opt.rs
