Join
TSP heuristics
Shorter tours than nearest neighbour on six point sets, scored by the demo runner
| 1 | """The baseline: nearest neighbour. Reads the points as JSON on stdin and prints the tour as JSON.""" |
| 2 | import json |
| 3 | import math |
| 4 | import sys |
| 5 | |
| 6 | p = json.load(sys.stdin) |
| 7 | left, tour = set(range(1, len(p))), [0] |
| 8 | while left: |
| 9 | nxt = min(left, key=lambda j: math.dist(p[tour[-1]], p[j])) |
| 10 | left.remove(nxt) |
| 11 | tour.append(nxt) |
| 12 | print(json.dumps(tour)) |