#!/usr/bin/python3
# Simulated annealing for a simple travelling salesman problem

import numpy as np
import matplotlib.pyplot as plt

N = 20
Tstart = 10.0   # starting temperature
Tend = 1.E-2    # final temperature
delta = 1.E-4   # decrease temperature by a factor (1-delta)

def length(p):  # calculates path length
    L = 0.0
    x = p[:, 0] # x coordinates of cities
    y = p[:, 1] # y coordinates
    for n in range(-1, N-1): # (index -1 = last point)
        dx = x[n] - x[n + 1]
        dy = y[n] - y[n + 1]
        L += np.sqrt(dx**2 + dy**2)
    return L 
    # More compact, less readable:
    # return np.sqrt(np.sum((p[1:,:] - p[:-1, :])**2) + np.sum((p[0, :] - p[-1, :])**2))

path = np.random.random([N, 2])
d = length(path)
T = Tstart

while T > Tend:    # main loop
    city1, city2 = np.random.randint(N), np.random.randint(N)
    path[[city1, city2],:] = path[[city2, city1],:]  # flip two cities
    newd = length(path)                              # compute new path length
    if np.exp(-(newd - d)/T) > np.random.random():   # accept this configuration?
        d = newd
    else:                                            # otherwise, undo the change
        path[[city1, city2],:] = path[[city2, city1],:] 
    T *= (1 - delta)
    
print(d)
plt.plot(path[:,0], path[:,1], 'o-')
plt.show()