Day 098-Q3 — MST-doubling 2近似法（巡回セールスマン問題の近似アルゴリズム）

2026-07-21 赤色 Master / Phase 8+ ★★★★★★★★★ Approximation Algorithm

問題

2次元平面上に $N$ 個の点（三角不等式を満たすユークリッド距離を辺重みとする）が与えられる。以下のアルゴリズムに従って巡回路を構築し、その総距離を出力せよ。

  1. 完全グラフに対し Kruskal法 で最小全域木（MST）を構築する。辺は $(重み, u, v)$ の辞書式順（0-indexed）でソートする。
  2. MSTの各頂点の隣接頂点リストを頂点番号の昇順にソートする。
  3. 頂点0を根として、隣接頂点を番号昇順に訪れるDFS行きがけ順（preorder）で頂点を並べる。
  4. その順序で頂点を巡り、最後に頂点0へ戻る閉路の総距離を計算する。

これは「MSTを2重化してオイラー閉路を作り、既訪問頂点をショートカットする」操作と数学的に同値で、三角不等式のもとで最適解の高々2倍に収まることが保証される。

入力形式

N
x_1 y_1
:
x_N y_N

制約

$2 \le N \le 2000$
$0 \le x_i, y_i \le 10^4$（整数）
誤差 $10^{-6}$ 以内で正解

入出力例

入力例1

4
0 0
0 2
2 2
2 0

出力例1

8.000000

正方形の4頂点。MSTは辺(0,1),(0,3),(1,2)（タイブレークにより決定）で、DFS preorderは 0→1→2→3。周を1周すると 2+2+2+2=8（正方形の周長と一致）。

概念図

MST → 2重化 → オイラー閉路 → ショートカット P0 P1 P2 P3 MST（木構造・3辺） 0 1 2 3 DFS preorder: 0→1→2→3→0 既訪問頂点をスキップするショートカットは三角不等式により経路長を増やさない → ツアー長 ≤ 2×MST重み ≤ 2×OPT（最適解）

ヒント（段階的開示）

ヒント1: 方向性
巡回セールスマン問題の厳密解は $NP$ 困難だが、「距離が三角不等式を満たす」制約があれば多項式時間で最適解の2倍以内の解を作れる。最小全域木の総重みが最適巡回路長の下界になっている、という関係に着目せよ。
ヒント2: アプローチ
MSTの各辺を2本ずつ使うと全頂点の次数が偶数になり、オイラー閉路が存在する。このオイラー閉路をたどりながら「すでに訪れた頂点はスキップして次の未訪問頂点へ直接進む」ことでハミルトン閉路が得られる。三角不等式によりこのショートカットは経路長を増やさない。実装上はDFSの行きがけ順（preorder）で頂点を並べるだけで同じ結果になる。
ヒント3: 誘導（コード骨格） 
edges.sort(key=lambda e: (e[0], e[1], e[2]))  # (重み, u, v)
# Kruskal法でMST構築（Union-Find使用）
for a in adj:
    a.sort()

order = []
visited = [False] * n

def dfs(u):
    visited[u] = True
    order.append(u)
    for v in adj[u]:
        if not visited[v]:
            dfs(v)

dfs(0)
# order を順に結び、最後に order[0] へ戻る閉路の総距離を計算する

模範解答 (Python)

import sys
import math


def solve():
    data = sys.stdin.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    pts = []
    for _ in range(n):
        x = int(data[idx]); y = int(data[idx + 1]); idx += 2
        pts.append((x, y))

    def dist(i, j):
        dx = pts[i][0] - pts[j][0]
        dy = pts[i][1] - pts[j][1]
        return math.hypot(dx, dy)

    edges = []
    for i in range(n):
        for j in range(i + 1, n):
            edges.append((dist(i, j), i, j))
    edges.sort(key=lambda e: (e[0], e[1], e[2]))

    parent = list(range(n))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    adj = [[] for _ in range(n)]
    used = 0
    for w, u, v in edges:
        ru, rv = find(u), find(v)
        if ru != rv:
            parent[ru] = rv
            adj[u].append(v)
            adj[v].append(u)
            used += 1
            if used == n - 1:
                break

    for a in adj:
        a.sort()

    visited = [False] * n
    order = []
    sys.setrecursionlimit(10000)

    def dfs(u):
        visited[u] = True
        order.append(u)
        for v in adj[u]:
            if not visited[v]:
                dfs(v)

    dfs(0)

    total = 0.0
    for i in range(n):
        u = order[i]
        v = order[(i + 1) % n]
        total += dist(u, v)

    print(f"{total:.6f}")


solve()
計算量: MST構築 $O(N^2\log N)$（全点対辺の生成とソート）、DFS $O(N)$。全体 $O(N^2\log N)$。

Step-by-Step 解説

1最小全域木の構築
全点対の距離を辺として列挙し、Kruskal法でMSTを求める。$(重み,u,v)$ でソートし結果を一意に定める。
2隣接リストの整備
木としての隣接頂点リストを構築し番号順にソートする。DFSの走査順序を一意に定める。
3DFS行きがけ順の取得
頂点0からDFSし訪れた順に記録（preorder）。2重化MSTのオイラー閉路をショートカットした経路と一致する。
4巡回路長の計算
preorder順に頂点を結び、最後に最初の頂点へ戻る閉路の総距離を計算する。
5近似保証の直感
$OPT \ge MST$ であり、2重化MSTの総重みは $2\cdot MST$。三角不等式によりショートカットしても経路長は増えないため、得られる巡回路長は $2\cdot MST \le 2\cdot OPT$ に収まる。

よくあるミス

ミス原因正しい書き方
同じ重みの辺のタイブレークを決めない実装依存でMSTの形が変わり出力が再現できない辺を $(重み,u,v)$ の辞書式順でソートし一意に定める
DFS訪問順を隣接リストの挿入順のまま使う頂点番号順でなくグラフ構築順に依存し非決定的になる各頂点の隣接リストを必ずソートしてからDFSする
三角不等式を満たさない距離に適用2近似の保証は三角不等式が前提適用条件を確認する
大きい $N$ で全点対 $O(N^2)$ の辺生成がボトルネック$N$ が大きいと重い$N\le2000$程度に留めるかPrim法+近傍探索で高速化する

次のステップ

  • 発展: Christofides法（奇数次数頂点の最小重み完全マッチングを追加し $1.5$ 近似に改善）
  • 発展: Held-Karp下界（1-tree緩和・ラグランジュ双対によるTSPの下界計算）
  • 次回予告: Capacity Scaling法（最大流のスケーリング高速化アルゴリズム）

自己評価

自分の回答

気づき・メモ