Traveling Salesman Problem
(dp/TravelingSalesmanProblem.hpp)

• View this file on GitHub
• Last update: 2024-08-24 16:53:34+09:00
• Include: #include "dp/TravelingSalesmanProblem.hpp"

概要

todo

計算量

todo

Code

#pragma once
template <class T>
vector<vector<T>> tsp(vector<vector<T>> &w, int n) {
    T INF = numeric_limits<T>::max();
    vector<vector<T>> dp(n, vector<T>((1 << (n + 1)), INF));
    dp[0][0] = 0;
    for (int bit = 0; bit < (1 << n); bit++) {
        for (int cur = 0; cur < n; cur++) {
            if (dp[cur][bit] == INF) continue;
            for (int nex = 0; nex < n; nex++) {
                if ((bit / (1 << nex)) % 2 == 1) continue;
                dp[nex][bit | (1 << nex)] = min(dp[nex][bit | (1 << nex)], dp[cur][bit] + w[cur][nex]);
            }
        }
    }
    return dp;
}

#line 2 "dp/TravelingSalesmanProblem.hpp"
template <class T>
vector<vector<T>> tsp(vector<vector<T>> &w, int n) {
    T INF = numeric_limits<T>::max();
    vector<vector<T>> dp(n, vector<T>((1 << (n + 1)), INF));
    dp[0][0] = 0;
    for (int bit = 0; bit < (1 << n); bit++) {
        for (int cur = 0; cur < n; cur++) {
            if (dp[cur][bit] == INF) continue;
            for (int nex = 0; nex < n; nex++) {
                if ((bit / (1 << nex)) % 2 == 1) continue;
                dp[nex][bit | (1 << nex)] = min(dp[nex][bit | (1 << nex)], dp[cur][bit] + w[cur][nex]);
            }
        }
    }
    return dp;
}

Back to top page