Day 150-Q4 — タブーサーチ（Tabu Search・巡回セールスマン問題の2-opt近傍探索）

2026-09-11 赤色 Master / Phase 8+ ★★★★★★★★★ 直近の操作を一定期間禁止し、改悪も受理することで局所最適から脱出する

問題

$N$都市の巡回セールスマン問題。2都市間の距離はマンハッタン距離。初期巡回路が与えられる。以下のタブーサーチの手順を$K$回反復し、見つかったベスト解の長さと巡回路を出力せよ。

2-optムーブ

インデックス$i,j$（$1\le i<j\le N-1$、都市0は固定）に対し区間[i,j]を反転する操作。

各反復の手順

  1. 全ムーブ$(i,j)$を辞書式順で列挙し適用後の巡回路長を計算。
  2. タブー中のムーブは原則不可。ただし適用後の長さがこれまでのベストより真に短いなら例外的に許可（アスピレーション基準）。
  3. 使用可能な中から最小長を選ぶ（同着は辞書式最小の$(i,j)$）。
  4. 必ず適用（改善していなくても）。
  5. タブーリストの残り期間を1減らし、0なら削除。その後選んだムーブをタブー期間$T$で追加。
  6. ベストより短ければ更新。

入力形式

N T K
x_1 y_1
:
x_N y_N
p_1 ... p_N

制約

$3 \le N \le 8$
$1 \le T \le 5$
$1 \le K \le 10$
座標は $0$〜$20$

入出力例

入力例1

5 2 5
0 0
3 0
3 4
0 4
1 2
0 1 4 2 3

出力例1

16
0 4 3 2 1

概念図：巡回路長の推移（局所最適からの脱出）

反復ごとの巡回路長（改悪を経由して大域最適16へ到達） 18 16 best=16 初期18 it1: 18 it2: 16★ it3: 16 it4: 18 it5: 18 赤=改悪(タブーで改善手が塞がれ受理した非改善ムーブ)

ヒント（段階的開示）

ヒント1（方向性）

初期巡回路 0 1 4 2 3 は、実はどの1回の2-optムーブを適用しても改善しない局所最適に陥っている。改善する手だけを選ぶ通常の山登り法ならここで探索が完全に停止する。

ヒント2（アプローチ）

「改悪を受理する」だけでは同じ操作を繰り返して元に戻ってしまう恐れがある。直前に使った操作をしばらく禁止リストに入れることで、同じ場所の行き来を防ぐ。ただしベスト更新が確定するムーブだけは禁止を無視できる例外（アスピレーション基準）を設ける。

ヒント3（誘導） 
def two_opt(tour, i, j):
    return tour[:i] + list(reversed(tour[i:j+1])) + tour[j+1:]

tabu = {}
current = initial_tour[:]
best = initial_tour[:]
best_len = tour_length(initial_tour)

for it in range(K):
    candidates = []
    for i in range(1, N-1):
        for j in range(i+1, N):
            nt = two_opt(current, i, j)
            candidates.append((i, j, nt, tour_length(nt)))
    allowed = [c for c in candidates
               if (c[0], c[1]) not in tabu or c[3] < best_len]
    allowed.sort(key=lambda c: (c[3], c[0], c[1]))

模範解答 (Python)

import sys


def main():
    data = sys.stdin.read().split()
    ptr = 0
    n = int(data[ptr]); tenure = int(data[ptr + 1]); k_iter = int(data[ptr + 2]); ptr += 3
    coords = []
    for _ in range(n):
        x = int(data[ptr]); y = int(data[ptr + 1]); ptr += 2
        coords.append((x, y))
    tour0 = [int(data[ptr + i]) for i in range(n)]
    ptr += n

    def dist(a, b):
        return abs(coords[a][0] - coords[b][0]) + abs(coords[a][1] - coords[b][1])

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

    def two_opt(t, i, j):
        return t[:i] + list(reversed(t[i:j + 1])) + t[j + 1:]

    current = tour0[:]
    best = tour0[:]
    best_len = tour_length(tour0)
    tabu = {}

    for _ in range(k_iter):
        candidates = []
        for i in range(1, n - 1):
            for j in range(i + 1, n):
                nt = two_opt(current, i, j)
                nl = tour_length(nt)
                candidates.append((i, j, nt, nl))
        allowed = [c for c in candidates if (c[0], c[1]) not in tabu or c[3] < best_len]
        allowed.sort(key=lambda c: (c[3], c[0], c[1]))
        i, j, nt, nl = allowed[0]
        current = nt
        for key in list(tabu.keys()):
            tabu[key] -= 1
            if tabu[key] <= 0:
                del tabu[key]
        tabu[(i, j)] = tenure
        if nl < best_len:
            best_len = nl
            best = nt[:]

    print(best_len)
    print(" ".join(map(str, best)))


main()

Step-by-Step 解説

1初期解が局所最適
初期巡回路(長さ18)に対し6通りの2-optムーブを全て試しても、どれも18以上にしかならない。
2タブーリストが空のうちに改悪を受理
反復1では最小長18(同点)で辞書式最小の$(1,2)$が選ばれ、`0 4 1 2 3`(長さ18)へ移動。タブーに$(1,2):2$が追加。
3改悪を経由して大域最適に到達
反復2で$(2,4)$を適用すると`0 4 3 2 1`(長さ16)が得られベストを更新。$(1,2)$がタブーでも$(2,4)$はタブーでないため通常通り選ばれる。
4反復を続けても結果は変わらない
$K=5$回の反復終了時点でのベスト解は反復2で見つかった長さ16のまま(この配置の大域最適値はブルートフォースで16と確認できる)。

よくあるミス

ミス原因正しい書き方
改善するムーブが無いとき探索を止めてしまう山登り法の感覚を引きずるタブーサーチは改悪でも必ず1手選び$K$回固定反復する
アスピレーション基準を「現在解より良ければ」で判定比較対象の取り違え比較対象はベスト解の長さであり直前の現在解ではない
タブー期間の減算を新規追加の前に行わない更新順序の誤り既存エントリを先に減算・削除し、その後今回のムーブを期間$T$で追加
反転範囲に両端（都市0や$N-1$）を含めてしまう「全体を自由に変形してよい」と誤解定義通り$1\le i<j\le N-1$に限定し先頭都市は含めない
タブー判定を巡回路全体で行ってしまうキーの取り違え本問はムーブ$(i,j)$単位でタブー管理する

次のステップ

  • 発展: 本問は全候補から最良の1手を選ぶ最良改善方式だが、候補をランダムに一部だけサンプリングする近傍サイズ制限を導入すると、都市数が多い場合の1反復あたりの計算量を抑えられる。
  • 次回予告: 山登り法（Hill Climbing・グラフ彩色の局所改善）

自己評価

自分の回答

気づき・メモ