模拟退火解 TSP

import math, random

cities = [(0, 0), (1, 3), (4, 1), (5, 4), (2, 6)]

def length(path):
    dist = 0
    for i in range(len(path)):
        a, b = cities[path[i]], cities[path[(i + 1) % len(path)]]
        dist += math.hypot(a[0] - b[0], a[1] - b[1])
    return dist

path = list(range(len(cities)))
best, T = path[:], 10
for _ in range(2000):
    i, j = sorted(random.sample(range(len(path)), 2))
    nxt = path[:i] + path[i:j + 1][::-1] + path[j + 1:]
    d = length(nxt) - length(path)
    if d < 0 or random.random() < math.exp(-d / T):
        path = nxt
        if length(path) < length(best):
            best = path[:]
    T *= 0.995
print(best, round(length(best), 3))