algorithms_edu/problems/graph/tsp/
brute_force.rs

1use crate::algo::graph::WeightedAdjacencyMatrix;
2use crate::algo::misc::permutations::*;
3
4pub fn tsp(g: &WeightedAdjacencyMatrix, start: usize) -> (f64, Vec<usize>) {
5    let n = g.node_count();
6    let permutations = (0..n)
7        .filter(|&i| i != start)
8        .collect::<Vec<_>>()
9        .permutations();
10    let mut tour = vec![];
11    let mut best_tour_cost = f64::INFINITY;
12    for perm in permutations {
13        let perm = unsafe { &*perm };
14        let cost = compute_tour_cost(g, perm, start);
15        if cost < best_tour_cost {
16            best_tour_cost = cost;
17            tour = perm.to_owned();
18        }
19    }
20    tour.insert(0, start);
21    (best_tour_cost, tour)
22}
23
24fn compute_tour_cost(g: &WeightedAdjacencyMatrix, tour: &[usize], start: usize) -> f64 {
25    tour.windows(2)
26        .fold(0., |cost, step| cost + g[step[0]][step[1]])
27        + g[start][*tour.first().unwrap()]
28        + g[*tour.last().unwrap()][start]
29}
30
31// #[cfg(test)]
32// mod tests {
33//     use super::*;
34//     use crate::algo::graph::WeightedAdjacencyList;
35//     #[test]
36//     fn test_tsp_brute_force() {
37//         let g: WeightedAdjacencyMatrix = WeightedAdjacencyList::new_undirected(
38//             6,
39//             &[
40//                 (5, 0, 10.),
41//                 (1, 5, 12.),
42//                 (4, 1, 2.),
43//                 (2, 4, 4.),
44//                 (3, 2, 6.),
45//                 (0, 3, 8.),
46//             ],
47//         )
48//         .into();
49//         assert_eq!(&tsp(&g), &[0, 3, 2, 4, 1, 5, 0]);
50//     }
51// }
algorithms_edu/problems/graph/tsp/brute_force.rs

algorithms_edu/problems/graph/tsp/
brute_force.rs
