Day 105-Q3 | 双調巡回セールスマン問題（Bitonic TSP）

問題

平面上に$N$個の点$(x_i,y_i)$が与えられる（$x$座標はすべて相異なる）。すべての点を1回ずつ訪れて出発点に戻る双調（bitonic）な巡回路のうち、総移動距離が最小のものを求めよ。

「双調」とは、$x$座標が最小の点から出発して$x$座標が単調に増加し、最大の点に到達後は単調に減少して戻る形の巡回路を指す。一般のTSPはNP困難だが、この制約下では$O(N^2)$のDPで厳密な最適解が求まる（Supowit, Plaisted, Reingoldの手法・CLRS演習問題としても有名）。

入力形式

N
x_1 y_1
...
x_N y_N

制約

$2 \le N \le 2000$

$-10^4 \le x_i,y_i \le 10^4$（整数）

$x_i$はすべて相異なる

入出力例

入力例1

出力例1

12.10654957

絶対誤差または相対誤差$10^{-6}$以内であれば正解として扱う。

概念図: 2経路への分岐とフロンティア

ヒント（段階的開示）

ヒント1: 方向性

一般のTSPは$N\le15$程度でないとbitDPでも間に合わないが、この問題には「双調」という強い制約がある。$x$座標でソートし、巡回路を「左から右」「右から左」の2本の経路に分解して考えよう。

ヒント2: アプローチ

$x$座標昇順に$p_1,\dots,p_N$と並べる。新しく追加される点$p_{i+1}$は、その時点で「まだ経路の末端になっていて最も右にある点」の続きとしてしか追加できない。状態$dp[i][j]$（$i

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

dp[0][1] = dist(p[0], p[1])
for j in range(2, n):
    for i in range(0, j - 1):
        dp[i][j] = dp[i][j - 1] + dist(p[j - 1], p[j])
    dp[j - 1][j] = min(dp[k][j - 1] + dist(p[k], p[j])
                        for k in range(0, j - 1))
answer = min(dp[i][n - 1] + dist(p[i], p[n - 1])
             for i in range(0, n - 1))

模範解答 (Python)

import sys
import math


def solve():
    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))

    pts.sort()

    def dist(a, b):
        return math.hypot(pts[a][0] - pts[b][0], pts[a][1] - pts[b][1])

    if n == 2:
        print(f"{2 * dist(0, 1):.8f}")
        return

    INF = float('inf')
    dp = [[INF] * n for _ in range(n)]
    dp[0][1] = dist(0, 1)

    for j in range(2, n):
        for i in range(0, j - 1):
            dp[i][j] = dp[i][j - 1] + dist(j - 1, j)
        best = INF
        for k in range(0, j - 1):
            cand = dp[k][j - 1] + dist(k, j)
            if cand < best:
                best = cand
        dp[j - 1][j] = best

    ans = INF
    for i in range(0, n - 1):
        cand = dp[i][n - 1] + dist(i, n - 1)
        if cand < ans:
            ans = cand

    print(f"{ans:.8f}")


solve()

計算量: $O(N^2)$（状態数$O(N^2)$、各遷移を累積最小値で$O(1)$〜均し$O(1)$に抑制）。ランダム200ケースで全巡回路の総当たりとの一致を確認済み。

Step-by-Step 解説

1x座標ソートとフロンティア
左から順に処理すれば、常にどちらか一方の経路の末端は「これまでで最大index」になる。これが状態を$O(N^2)$に絞り込む鍵。

2状態dp[i][j]の定義
点$p_0..p_j$を2経路に割り当て、末端が$p_i$と$p_j$（$j$は最大index）のときの合計長最小値。

3遷移（ケースA・B）
ケースA: 末端$j-1$の経路を延長→`dp[i][j]=dp[i][j-1]+dist(j-1,j)`。ケースB: 末端$i$の経路を延長→`dp[j-1][j]=min_i dp[i][j-1]+dist(i,j)`。

4閉路として閉じる
最後の点まで処理したら末端$i$と$n-1$を直接結ぶ。すべての$i$についての最小値が答え。

よくあるミス

ミス	原因	正しい書き方
x座標でソートせずDPを組む	「フロンティアが常に最大index」の前提が崩れる	最初に必ずx座標でソートする
ケースBのminを毎回$O(N)$で愚直計算し全体$O(N^3)$	$N=2000$で$O(N^3)=8\times10^9$はTLE	累積最小値を保持しながら計算し$O(N^2)$に抑える
$n=2,3$の境界ケースを特別扱いしない	`dp[0][1]`基準のループが空になり未定義動作	境界を明示的に処理する（$n=2$は往復距離を直接出力）
出力の桁数を指定しない	許容誤差$10^{-6}$を満たせない可能性	`f"{ans:.8f}"`のように十分な桁数を指定する

次のステップ

発展: $x$座標に同値がある場合の tie-break 処理（$y$座標を第2キーにする）
発展: 「$k$本の単調経路に分解できる巡回路」への一般化DP
次回予告: Wavelet Tree（区間内での値の範囲カウントクエリ・$O(\log(\max A))$）

自己評価

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

Day 105-Q3 — 双調巡回セールスマン問題（Bitonic TSP）

問題