ホーム > libalgo

巡回セールスマン問題

概要

巡回セールスマン問題を動的計画法によって解きます.

使い方

dp[S][v] = u $\in$ S を全て訪れ v にいるときの最小値.

計算量

$O(E 2^V)$

実装

Weight travelingSalesman(const Graph &g) {
    int n = g.size();
    Matrix dp(1 << n, Array(n, inf));
    dp[0][0] = 0;
    for (int S = 0; S < 1 << n; S++) {
        for (auto &es : g) {
            for (auto &e : es) {
                int u = e.src, v = e.dst;
                auto w = e.weight;
                if (~S >> v & 1) dp[S | 1 << v][v] = std::min(dp[S | 1 << v][v], dp[S][u] + w);
            }
        }
    }
    return dp[(1 << n) - 1][0];
}

検証

AOJ GRL1A (Submission)