加入
TSP heuristics
Shorter tours than nearest neighbour on six point sets, scored by the demo runner
| 1 | #!/usr/bin/env python3 |
| 2 | """Score a route's travelling-salesman heuristic on six fixed point sets: its tour's length over nearest neighbour's. |
| 3 | |
| 4 | Usage: score.py ROUTE_FOLDER. The route's solve.py (or the baseline's, at the top of the project, if the route has |
| 5 | none) reads the points as JSON on stdin and prints the tour as JSON. It runs in its own process and only the tour it |
| 6 | prints is used. Writes metrics.json; the last line sums up.""" |
| 7 | import json |
| 8 | import math |
| 9 | import random |
| 10 | import subprocess |
| 11 | import sys |
| 12 | import time |
| 13 | from pathlib import Path |
| 14 | |
| 15 | |
| 16 | def points(n, seed): |
| 17 | rng = random.Random(seed) |
| 18 | return [[round(rng.random(), 6), round(rng.random(), 6)] for _ in range(n)] |
| 19 | |
| 20 | |
| 21 | SETS = {f"n{n}-{s}": points(n, s) for n, s in [(40, 1), (40, 2), (80, 3), (80, 4), (160, 5), (160, 6)]} |
| 22 | |
| 23 | |
| 24 | def length(p, tour): |
| 25 | return sum(math.dist(p[tour[i - 1]], p[tour[i]]) for i in range(len(tour))) |
| 26 | |
| 27 | |
| 28 | def nearest(p): |
| 29 | left, tour = set(range(1, len(p))), [0] |
| 30 | while left: |
| 31 | nxt = min(left, key=lambda j: math.dist(p[tour[-1]], p[j])) |
| 32 | left.remove(nxt) |
| 33 | tour.append(nxt) |
| 34 | return tour |
| 35 | |
| 36 | |
| 37 | folder = Path(sys.argv[1]) |
| 38 | solver = folder / "solve.py" if (folder / "solve.py").is_file() else Path("input/solve.py") |
| 39 | subtasks, seconds = {}, 0.0 |
| 40 | for name, p in SETS.items(): |
| 41 | start = time.perf_counter() |
| 42 | try: |
| 43 | out = subprocess.run([sys.executable, str(solver)], input=json.dumps(p), capture_output=True, text=True, timeout=30) |
| 44 | tour = json.loads(out.stdout) |
| 45 | ok = isinstance(tour, list) and sorted(tour) == list(range(len(p))) |
| 46 | except Exception as e: |
| 47 | print(f"{name}: the solver failed ({type(e).__name__})") |
| 48 | sys.exit(1) |
| 49 | seconds += time.perf_counter() - start |
| 50 | if not ok: |
| 51 | print(f"{name}: the tour must visit every point exactly once") |
| 52 | sys.exit(1) |
| 53 | subtasks[name] = round(length(p, tour) / length(p, nearest(p)), 4) |
| 54 | if seconds > 30: |
| 55 | print(f"took {seconds:.1f} s; the limit is 30 s") |
| 56 | sys.exit(1) |
| 57 | score = round(sum(subtasks.values()) / len(subtasks), 4) |
| 58 | Path("metrics.json").write_text(json.dumps({"score": score, "cost": round(seconds, 2), "subtasks": subtasks})) |
| 59 | print(f"{score} of nearest neighbour's tour length on {len(subtasks)} point sets, in {seconds:.1f} s") |