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