Rustコトハジメ

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

巡回セールスマン問題の考え方

巡回セールスマン問題が初見で解けなかったので、考え方をまとめておきます。

巡回セールスマン問題とは

https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/2/DPL_2_A

f:id:akiradeveloper529:20190307135107j:plain

全部の点を通って帰ってくる最短経路を求めなさいという問題です。Vが15ほどですが、全部の並び順を調べるという方針で15!をやってしまうとTLEします。10くらいならギリいけるのかもしれませんが。

考え方

対称性から0番目のノードから出発することにして構いません。どうせ回ってるから、どこから出発しても同じです。

その上で、DPテーブルを、

dp[0から出発して訪れたノードの集合][最後に訪れたノード]

と定義します。すると、dp[全部訪れた集合][0]が求める答えということになります。これをノーヒントで思いつく人はすごすぎます。

そして今回は、この集合をビット列で表します。(なのでこれをbitDPといいます) 例えば、3ならば、0番目と1番目のノードに行きましたということです。

あとは、

dp[bit][t] = dp[bitからtを除いた][k] + cost(k, t) (for all k)

を計算していきます。

コード

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

    let inf = 1<<60;
    let mut cost = vec![vec![inf; V]; V]; // cost of s->t
    for i in 0..X.len() {
        let (s,t,d) = X[i];
        cost[s][t] = d;
    }
    // dp[bit][t]
    // bit: visited nodes
    // t: terminal
    let mut dp = vec![vec![inf; V]; (1<<V)];

    dp[0][0] = 0;
    for bit in 1..(1<<V) {
        for t in 0..V {
            if bit & (1<<t) > 0 {
                for k in 0..V {
                    dp[bit][t] = min(dp[bit][t], dp[bit-(1<<t)][k] + cost[k][t]);
                }
            }
        }
    }

    let ans = if dp[(1<<V)-1][0] == inf {
        -1
    } else {
        dp[(1<<V)-1][0] as i64
    };

    println!("{}", ans);
}