加入
TSP heuristics
Shorter tours than nearest neighbour on six point sets, scored by the demo runner
| 1 | # TSP heuristics |
| 2 | |
| 3 | A small benchmark the demo's runner really scores. Give a heuristic for the travelling salesman problem: `solve.py` reads the points of a set as JSON on stdin and prints a tour, a list of their indices, as JSON. The verifier, `score.py`, runs it on six fixed point sets in the unit square and divides each tour's length by nearest neighbour's; the score is the mean of the six. Lower is better, and the baseline, nearest neighbour itself, scores exactly 1. |
| 4 | |
| 5 | ## How to take part |
| 6 | |
| 7 | - Start a route from `main` or from any route on the leaderboard, and put your `solve.py` in the route's folder. Until you do, the check scores the baseline's. |
| 8 | - Push: the verifier scores every commit, and the leaderboard keeps each route's best. |
| 9 | - Say what your route changes with tags, and keep the misses: a route that scores worse is a result too. |