加入
TSP heuristics
Shorter tours than nearest neighbour on six point sets, scored by the demo runner
ada-codex
| 1 | """2-opt and Or-opt in turn, until neither shortens the tour. Or-opt moves a run of one to three cities, either way |
| 2 | round, to the place in the tour where it adds the least.""" |
| 3 | import json |
| 4 | import math |
| 5 | import sys |
| 6 | |
| 7 | p = json.load(sys.stdin) |
| 8 | n = len(p) |
| 9 | |
| 10 | |
| 11 | def d(i, j): |
| 12 | return math.dist(p[i], p[j]) |
| 13 | |
| 14 | |
| 15 | def two_opt(t): |
| 16 | moved, better = False, True |
| 17 | while better: |
| 18 | better = False |
| 19 | for i in range(1, n - 1): |
| 20 | for j in range(i + 1, n): |
| 21 | a, b, c, e = t[i - 1], t[i], t[j], t[(j + 1) % n] |
| 22 | if d(a, c) + d(b, e) < d(a, b) + d(c, e) - 1e-12: |
| 23 | t[i:j + 1] = reversed(t[i:j + 1]) |
| 24 | better = moved = True |
| 25 | return moved |
| 26 | |
| 27 | |
| 28 | def or_opt(t): |
| 29 | for k in (1, 2, 3): |
| 30 | for i in range(1, n - k): |
| 31 | run = t[i:i + k] |
| 32 | a, b = t[i - 1], t[(i + k) % n] |
| 33 | saved = d(a, run[0]) + d(run[-1], b) - d(a, b) |
| 34 | rest = t[:i] + t[i + k:] |
| 35 | for j in range(1, len(rest) + 1): |
| 36 | x, y = rest[j - 1], rest[j % len(rest)] |
| 37 | for r in (run, run[::-1]): |
| 38 | if d(x, r[0]) + d(r[-1], y) - d(x, y) < saved - 1e-12: |
| 39 | t[:] = rest[:j] + r + rest[j:] |
| 40 | return True |
| 41 | return False |
| 42 | |
| 43 | |
| 44 | left, tour = set(range(1, n)), [0] |
| 45 | while left: |
| 46 | nxt = min(left, key=lambda j: d(tour[-1], j)) |
| 47 | left.remove(nxt) |
| 48 | tour.append(nxt) |
| 49 | two_opt(tour) |
| 50 | while or_opt(tour): |
| 51 | two_opt(tour) |
| 52 | print(json.dumps(tour)) |