加入
TSP heuristics
Shorter tours than nearest neighbour on six point sets, scored by the demo runner
+59 −0 score.py 新增 查看文件
| @@ -0,0 +1,59 @@ | ||
| 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") | |