Day 100-Q5 | Held-Karpの1-木下界とLagrange緩和

問題

平面上に $N$ 個の都市がある。巡回セールスマン問題（TSP）の最適解そのものを厳密に求めるのは非現実的だが、「最適解はこれ以上ではない」という下界を高精度に求めることは、分枝限定法の枝刈りや近似解の精度評価に使える。

Held-Karpの1-木下界を、Lagrange緩和と劣勾配法で改善しながら求めよ。頂点$0$を除く頂点上の最小全域木に、頂点$0$から出る最も安い2辺を加えた「1-木」の重みは巡回路長の下界になる。各頂点にペナルティ $\lambda_i$ を課し、辺重みを $w(i,j)+\lambda_i+\lambda_j$ に変形してから1-木を計算すると、変形後の1-木重み $-\ 2\sum\lambda_i$ はどんな $\lambda$ でも合法な下界になる。次数が2から離れた頂点のペナルティを劣勾配法で更新し、下界を押し上げよ。

出力された下界が、真の最適巡回路長の 99%以上、かつ超えない（下界として正当）であれば正解とする特別採点方式で評価する。

入力形式

N
x_0 y_0
:
x_{N-1} y_{N-1}

制約

$3 \le N \le 200$

$0 \le x_i, y_i \le 1000$（整数）

座標はすべて相異なる

実行時間制限: 2秒

入出力例

入力例1（例）

出力例1（例）

28.822769

この例では真の最適巡回路長も28.822769（総当たり検証済み）。素の1-木下界（λ=0）は約26.616だが、Lagrange緩和後は大幅にタイトになる。

概念図

ヒント（段階的開示）

ヒント1: 方向性

任意の巡回路から1本の辺を除けば全域木の一種であり、1-木は「頂点0の次数がちょうど2」という制約を満たす最小の全域構造を含むため、巡回路長の下界になる。まずはこの性質を腑に落とすこと。

ヒント2: アプローチ

素の1-木下界はしばしば緩い。次数が2から離れた頂点にペナルティを課し使いにくく/使いやすくすることで、1-木をより巡回路に近い形へ誘導する（Lagrange緩和の双対問題を劣勾配法で解く）。任意の巡回路の変形後の長さは「元の長さ + 2Σλi」に等しいため、「変形後の1-木重み − 2Σλi」はどんなλでも合法な下界になる。

ヒント3: 誘導（コード骨格）

lam = [0.0] * n
best_bound = -math.inf
step = initial_step
for it in range(ITERS):
    w1tree, deg = min_one_tree(lam)
    bound = w1tree - 2 * sum(lam)
    best_bound = max(best_bound, bound)
    if all(d == 2 for d in deg):
        break
    t = step * (0.98 ** it)
    for i in range(n):
        lam[i] += t * (deg[i] - 2)

min_one_treeはPrim法（頂点0を除外して構築）+ 頂点0から最も安い2辺の追加で実装する。

模範解答 (Python)

import sys
import math


def solve():
    data = sys.stdin.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    xs, ys = [], []
    for _ in range(n):
        xs.append(float(data[idx])); idx += 1
        ys.append(float(data[idx])); idx += 1

    def dist(i, j):
        return math.hypot(xs[i] - xs[j], ys[i] - ys[j])

    def min_one_tree(lam):
        in_tree = [False] * n
        in_tree[0] = True
        key = [math.inf] * n
        parent = [-1] * n
        key[1] = 0.0
        for _ in range(n - 1):
            u = -1
            best = math.inf
            for v in range(1, n):
                if not in_tree[v] and key[v] < best:
                    best = key[v]
                    u = v
            if u == -1:
                break
            in_tree[u] = True
            for v in range(1, n):
                if not in_tree[v]:
                    wt = dist(u, v) + lam[u] + lam[v]
                    if wt < key[v]:
                        key[v] = wt
                        parent[v] = u
        deg = [0] * n
        total = 0.0
        for v in range(2, n):
            if parent[v] != -1:
                total += dist(parent[v], v) + lam[parent[v]] + lam[v]
                deg[parent[v]] += 1
                deg[v] += 1
        cand = sorted(range(1, n), key=lambda v: dist(0, v) + lam[0] + lam[v])
        e1, e2 = cand[0], cand[1]
        total += dist(0, e1) + lam[0] + lam[e1]
        total += dist(0, e2) + lam[0] + lam[e2]
        deg[0] += 2
        deg[e1] += 1
        deg[e2] += 1
        return total, deg

    lam = [0.0] * n
    w0, _ = min_one_tree(lam)
    step = w0 / (2 * n)
    best_bound = -math.inf
    ITERS = 200
    for it in range(ITERS):
        w1tree, deg = min_one_tree(lam)
        bound = w1tree - 2 * sum(lam)
        if bound > best_bound:
            best_bound = bound
        denom = sum((d - 2) ** 2 for d in deg)
        if denom == 0:
            break
        t = step * (0.98 ** it)
        for i in range(n):
            lam[i] += t * (deg[i] - 2)

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


solve()

計算量: 1反復あたり $O(N^2)$（Prim法MST）× 反復回数200 = $O(200N^2)$。$N\le200$で余裕を持って高速。

Step-by-Step 解説

11-木の構築（Prim法）
頂点0を除外し頂点1..N-1上のMSTを構築。辺重みは常に元の距離+λi+λj。

2頂点0の接続
頂点0から出る最安2辺を加え、頂点0の次数を必ず2にする。

3下界の計算
変形後の1-木重みから2Σλiを引いたものが合法な下界（弱双対性）。

4劣勾配によるペナルティ更新
次数が2より大きい頂点はペナルティを上げ、2未満なら下げる。全頂点の次数が2になれば最適解に一致。

5ステップ幅の減衰と反復終了
幾何減衰で序盤は大胆に、終盤は微調整。反復中の最良下界を記録して出力する。

よくあるミス

ミス	原因	正しい書き方
最終反復の下界をそのまま出力	劣勾配法は単調増加とは限らず途中で最良値を通り過ぎる	反復中の`best_bound`を保持し出力する
素の1-木下界（λ=0）だけで満足	Lagrange緩和を省略すると下界が緩すぎる	劣勾配法でλを反復更新しタイトにする
`2*sum(lam)`の引き算を忘れる	変形後の重みがそのまま下界だと誤解	変形後の1-木重みから必ず引く
ステップ幅を固定値のまま反復	減衰させないと終盤で振動し収束しない	幾何減衰または適応的ステップ幅を使う

次のステップ

発展: この下界とDay099-Q1の焼きなまし法による上界を突き合わせ、双対ギャップの縮まり方を実験する
発展: Lagrange緩和に分枝操作を組み合わせた分枝限定法（Branch and Bound with Held-Karp bound）
次回予告: Day101以降もMaster Levelのテーマローテーションを継続

自己評価

完全理解おおむね理解要復習

Day 100-Q5 — Held-Karpの1-木下界とLagrange緩和

問題