巡回セールスマン問題を解くDP
(ugilib/graph/tsp.hpp)

• View this file on GitHub
• Last update: 2024-04-03 22:46:30+09:00
• Include: #include "ugilib/graph/tsp.hpp"

Depends on

• ugilib/base/constants.hpp
• ugilib/base/definitions.hpp
• 数値 -> ビット配列 (ugilib/bit/bit_util.hpp)

Verified with

• tests/graph/tsp.test.cpp

Code

#pragma once
#include <bits/stdc++.h>
#include "ugilib/base/constants.hpp"
#include "ugilib/bit/bit_util.hpp"

using namespace std;

namespace ugilib {
    /**
     * @brief 巡回セールスマン問題を解くDP
     * @param n 都市数
     * @param start 始点
     * @param graph グラフ. vector<pair<int, weight_t>> で隣接頂点とコストを表す
     * @param weight_inf 無限大の値. パスが存在しない場合のコスト
     * @return 始点から各頂点を一度だけ通って戻ってくる最小コスト
     * @note O(2^n * n^2)
    */
    template <typename weight_t>
    weight_t tsp_bitDP(int n, int start, const vector<vector<pair<int, weight_t>>> &graph, const weight_t weight_inf = ugilib::constants::INF<weight_t>) {
        const int num_states = (1 << n);
        // dp[これまでに取った都市集合. [0, 2^n-1]][現在地. [0, n-1]]
        vector<vector<weight_t>> dp(num_states, vector<weight_t>(n, weight_inf));
        dp[0][start] = 0;

        // 全状態についてDPする
        for (int i = 0; i < num_states; i++) {
            // 状態をビット表現する
            auto bits = ugilib::num_to_bits(i, n);
            // 今どの都市にいるか
            for (int j = 0; j < n; j++) {
                if (dp[i][j] == weight_inf) continue;  // この状態に辿り着かない場合
                // 次どの都市に行くか
                for (const auto [node, cost] : graph[j]) {
                    if (bits[node]) continue;  // 訪問済み
                    // 訪問する
                    bits[node] = true;
                    auto &dest = dp[ugilib::bits_to_num(bits)][node];
                    dest = min(dest, dp[i][j] + cost);
                    bits[node] = false;
                }
            }
        }

        return dp[num_states-1][start];  // 全状態訪問後にstartに戻って来る最小コスト
    }
    }  // namespace ugilib

#line 2 "ugilib/graph/tsp.hpp"
#include <bits/stdc++.h>
#line 2 "ugilib/base/definitions.hpp"

using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define rep(i, n) for(size_t i = 0; i < n; i++)  // rep macro
#define all(v) begin(v), end(v)  // all iterator
#line 3 "ugilib/base/constants.hpp"

namespace ugilib::constants {
    template<typename T>
    inline constexpr T INF = std::numeric_limits<T>::max() / 2;
} // namespace ugilib::constants

const ll INF = ugilib::constants::INF<ll>;
#line 4 "ugilib/bit/bit_util.hpp"

using namespace std;

namespace ugilib {
    /**
     * @brief 数値 -> ビット配列
     * @param num ビット配列にするための数値
     * @param digit ビット数
     * @return vector<bool> 変換されたビット配列. 0番目が一番下の桁
     * @details 数値を指定桁のビット配列に変換する
    */
    vector<bool> num_to_bits(const ll num, const size_t &digit) {
        vector<bool> bits(digit);
        for (int i = 0; i < digit; i++) {
            bits[i] = (num >> i) & 1U;
        }
        return bits;
    }

    /**
     * @brief ビット配列 -> 数値
     * @param bits 数値にするためのビット配列. 0番目が一番下の桁
     * @return ll 変換された数値
     * @details ビット配列を数値に戻す. num_to_bitsの逆変換
    */
    ll bits_to_num(const vector<bool> &bits) {
        ll num = 0;
        for (int i = 0; i < bits.size(); i++) {
            num += bits[i] << i;
        }
        return num;
    }
}  // namespace ugilib
#line 5 "ugilib/graph/tsp.hpp"

using namespace std;

namespace ugilib {
    /**
     * @brief 巡回セールスマン問題を解くDP
     * @param n 都市数
     * @param start 始点
     * @param graph グラフ. vector<pair<int, weight_t>> で隣接頂点とコストを表す
     * @param weight_inf 無限大の値. パスが存在しない場合のコスト
     * @return 始点から各頂点を一度だけ通って戻ってくる最小コスト
     * @note O(2^n * n^2)
    */
    template <typename weight_t>
    weight_t tsp_bitDP(int n, int start, const vector<vector<pair<int, weight_t>>> &graph, const weight_t weight_inf = ugilib::constants::INF<weight_t>) {
        const int num_states = (1 << n);
        // dp[これまでに取った都市集合. [0, 2^n-1]][現在地. [0, n-1]]
        vector<vector<weight_t>> dp(num_states, vector<weight_t>(n, weight_inf));
        dp[0][start] = 0;

        // 全状態についてDPする
        for (int i = 0; i < num_states; i++) {
            // 状態をビット表現する
            auto bits = ugilib::num_to_bits(i, n);
            // 今どの都市にいるか
            for (int j = 0; j < n; j++) {
                if (dp[i][j] == weight_inf) continue;  // この状態に辿り着かない場合
                // 次どの都市に行くか
                for (const auto [node, cost] : graph[j]) {
                    if (bits[node]) continue;  // 訪問済み
                    // 訪問する
                    bits[node] = true;
                    auto &dest = dp[ugilib::bits_to_num(bits)][node];
                    dest = min(dest, dp[i][j] + cost);
                    bits[node] = false;
                }
            }
        }

        return dp[num_states-1][start];  // 全状態訪問後にstartに戻って来る最小コスト
    }
    }  // namespace ugilib

Back to top page