Rustコトハジメ

プログラミング言語Rustに関する情報をお届けします。

中国人郵便配達問題の考え方

中国人郵便配達問題とは

中国人郵便配達問題は、巡回セールスマン問題

www.rustforbeginners.com

の類問ですが、すべてのノードではなく、すべてのエッジを通るという問題です。

https://onlinejudge.u-aizu.ac.jp/problems/DPL_2_B

f:id:akiradeveloper529:20190307134933j:plain

名前の由来が気になったのでぐぐるとやばいタイトルの本が見つかりました。これが正しいならこの記事のタイトルも「コンピュータサイエンス最大の難関の考え方」にしていいはずなのですが、やめましょう。たぶんVがものすごく大きい時のことを言ってるのでしょうから。しらんけど。

中国人郵便配達問題=コンピュータサイエンス最大の難関 (講談社選書メチエ)

中国人郵便配達問題=コンピュータサイエンス最大の難関 (講談社選書メチエ)

名前の由来は、この問題に一番はじめに取り組んでいた中国人の数学者のMei-Ko Kwanさんにちなむそうです。

考え方

  1. 全部のノードの次数が偶数になればオイラーグラフとなる
  2. 次数が奇数のノードを洗い出す。この数は必ず偶数となる (グラフ中の次数の合計は偶数だから)
  3. 次数奇数のノードを結んでいった時に経路長の合計が最小となるマッチングをみつけて、その経路を複製する。(各辺は何回通ってもよいため許される)

次数奇数ノード間の最小距離はワーシャルフロイド法で計算出来ます。マッチングを見つけるところは、マッチングしたノードのセットでビットDPすればいいです。最速ではO(V3)で解けることがwikiに書いてありますが、このアルゴリズムはO(2V V2)です。しかし今回はVがたかだか15と小さいので解くことが出来ます。

コード

fn solve() {
    input! {
        V: usize, E: usize,
        X: [(usize,usize,usize); E],
    }

    let mut dist = vec![vec![1<<60; V]; V];
    for i in 0..V {
        dist[i][i] = 0;
    }

    let mut deg = vec![0; V];

    let mut cost0 = 0;
    for i in 0..E {
        let (s,t,d) = X[i];
        cost0 += d;
        dist[s][t] = min(dist[s][t], d);
        dist[t][s] = min(dist[t][s], d);
        deg[s] += 1;
        deg[t] += 1;
    }

    // Find odd nodes
    let mut odd_nodes = vec![];
    for i in 0..V {
        if deg[i] % 2 != 0 {
            odd_nodes.push(i);
        }
    }
    let M = odd_nodes.len();
    assert!(M%2==0);

    // WF
    for k in 0..V {
        for i in 0..V {
            for j in 0..V {
                if k==i || k==j { continue; }

                dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
            }
        }
    }

    let mut dp = vec![1<<60; (1<<M)];
    dp[0] = 0;
    for s in 0..(1<<M) {
        for i in 0..M {
            for j in 0..M {
                if i==j { continue; }
                if s & (1<<i) == 0 || s & (1<<j) == 0 { continue; }

                let s_no_ij = ((s as i64) - (1<<i) - (1<<j)) as usize;
                dp[s] = min(dp[s], dp[s_no_ij] + dist[odd_nodes[i]][odd_nodes[j]]);
            }
        }
    }

    let cost1 = dp[(1<<M)-1];
    println!("{}", cost0+cost1);
}

((s as i64) - (1<<i) - (1<<j)) as usizeとかいうコードを書かないといけないのがRustのまどろっこしいところですね。