巡回セールスマン問題 (traveling salesman problem)
(include/emthrm/graph/traveling_salesman_problem.hpp)

• View this file on GitHub
• Last update: 2023-02-24 21:17:22+09:00
• Include: #include "emthrm/graph/traveling_salesman_problem.hpp"

重み付き有向グラフに対してコスト最小のハミルトン閉路を求める問題である。

時間計算量

$O(2^{\lvert V \rvert} {\lvert V \rvert}^2)$

仕様

Held–Karp algorithm

名前	戻り値
template <typename CostType> CostType traveling_salesman_problem(const std::vector<std::vector<Edge<CostType>>>& graph, const CostType inf = std::numeric_limits<CostType>::max());	グラフ $\mathrm{graph}$ の巡回セールスマン問題の解のコスト。ただし解が存在しないときは $\infty$ を返す。

参考文献

Held–Karp algorithm

• Richard Bellman: Dynamic Programming Treatment of the Travelling Salesman Problem, Journal of the ACM, Vol. 9, No. 1, pp. 61–63 (1962). https://doi.org/10.1145/321105.321111
• 秋葉拓哉，岩田陽一，北川宜稔：プログラミングコンテストチャレンジブック [第2版]，pp.173-175，マイナビ出版（2012）

TODO

• 最短のハミルトン路
  • https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%9F%E3%83%AB%E3%83%88%E3%83%B3%E8%B7%AF
  • https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%9F%E3%83%AB%E3%83%88%E3%83%B3%E9%96%89%E8%B7%AF%E5%95%8F%E9%A1%8C
  • http://www.prefield.com/algorithm/graph/shortest_hamilton_path.html
  • https://github.com/primenumber/ProconLib/blob/master/Graph/ShortestHamiltonPath.cpp
  • https://github.com/spaghetti-source/algorithm/blob/master/graph/hamilton_cycle_ore.cc

Submissons

• Held–Karp algorithm

Depends on

• 辺 (include/emthrm/graph/edge.hpp)

Verified with

• グラフ/巡回セールスマン問題 (test/graph/traveling_salesman_problem.test.cpp)

Code

#ifndef EMTHRM_GRAPH_TRAVELING_SALESMAN_PROBLEM_HPP_
#define EMTHRM_GRAPH_TRAVELING_SALESMAN_PROBLEM_HPP_

#include <algorithm>
#include <limits>
#include <numeric>
#include <vector>

#include "emthrm/graph/edge.hpp"

namespace emthrm {

template <typename CostType>
CostType traveling_salesman_problem(
    const std::vector<std::vector<Edge<CostType>>>& graph,
    const CostType inf = std::numeric_limits<CostType>::max()) {
  const int n = graph.size();
  if (n == 1) [[unlikely]] return 0;
  std::vector<std::vector<CostType>> dp(1 << n, std::vector<CostType>(n, inf));
  dp[1][0] = 0;
  for (int i = 1; i < (1 << n); ++i) {
    for (int j = 0; j < n; ++j) {
      if (dp[i][j] == inf) continue;
      for (const Edge<CostType>& e : graph[j]) {
        if (i >> e.dst & 1) continue;
        dp[i | (1 << e.dst)][e.dst] =
            std::min(dp[i | (1 << e.dst)][e.dst], dp[i][j] + e.cost);
      }
    }
  }
  CostType res = inf;
  for (int j = 1; j < n; ++j) {
    if (dp.back()[j] == inf) continue;
    for (const Edge<CostType>& e : graph[j]) {
      if (e.dst == 0) res = std::min(res, dp.back()[j] + e.cost);
    }
  }
  return res;
}

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_TRAVELING_SALESMAN_PROBLEM_HPP_

#line 1 "include/emthrm/graph/traveling_salesman_problem.hpp"



#include <algorithm>
#include <limits>
#include <numeric>
#include <vector>

#line 1 "include/emthrm/graph/edge.hpp"
/**
 * @title 辺
 */

#ifndef EMTHRM_GRAPH_EDGE_HPP_
#define EMTHRM_GRAPH_EDGE_HPP_

#include <compare>

namespace emthrm {

template <typename CostType>
struct Edge {
  CostType cost;
  int src, dst;

  explicit Edge(const int src, const int dst, const CostType cost = 0)
      : cost(cost), src(src), dst(dst) {}

  auto operator<=>(const Edge& x) const = default;
};

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_EDGE_HPP_
#line 10 "include/emthrm/graph/traveling_salesman_problem.hpp"

namespace emthrm {

template <typename CostType>
CostType traveling_salesman_problem(
    const std::vector<std::vector<Edge<CostType>>>& graph,
    const CostType inf = std::numeric_limits<CostType>::max()) {
  const int n = graph.size();
  if (n == 1) [[unlikely]] return 0;
  std::vector<std::vector<CostType>> dp(1 << n, std::vector<CostType>(n, inf));
  dp[1][0] = 0;
  for (int i = 1; i < (1 << n); ++i) {
    for (int j = 0; j < n; ++j) {
      if (dp[i][j] == inf) continue;
      for (const Edge<CostType>& e : graph[j]) {
        if (i >> e.dst & 1) continue;
        dp[i | (1 << e.dst)][e.dst] =
            std::min(dp[i | (1 << e.dst)][e.dst], dp[i][j] + e.cost);
      }
    }
  }
  CostType res = inf;
  for (int j = 1; j < n; ++j) {
    if (dp.back()[j] == inf) continue;
    for (const Edge<CostType>& e : graph[j]) {
      if (e.dst == 0) res = std::min(res, dp.back()[j] + e.cost);
    }
  }
  return res;
}

}  // namespace emthrm

Back to top page