Day 145-Q1 — Christofidesアルゴリズム（TSP 1.5-近似・MST+奇数次数頂点の最小重みマッチング）

問題

$N$ 個の点が2次元平面上に与えられる（各点間の距離はユークリッド距離。三角不等式を満たすためChristofidesアルゴリズムの前提条件を満たす）。

Christofidesアルゴリズムは次の手順で巡回路の上界を構成する。

1. 全点を頂点とする完全グラフ上で最小全域木（MST）を求める。
2. MST上で次数が奇数である頂点集合 $O$ を求める（握手補題より $|O|$ は必ず偶数）。
3. $O$ の頂点だけからなる完全グラフ上で、最小重み完全マッチング $M$ を求める。
4. MST辺と $M$ の辺を合わせると全頂点が偶数次数になりオイラー閉路が存在する。重複訪問頂点をショートカットすると、三角不等式によりコストが増えないハミルトン閉路を得る。

本問で求めるもの: 「MSTの重み + 奇数次数頂点集合上の最小重み完全マッチングの重み」（＝ Christofidesアルゴリズムが保証する巡回路長の上界値）を求めよ。複数の最小重み完全マッチングが存在してもその総重量は一意に定まるため、答えは一意である。

入力形式

N
x_1 y_1
:
x_N y_N

制約

入出力例

4
0 0
0 1
1 0
1 1

4.000000

単位正方形の4点。MSTは3辺（重み計3）、残る奇数次数2点間のマッチング（重み1）を加えて計4。

概念図：MST + マッチングによる偶数次数化

ヒント（段階的開示）

def min_weight_perfect_matching(vertices, dist):
    k = len(vertices)
    FULL = (1 << k) - 1
    dp = [float('inf')] * (1 << k)
    dp[0] = 0.0
    for mask in range(1 << k):
        if dp[mask] == float('inf'):
            continue
        i = 0
        while mask & (1 << i):
            i += 1
        if i >= k:
            continue
        for j in range(i + 1, k):
            if not (mask & (1 << j)):
                nmask = mask | (1 << i) | (1 << j)
                w = dist[vertices[i]][vertices[j]]
                dp[nmask] = min(dp[nmask], dp[mask] + w)
    return dp[FULL]

模範解答 (Python)

📋 コピーimport sys
import math

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

    dist = [[0.0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            dist[i][j] = math.hypot(pts[i][0] - pts[j][0], pts[i][1] - pts[j][1])

    # --- Step 1: Prim法によるMST構築 ---
    INF = float('inf')
    in_mst = [False] * N
    min_edge = [INF] * N
    parent = [-1] * N
    min_edge[0] = 0.0
    mst_weight = 0.0
    degree = [0] * N
    for _ in range(N):
        u = -1
        for v in range(N):
            if not in_mst[v] and (u == -1 or min_edge[v] < min_edge[u]):
                u = v
        in_mst[u] = True
        mst_weight += min_edge[u]
        if parent[u] != -1:
            degree[u] += 1
            degree[parent[u]] += 1
        for v in range(N):
            if not in_mst[v] and dist[u][v] < min_edge[v]:
                min_edge[v] = dist[u][v]
                parent[v] = u

    # --- Step 2: 奇数次数頂点の抽出 ---
    odd_vertices = [v for v in range(N) if degree[v] % 2 == 1]
    k = len(odd_vertices)

    # --- Step 3: ビットマスクDPによる最小重み完全マッチング ---
    if k == 0:
        matching_weight = 0.0
    else:
        FULL = (1 << k) - 1
        dp = [INF] * (1 << k)
        dp[0] = 0.0
        for mask in range(1 << k):
            if dp[mask] == INF:
                continue
            i = 0
            while mask & (1 << i):
                i += 1
            if i >= k:
                continue
            for j in range(i + 1, k):
                if not (mask & (1 << j)):
                    nmask = mask | (1 << i) | (1 << j)
                    w = dist[odd_vertices[i]][odd_vertices[j]]
                    nd = dp[mask] + w
                    if nd < dp[nmask]:
                        dp[nmask] = nd
        matching_weight = dp[FULL]

    print(f"{mst_weight + matching_weight:.6f}")

main()

Step-by-Step 解説

よくあるミス

次のステップ

• 発展: 実際にオイラー閉路を構成し（Hierholzerのアルゴリズム）、ショートカットして具体的な巡回路を出力せよ。
• 次回予告: Vizingの定理と辺彩色（Δ+1色によるバックトラック構成）

自己評価

自分の回答

気づき・メモ