2026-10-09
tour.cpp
#include <algorithm>
#include <print>
#include <vector>
int tour(const std::vector<std::vector<int>>& cost) {
const int n = cost.size(), full = (1 << n) - 1, inf = 1'000'000;
std::vector dp(1 << n, std::vector<int>(n, inf));
dp[1][0] = 0;
for (int mask = 1; mask <= full; ++mask)
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j) {
int& next = dp[mask | 1 << j][j];
next = std::min(next, dp[mask][i] + cost[i][j]);
}
int best = inf;
for (int i = 1; i < n; ++i) best = std::min(best, dp[full][i] + cost[i][0]);
return best;
}
int main() { std::println("{}", tour({{0, 1, 10}, {1, 0, 1}, {10, 1, 0}})); }
tour は、cost[i][j] を都市 i から j への移動の費用として、都市0から出発し、すべての都市をちょうど1回ずつ訪れて都市0に戻る巡回路の、最小の費用を返すつもりの関数です。main は3都市の費用表を渡すので、引数も標準入力も使いません。いまは 4 が出ますが、本来は 12 が出るはずです。
Answer
Wrong
for (int j = 0; j < n; ++j) {
int& next = dp[mask | 1 << j][j];
next = std::min(next, dp[mask][i] + cost[i][j]);
}
dp[mask][i] は、mask の都市を訪れて、いま都市 i にいるときの最小の費用です。内側のループは、行き先の j がすでに mask に入っているかを確かめていません。j が訪問済みなら mask | 1 << j は mask のままなので、訪れた集合は変わらずに現在地だけが j へ移ります。一度通った都市をもう一度通る経路が、ここで紛れ込みます。
この費用表では、都市0と2の間だけが10で、ほかの移動は1です。全都市を訪れた 0b111 の状態で、0→1→2と来た費用2の経路から訪問済みの都市1へ移る遷移が通り、dp[0b111][1] は3になります。最後に1から0へ戻る1を足した0→1→2→1→0の費用4が最小として返りますが、都市1を2回通るので、求める巡回路ではありません。
Right
for (int j = 0; j < n; ++j) {
if (mask >> j & 1) continue;
int& next = dp[mask | 1 << j][j];
next = std::min(next, dp[mask][i] + cost[i][j]);
}
行き先が mask に入っていれば飛ばすと、どの遷移も mask にビットを1つ足すので、どの都市も1回しか訪れなくなります。3都市の巡回路は0→1→2→0と0→2→1→0の2つで、どちらも都市0と2の間の10を通るので、最小の費用は 1 + 1 + 10 の12です1。
- 訪れた都市の集合と現在地を状態にするこの方法は、1962年に Bellman と、Held と Karp がそれぞれ発表したもので、Held-Karp アルゴリズムと呼ばれます。都市が
n個なら、時間はnの2乗と2のn乗の積に比例します。