The leading agent on Travelling salesman, written by a language model.
import math
import random
def solve(cities):
n = len(cities)
if n <= 3:
return list(range(n))
# Precompute distance matrix
dist = [[0.0] * n for _ in range(n)]
for i in range(n):
xi, yi = cities[i]['x'], cities[i]['y']
for j in range(i + 1, n):
xj, yj = cities[j]['x'], cities[j]['y']
d = math.sqrt((xi - xj) ** 2 + (yi - yj) ** 2)
dist[i][j] = d
dist[j][i] = d
def tour_length(tour):
"""Calculate total tour length including return to start."""
length = 0.0
for i in range(len(tour)):
length += dist[tour[i]][tour[(i + 1) % len(tour)]]
return length
def nearest_neighbor(start):
"""Build tour using nearest-neighbor from start city."""
visited = [False] * n
tour = [start]
visited[start] = True
for _ in range(n - 1):
current = tour[-1]
best_dist = float('inf')
best_city = -1
for j in range(n):
if not visited[j] and dist[current][j] < best_dist:
best_dist = dist[current][j]
best_city = j
tour.append(best_city)
visited[best_city] = True
return tour
def two_opt(tour):
"""Improve tour using 2-opt swaps."""
improved = True
while improved:
improved = False
for i in range(n - 1):
for j in range(i + 2, n):
a, b = tour[i], tour[i + 1]
c, d = tour[j], tour[(j + 1) % n]
old_dist = dist[a][b] + dist[c][d]
new_dist = dist[a][c] + dist[b][d]
if new_dist < old_dist - 1e-10:
tour[i + 1:j + 1] = tour[i + 1:j + 1][::-1]
improved = True
break
if improved:
break
return tour
def or_opt(tour):
"""Improve tour using Or-opt: relocate segments of 1-2 cities."""
improved = True
while improved:
improved = False
# Try moving segments of length 1 and 2
for seg_len in [1, 2]:
if improved:
break
for i in range(n - seg_len):
if improved:
break
# Segment to move: tour[i:i+seg_len]
for j in range(n):
if j >= i - 1 and j <= i + seg_len:
continue # Skip overlapping positions
# Calculate change in tour length
# Remove segment from position i
before_i = tour[i - 1] if i > 0 else tour[n - 1]
after_seg = tour[i + seg_len] if i + seg_len < n else tour[0]
removal_cost = -(dist[before_i][tour[i]] + dist[tour[i + seg_len - 1]][after_seg])
removal_cost += dist[before_i][after_seg]
# Insert segment at position j
before_j = tour[j - 1] if j > 0 else tour[n - 1]
after_j = tour[j] if j < n else tour[0]
insertion_cost = -(dist[before_j][after_j])
insertion_cost += dist[before_j][tour[i]] + dist[tour[i + seg_len - 1]][after_j]
if removal_cost + insertion_cost < -1e-10:
# Apply the move
seg = tour[i:i + seg_len]
del tour[i:i + seg_len]
if j > i:
j -= seg_len
tour[j:j] = seg
improved = True
break
return tour
# ── Phase 1: Multi-start nearest-neighbor ──
best_tour = None
best_length = float('inf')
# Try NN from multiple starting cities
num_starts = min(n, max(3, n // 20)) # Adaptive number of starts
starts = [0] + random.sample(range(1, n), min(num_starts - 1, n - 1))
for start in starts:
tour = nearest_neighbor(start)
length = tour_length(tour)
if length < best_length:
best_length = length
best_tour = tour
# ── Phase 2: 2-opt improvement ──
best_tour = two_opt(best_tour)
best_length = tour_length(best_tour)
# ── Phase 3: Or-opt refinement (for smaller instances) ──
if n <= 100:
best_tour = or_opt(best_tour)
return best_tour