<reponame>toratarou3153/python-learning
import random
import math
import numpy as np
import copy
import matplotlib.pyplot as plt

#点の数
n = 47
print(" 都市の数：" + str(n))
#クラスタリング・スケジュール(温度関数)の定数
c = 30
#クラスタリング・スケジュール(温度関数)の上界
end = 10000    #ここを変更
#摂動回数の設定
k = 400   #ここを変更


#クラスタリング・スケジュール(温度関数)の設定---------------------------------------------------------------------------------
def T(temper):
    return c/(math.sqrt(temper)+1)  #ここを変更

#初めにめぐる点の順番--------------------------------------------------------------------------------------------------------
city = [i for i in range(n)]
random.shuffle(city)

#点の位置-------------------------------------------------------------------------------------------------------------------
x=[141.345505,140.74,141.1525,140.87194,140.1025,140.36333,140.46778,140.44667,139.88361,139.06083,139.64889,140.12333,139.69167,139.6425,139.02361,137.21139,136.62556,136.22194,138.56833,138.18111,136.72222,138.38306,136.90667,136.50861,135.86833,135.75556,135.52,135.18306,135.83278,135.1675,134.23833,133.05056,133.935,132.45944,131.47139,134.55944,134.04333,132.76611,133.53111,130.41806,130.29889,129.87361,130.74167,131.6125,131.42389,130.55806,127.68111]
y=[43.06417,40.82444,39.70361,38.26889,39.71861,38.24056,37.75,36.34139,36.56583,36.39111,35.85694,35.60472,35.68944,35.44778,37.90222,36.69528,36.59444,36.06528,35.66389,36.65139,35.39111,34.97694,35.18028,34.73028,35.00444,35.02139,34.68639,34.69139,34.68528,34.22611,35.50361,35.47222,34.66167,34.39639,34.18583,34.06583,34.34028,33.84167,33.55972,33.60639,33.24944,32.74472,32.78972,33.23806,31.91111,31.56028,26.2125]


x_y = {}
for i,j,r in zip(range(n),x,y):
    x_y[i] = [j, r]

#距離を求める関数の生成-------------------------------------------------------------------------------------------------------
def d(toshi):
    kyori = 0
    for i in range(n):
        if toshi[i] != toshi[n-1]:
            kyori += math.sqrt((x_y[toshi[i+1]][0]-x_y[toshi[i]][0])**2+(x_y[toshi[i+1]][1]-x_y[toshi[i]][1])**2)
        else:
            kyori += math.sqrt((x_y[toshi[0]][0]-x_y[toshi[i]][0])**2+(x_y[toshi[0]][1]-x_y[toshi[i]][1])**2)
    return kyori
print("初期の距離：" + str(d(city)))

print("理想的な距離：",d([i for i in range(n)]))
x = [x_y[i][0] for i in range(n)]
y = [x_y[j][1] for j in range(n)]
x.append(x_y[0][0])
y.append(x_y[0][1])
plt.plot(x, y, marker="o")
plt.show()

x = [x_y[i][0] for i in city]
y = [x_y[j][1] for j in city]
x.append(x_y[city[0]][0])
y.append(x_y[city[0]][1])
plt.plot(x, y, marker="o")
plt.show()

#大域的最小値の生成-----------------------------------------------------------------------------------------------------------
for t in range(end):
    for i in range(k):
        #摂動の生成--------------------------------------------------------------------------------------------------
        a = random.randint(1,n-1)
        b = random.randint(a+1,n)
        city_near = copy.copy(city)
        city_near[a:b] = reversed(city_near[a:b])
        #遷移--------------------------------------------------------------------------------------------------------
        if d(city) >= d(city_near):
            city = city_near
        else:
            P = (math.e)**(-(d(city_near)-d(city))/T(t))
            m = np.random.choice([0,1],p = [1-P,P])
            if m == 1:
                city = city_near

print("最小値：" + str(d(city)))
print("順番：" + str(city))

x = [x_y[i][0] for i in city]
y = [x_y[j][1] for j in city]
x.append(x_y[city[0]][0])
y.append(x_y[city[0]][1])
plt.plot(x, y, marker="o")
plt.show()
