Day 099-Q1 | 焼きなまし法（Simulated Annealing）

問題

平面上に $N$ 個の都市がある。都市 $i$ の座標は $(x_i, y_i)$ である。すべての都市をちょうど1回ずつ訪れて出発点に戻る巡回路（閉路）のうち、総移動距離（各都市間はユークリッド距離）が最小になるものを求めたい（巡回セールスマン問題, TSP）。

$N$ が大きい場合、厳密な最適解を多項式時間で求めるアルゴリズムは知られていない（NP困難）。そこで 焼きなまし法（Simulated Annealing, SA） を用いて、実行時間内でできるだけ短い巡回路を探索せよ。

出力された巡回路の総距離が、既知の最良解の 105%以内 であれば正解とする特別採点（スペシャルジャッジ）方式で評価する。

入力形式

N
x_1 y_1
x_2 y_2
:
x_N y_N

制約

$2 \le N \le 200$

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

座標はすべて相異なる

実行時間制限: 2秒

入出力例

入力例1

出力例1（例）

1 2 3 4

正方形の4頂点を周回するのが最適で、総距離は $10+10+10+10=40$。出力は訪問順（1-indexedの都市番号、末尾から先頭へ戻る）で、同じ長さになる開始点違い・回転・反転もすべて正解。

概念図

ヒント（段階的開示）

ヒント1: 方向性

「今の解を少しだけ変形して改善する」操作を繰り返すだけでは、局所最適解に捕まってすぐ止まってしまう。ときどきあえて悪化する変形も受け入れることで、局所最適から脱出できないか考えよ。

ヒント2: アプローチ

「温度 $T$」を用意し、改善量（悪化量）を $\Delta$ としたとき確率 $\min(1, e^{-\Delta/T})$ で遷移を受理する（メトロポリス基準）。$T$ が高いうちは広く探索し、徐々に下げる（冷却スケジュール）ことで最終的には改善のみを受理するようになる。近傍操作にはTSP定番の2-opt（区間反転）を使い、変化する2辺だけで $\Delta$ を $O(1)$ 計算する。

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

i, j = sorted(random.sample(range(n), 2))
a, b = order[i - 1], order[i]
c, d = order[j], order[(j + 1) % n]
delta = (dist(a, c) + dist(b, d)) - (dist(a, b) + dist(c, d))

if delta < 0 or random.random() < math.exp(-delta / T):
    order[i:j + 1] = order[i:j + 1][::-1]
    cur_len += delta
T *= ALPHA

i == 0 and j == n - 1 のときは区間が巡回路全体になり a == c となる退化ケースなので、その反復はスキップする。

模範解答 (Python)

import sys
import math
import random
import time


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

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

    def tour_length(order):
        return sum(dist(order[k], order[(k + 1) % n]) for k in range(n))

    random.seed(1)
    order = list(range(n))
    random.shuffle(order)
    cur_len = tour_length(order)
    best_order = order[:]
    best_len = cur_len

    T = 100.0
    ALPHA = 0.9999
    TIME_LIMIT = 1.8
    start = time.time()

    if n >= 4:
        while time.time() - start < TIME_LIMIT:
            i, j = sorted(random.sample(range(n), 2))
            if i == 0 and j == n - 1:
                continue
            a, b = order[i - 1], order[i]
            c, d = order[j], order[(j + 1) % n]
            delta = (dist(a, c) + dist(b, d)) - (dist(a, b) + dist(c, d))
            if delta < 0 or random.random() < math.exp(-delta / T):
                order[i:j + 1] = order[i:j + 1][::-1]
                cur_len += delta
                if cur_len < best_len:
                    best_len = cur_len
                    best_order = order[:]
            T = max(T * ALPHA, 1e-6)

    print(' '.join(str(v + 1) for v in best_order))


solve()

計算量: 1反復あたり $O(1)$（差分計算）。実行時間制限いっぱいまで反復回数を最大化するのが実践的な戦略。

Step-by-Step 解説

1初期解の生成
都市の訪問順をランダムにシャッフルして初期解とする。

22-opt近傍と差分計算
反転で変わるのは境界の2辺だけなので $\Delta$ を $O(1)$ で計算できる。

3メトロポリス基準
$\Delta<0$なら無条件受理、$\Delta\ge0$でも確率 $e^{-\Delta/T}$ で受理し局所最適を脱出する。

4冷却スケジュール
T *= ALPHA（例: 0.9999）で徐々に温度を下げ、改善のみ受理する通常の局所探索に近づける。

5実行時間管理とベスト解保持
現在解が必ずしも最良とは限らないため best_order を別に保持し、最終出力に使う。

よくあるミス

ミス	原因	正しい書き方
反転のたびに全体長さをフル計算	差分計算を使わず反復回数が激減する	境界2辺だけで $\Delta$ を $O(1)$ で求める
最終出力に現在解 `order` を使う	現在解が必ずしも最良とは限らない	別途 `best_order` を保持しそれを出力する
温度を線形に減らす・急激に0へ	冷却が速すぎて局所最適に早期収束	指数的な冷却（`T *= ALPHA`、$\alpha$は1に近い値）を使う
`i==0, j==n-1`の退化ケースを未考慮	`a==c`となり$\Delta$計算が壊れる	このケースは反復をスキップする

次のステップ

発展: 2-optに加えてOr-opt近傍を混ぜる、あるいはLin-Kernighan法へ発展させる
次回予告: Myers' Bit-Vector Algorithm（編集距離のビット並列高速化）

自己評価

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

Day 099-Q1 — 焼きなまし法（Simulated Annealing・巡回セールスマン近似）

問題