Namaran

Code daily. Without assist.

2026-09-02

tour.cpp

#include <algorithm>
#include <cstdio>
#include <vector>

constexpr int n = 4;
constexpr int dist[n][n] = {{0, 1, 1, 1}, {1, 0, 1, 1}, {1, 1, 0, 9}, {1, 1, 9, 0}};
std::vector<int> memo(1 << n, -1);

int tour(unsigned visited, int at) {
    if (visited == (1u << n) - 1) return 0;
    int& best = memo[visited];
    if (best >= 0) return best;
    best = 1 << 30;
    for (int next = 0; next < n; ++next)
        if (!(visited >> next & 1))
            best = std::min(best, dist[at][next] + tour(visited | 1u << next, next));
    return best;
}

int main() { std::printf("%d\n", tour(1, 0)); }

tour は、頂点0から出発してすべての頂点を1回ずつ訪れる道順のうち、移動距離の合計が最小のものの距離を返すつもりの関数です。dist[i][j] は頂点 i と j の距離で、頂点2と3の間だけが9、ほかはすべて1です。0→2→1→3 と進めば合計3で済むので、本来は 3 と表示されるはずですが、いまは 11 と表示されます。

Answer

Wrong

std::vector<int> memo(1 << n, -1);

    int& best = memo[visited];

memo は訪れた頂点の集合 visited だけを添字にしていますが、残りの道のりは今いる頂点 at によっても変わります。最初にたどる 0→1→2 で、集合 {0, 1, 2} の残りは「2から3へ」の9として memo に入ります。あとで 0→2→1 と進んで同じ集合にたどり着いたとき、本当の残りは「1から3へ」の1なのに、memo から9が返ります。

こうして最短の 0→2→1→3 も 1 + 1 + 9 = 11 と見積もられ、ほかの道順も11より短くならないので、11 が表示されます。どの頂点で最初に集合が埋まるかは探索の順番で決まるので、dist を変えると、実際より短い値が返ることもあります。

Right

std::vector<std::vector<int>> memo(1 << n, std::vector<int>(n, -1));

    int& best = memo[visited][at];

訪れた頂点の集合と今いる頂点の組を添字にすれば、同じ添字を共有するのは、その先の進み方がまったく同じ場合だけになります。0→1→2 と 0→2→1 は別の添字になり、memo の大きさは 2n × n に増えます1。

  1. すべての頂点を1回ずつ訪れて出発点に戻る最短の道順を求める問題は、巡回セールスマン問題(traveling salesman problem)と呼ばれます。訪れた集合と今いる頂点の組を状態にするこの解き方は、1962年に Bellman と、Held と Karp がそれぞれ発表しました。