概要

配送センター（届け先 \(1\)）を出発し、\(N\) 箇所すべての届け先をちょうど1回ずつ訪問して配送センターに戻る巡回路のうち、燃料コスト（ユークリッド距離の二乗の総和）が最小となるものを求める、いわゆる巡回セールスマン問題（TSP）です。

考察

問題の本質

この問題は、\(N\) 頂点の完全グラフ上で、頂点 \(1\) を始点・終点とするハミルトン閉路（すべての頂点をちょうど1回ずつ通る閉路）のうち、辺の重みの合計が最小のものを求める問題です。

素朴なアプローチとその限界

最も単純な方法は、\(N\) 個の届け先を訪問する全順列を列挙することです。しかし、順列の数は \((N-1)!\) 通りあり、\(N = 16\) のとき \((16-1)! = 15! \approx 1.3 \times 10^{12}\) となり、到底間に合いません。

どう解決するか

訪問順序の全列挙では状態が爆発しますが、「どの届け先を訪問済みか（集合）」と「最後にどの届け先にいるか」だけを記録すれば、途中の訪問順序の詳細は不要です。これがビットマスクDP（ビットDP）の発想です。

\(N \leq 16\) なので、訪問済み集合を \(N\) ビットの整数で表現でき、状態数は \(2^N \times N\) で高々 \(2^{16} \times 16 = 1{,}048{,}576\) と十分小さくなります。

アルゴリズム

1. コスト行列の前計算

すべての届け先ペア \((i, j)\) について、移動コスト \((X_i - X_j)^2 + (Y_i - Y_j)^2\) を事前に計算しておきます。

2. ビットマスクDPの定義

• 状態: \(dp[S][u]\) = 「訪問済みの届け先の集合が \(S\)（ビットマスク）で、最後に訪問した届け先が \(u\) であるときの、最小コスト」
• 初期状態: \(dp[\{0\}][0] = 0\)（届け先 \(1\)、つまり0-indexedで頂点 \(0\) にいて、コストは \(0\)）
• 遷移: 集合 \(S\) にいて頂点 \(u\) にいる状態から、まだ訪問していない頂点 \(v\)（\(v \notin S\)）へ移動する： $\(dp[S \cup \{v\}][v] = \min(dp[S \cup \{v\}][v],\; dp[S][u] + \text{dist}[u][v])\)$

3. 答えの計算

すべての頂点を訪問した状態（\(S = \{0, 1, \ldots, N-1\}\)、ビットマスクで \(2^N - 1\)）から、配送センター（頂点 \(0\)）に戻るコストを加えた最小値が答えです： $\(\text{ans} = \min_{u=0}^{N-1} \left( dp[2^N - 1][u] + \text{dist}[u][0] \right)\)$

具体例

\(N = 3\)、頂点 \(0, 1, 2\) がある場合： - \(dp[001][0] = 0\)（頂点0のみ訪問、頂点0にいる） - \(dp[011][1] = \text{dist}[0][1]\)（頂点0→1と移動） - \(dp[111][2] = \text{dist}[0][1] + \text{dist}[1][2]\)（頂点0→1→2と移動） - 最後に \(dp[111][2] + \text{dist}[2][0]\) で頂点0に戻る

計算量

• 時間計算量: \(O(2^N \times N^2)\)（各状態 \(2^N \times N\) に対して、遷移先 \(N\) 個を試す）
  • \(N = 16\) のとき約 \(2^{16} \times 16^2 \approx 1.7 \times 10^7\) で十分高速
• 空間計算量: \(O(2^N \times N)\)（DPテーブルのサイズ）

実装のポイント

• 届け先は1-indexedで与えられますが、コード内では 0-indexed で扱い、配送センターを頂点 \(0\) としています。

• ビットマスク \(S\) のうち、頂点 \(0\)（配送センター）を含まない状態はスキップすることで無駄な計算を省いています（if not (S & 1): continue）。

• DPの初期値を INF（無限大）に設定し、到達不可能な状態を自然に除外しています。

• コスト行列を事前計算しておくことで、DP中の距離計算を \(O(1)\) にしています。

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    coords = []
    for i in range(N):
        x = int(input_data[idx]); idx += 1
        y = int(input_data[idx]); idx += 1
        coords.append((x, y))
    
    # Precompute distance (cost) matrix
    dist = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            dx = coords[i][0] - coords[j][0]
            dy = coords[i][1] - coords[j][1]
            dist[i][j] = dx * dx + dy * dy
    
    # TSP with bitmask DP
    # dp[S][i] = minimum cost to visit exactly the set S of nodes, ending at node i
    # Start at node 0 (1-indexed node 1)
    INF = float('inf')
    full = 1 << N
    dp = [[INF] * N for _ in range(full)]
    dp[1][0] = 0  # Start at node 0, visited set = {0}
    
    for S in range(1, full):
        if not (S & 1):
            continue  # Must include node 0
        for u in range(N):
            if dp[S][u] == INF:
                continue
            if not (S >> u & 1):
                continue
            for v in range(N):
                if S >> v & 1:
                    continue
                nS = S | (1 << v)
                cost = dp[S][u] + dist[u][v]
                if cost < dp[nS][v]:
                    dp[nS][v] = cost
    
    # Answer: visit all nodes and return to node 0
    full_mask = full - 1
    ans = INF
    for u in range(N):
        if dp[full_mask][u] + dist[u][0] < ans:
            ans = dp[full_mask][u] + dist[u][0]
    
    print(ans)

main()

---

この解説は claude4.6opus-thinking によって生成されました。