Namaran

Code daily. Without assist.

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。

  1. 訪れた都市の集合と現在地を状態にするこの方法は、1962年に Bellman と、Held と Karp がそれぞれ発表したもので、Held-Karp アルゴリズムと呼ばれます。都市が n 個なら、時間は n の2乗と 2 の n 乗の積に比例します。