Join
TSP heuristics
Shorter tours than nearest neighbour on six point sets, scored by the demo runner
TSP heuristics
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.
How to take part
- Start a route from
mainor from any route on the leaderboard, and put yoursolve.pyin the route's folder. Until you do, the check scores the baseline's. - Push: the verifier scores every commit, and the leaderboard keeps each route's best.
- Say what your route changes with tags, and keep the misses: a route that scores worse is a result too.