haar_lib/graph/
tsp.rs

1//! 巡回セールスマン問題
2//!
3//! # Problems
4//! - <https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/all/DPL_2_A>
5
6use crate::graph::*;
7use std::ops::Add;
8
9/// 巡回セールスマン問題
10pub fn tsp<E: EdgeTrait>(g: &Graph<Directed, E>, src: usize) -> Option<E::Weight>
11where
12    E::Weight: Copy + Ord + Add<Output = E::Weight>,
13{
14    let n = g.len();
15    let mut dp: Vec<Vec<Option<E::Weight>>> = vec![vec![None; 1 << n]; n];
16
17    for e in g.nodes[src].edges.iter() {
18        let (to, cost) = (e.to(), e.weight());
19        dp[to][1 << to] = dp[to][1 << to].map(|x| x.min(cost)).or(Some(cost));
20    }
21
22    for s in 1..1 << n {
23        for i in 0..n {
24            if (s & (1 << i)) == 0 {
25                continue;
26            }
27
28            for e in g.nodes[i].edges.iter() {
29                let (to, cost) = (e.to(), e.weight());
30                if s & (1 << to) != 0 {
31                    continue;
32                }
33
34                if let Some(x) = dp[i][s] {
35                    let t = s | (1 << to);
36                    dp[to][t] = dp[to][t].map(|y| y.min(x + cost)).or(Some(x + cost));
37                }
38            }
39        }
40    }
41
42    dp[src][(1 << n) - 1]
43}
44
45#[cfg(test)]
46mod tests {
47    use super::*;
48
49    #[test]
50    fn test() {
51        // https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/2/DPL_2_A
52
53        let mut g = Graph::<Directed, _>::new(4);
54        g.extend(
55            vec![
56                (0, 1, 2),
57                (1, 2, 3),
58                (1, 3, 9),
59                (2, 0, 1),
60                (2, 3, 6),
61                (3, 2, 4),
62            ]
63            .into_iter()
64            .map(|(u, v, w)| Edge::new(u, v, w, ())),
65        );
66        assert_eq!(tsp(&g, 0), Some(16));
67
68        let mut g = Graph::<Directed, _>::new(3);
69        g.extend(
70            vec![(0, 1, 1), (1, 2, 1), (0, 2, 1)]
71                .into_iter()
72                .map(|(u, v, w)| Edge::new(u, v, w, ())),
73        );
74        assert_eq!(tsp(&g, 0), None);
75    }
76}
haar_lib/graph/tsp.rs

haar_lib/graph/
tsp.rs
