0% ≤ diff ≤ 2%_main_: cluster #1 (11)
| # 6331419021 309 (2020-09-13 17:51) %diff = 0.0 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.001 : # while not finished # create a new tour from the current tour r = random.random() if r < 0.2: i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) elif r<0.4: a = random.randint(0,N-5) b = random.randint(a+1,N-3) c = random.randint(b+1, N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 =0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r<0.6 : a = random.randint(0,N-4) b = a+1 x = random.randint(b+1,N-2) tour1 = tour[:a+1] + tour[a+1:a+2] + tour[b+1:] L0 = L1 =0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r<0.8 : a = random.randint(0,N-4) b = random.randint(a+1,N-3) c = random.randint(b+1,N-2) d = random.randint(c+1,N-1) tour1 = tour[:a] + tour[c:d+1] + tour[b+1:c] + tour[a:b+1] + tour[d+1:] L0 = L1 =0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 else : a = random.randint(0,N-2) b = random.randint(a+1,N-1) tour1 = tour[:a+1] + tour[b:a:-1] + tour[b+1:] L0 = L1 =0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *= 0.9998 # lower the temperature print(tour) | # 6331010921 223 (2020-09-13 21:01) %diff = 0.0 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.001 : # while not finished # create a new tour from the current tour r = random.random() if r < 0.2: i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) elif r<0.4: a = random.randint(0,N-5) b = random.randint(a+1,N-3) c = random.randint(b+1, N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 =0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r<0.6 : a = random.randint(0,N-4) b = a+1 x = random.randint(b+1,N-2) tour1 = tour[:a+1] + tour[a+1:a+2] + tour[b+1:] L0 = L1 =0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r<0.8 : a = random.randint(0,N-4) b = random.randint(a+1,N-3) c = random.randint(b+1,N-2) d = random.randint(c+1,N-1) tour1 = tour[:a] + tour[c:d+1] + tour[b+1:c] + tour[a:b+1] + tour[d+1:] L0 = L1 =0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 else : a = random.randint(0,N-2) b = random.randint(a+1,N-1) tour1 = tour[:a+1] + tour[b:a:-1] + tour[b+1:] L0 = L1 =0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *= 0.9998 # lower the temperature print(tour) | # 6330004021 53 (2020-09-13 21:42) %diff = 1.89 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.001 : # while not finished # create a new tour from the current tour r = random.random() if r < 0.2 : #good 280.11 i = random.randint(0, N-2) j = random.randint(i+1,N-1) tour1 = list(tour) tour1[i],tour1[j] = tour1[j],tour1[i] dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) elif r< 0.2 : #very good 238.03 a = random.randint(0,N-5) b = random.randint(a+1,N-3) c = random.randint(b+1,N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1],tour[i]) L1 += dist(tour1[i-1],tour1[i]) dE = L1 - L0 elif r < 0.1 :#bad a = random.randint(0,N-5) b = a+1 x = random.randint(a+2,N-3) tour1 = tour[:a+1]+tour[x:x+1]+tour[b:] L0 = L1 = 0 for i in range(N) : L0 += dist(tour[i-1],tour[i]) L1 += dist(tour1[i-1],tour1[i]) dE = L1 - L0 elif r< 0.2 :#good 262 a = random.randint(0,N-5) b = random.randint(a+1,N-3) c = random.randint(b+1,N-2) d = random.randint(c+1,N-1) tour1 = tour[:a]+tour[c:d+1]+tour[b+1:c]+tour[a:b+1]+tour[d+1:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1],tour[i]) L1 += dist(tour1[i-1],tour1[i]) dE = L1 - L0 else: #Perfect a = random.randint(1,N-2) b = random.randint(a+1,N-1) tour1 = tour[:a]+tour[b:a-1:-1]+tour[b+1:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1],tour[i]) L1 += dist(tour1[i-1],tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *= 0.9999 # lower the temperature print(tour) | # 6331002921 216 (2020-09-13 21:45) %diff = 0.0 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.001 : # while not finished # create a new tour from the current tour r = random.random() if r < 0.2: i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) elif r<0.4: a = random.randint(0,N-5) b = random.randint(a+1,N-3) c = random.randint(b+1, N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 =0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r<0.6 : a = random.randint(0,N-4) b = a+1 x = random.randint(b+1,N-2) tour1 = tour[:a+1] + tour[a+1:a+2] + tour[b+1:] L0 = L1 =0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r<0.8 : a = random.randint(0,N-4) b = random.randint(a+1,N-3) c = random.randint(b+1,N-2) d = random.randint(c+1,N-1) tour1 = tour[:a] + tour[c:d+1] + tour[b+1:c] + tour[a:b+1] + tour[d+1:] L0 = L1 =0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 else : a = random.randint(0,N-2) b = random.randint(a+1,N-1) tour1 = tour[:a+1] + tour[b:a:-1] + tour[b+1:] L0 = L1 =0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *= 0.9998 # lower the temperature print(tour) | # 6330020021 69 (2020-09-13 22:10) %diff = 1.48 map_name = input("map name = ") X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T>0.001 : # while not finished # create a new tour from the current tour r = random.random() if r < 0.1: i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) elif r<0.3: a = random.randint(0,N-5) b = random.randint(a+1,N-3) c = random.randint(b+1, N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 =0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r<0.5 : a = random.randint(0,N-4) b = a+1 x = random.randint(b+1,N-2) tour1 = tour[:a+1] + tour[a+1:a+2] + tour[b+1:] L0 = L1 =0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r<0.7 : a = random.randint(0,N-4) b = random.randint(a+1,N-3) c = random.randint(b+1,N-2) d = random.randint(c+1,N-1) tour1 = tour[:a] + tour[c:d+1] + tour[b+1:c] + tour[a:b+1] + tour[d+1:] L0 = L1 =0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 else : a = random.randint(0,N-2) b = random.randint(a+1,N-1) tour1 = tour[:a+1] + tour[b:a:-1] + tour[b+1:] L0 = L1 =0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 #accept new tour if shorter or within prob. if dE< 0 or random.random() < math.exp(-dE/T): tour = tour1 T*=0.99955 # lower the temperature print(tour) | # 6331023021 235 (2020-09-13 22:15) %diff = 0.0 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.001 : # while not finished # create a new tour from the current tour r = random.random() if r < 0.2: i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 à ¹‚€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) elif r<0.4: a = random.randint(0,N-5) b = random.randint(a+1,N-3) c = random.randint(b+1, N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 =0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r<0.6 : a = random.randint(0,N-4) b = a+1 x = random.randint(b+1,N-2) tour1 = tour[:a+1] + tour[a+1:a+2] + tour[b+1:] L0 = L1 =0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r<0.8 : a = random.randint(0,N-4) b = random.randint(a+1,N-3) c = random.randint(b+1,N-2) d = random.randint(c+1,N-1) tour1 = tour[:a] + tour[c:d+1] + tour[b+1:c] + tour[a:b+1] + tour[d+1:] L0 = L1 =0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 else : a = random.randint(0,N-2) b = random.randint(a+1,N-1) tour1 = tour[:a+1] + tour[b:a:-1] + tour[b+1:] L0 = L1 =0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *= 0.9998 # lower the temperature print(tour) | # 6331517821 323 (2020-09-13 22:19) %diff = 0.0 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.001 : # while not finished # create a new tour from the current tour r = random.random() if r < 0.2: i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 à ¹‚€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) elif r < 0.4: a = random.randint(0,N-5) b = random.randint(a+1,N-3) c = random.randint(b+1, N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 =0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r < 0.6 : a = random.randint(0,N-4) b = a+1 x = random.randint(b+1,N-2) tour1 = tour[:a+1] + tour[a+1:a+2] + tour[b+1:] L0 = L1 =0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r<0.8 : a = random.randint(0,N-4) b = random.randint(a+1,N-3) c = random.randint(b+1,N-2) d = random.randint(c+1,N-1) tour1 = tour[:a] + tour[c:d+1] + tour[b+1:c] + tour[a:b+1] + tour[d+1:] L0 = L1 =0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 else : a = random.randint(0,N-2) b = random.randint(a+1,N-1) tour1 = tour[:a+1] + tour[b:a:-1] + tour[b+1:] L0 = L1 =0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *= 0.9998 # lower the temperature print(tour) | # 6331205021 274 (2020-09-13 22:31) %diff = 0.0 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.001 : # while not finished # create a new tour from the current tour r = random.random() if r < 0.2: i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 à ¹‚€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) elif r < 0.4: a = random.randint(0,N-5) b = random.randint(a+1,N-3) c = random.randint(b+1, N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 =0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r < 0.6 : a = random.randint(0,N-4) b = a+1 x = random.randint(b+1,N-2) tour1 = tour[:a+1] + tour[a+1:a+2] + tour[b+1:] L0 = L1 =0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r<0.8 : a = random.randint(0,N-4) b = random.randint(a+1,N-3) c = random.randint(b+1,N-2) d = random.randint(c+1,N-1) tour1 = tour[:a] + tour[c:d+1] + tour[b+1:c] + tour[a:b+1] + tour[d+1:] L0 = L1 =0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 else : a = random.randint(0,N-2) b = random.randint(a+1,N-1) tour1 = tour[:a+1] + tour[b:a:-1] + tour[b+1:] L0 = L1 =0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *= 0.9998 # lower the temperature print(tour) | # 6331005821 219 (2020-09-13 22:41) %diff = 0.08 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.001 : # while not finished # create a new tour from the current tour r = random.random() if r < 0.2: i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 à ¹‚€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) elif r < 0.4: a = random.randint(0,N-5) b = random.randint(a+1,N-3) c = random.randint(b+1, N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 =0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r < 0.6 : a = random.randint(0,N-4) b = a+1 x = random.randint(b+1,N-2) tour1 = tour[:a+1] + tour[a+1:a+2] + tour[b+1:] L0 = L1 =0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r<0.8 : a = random.randint(0,N-4) b = random.randint(a+1,N-3) c = random.randint(b+1,N-2) d = random.randint(c+1,N-1) tour1 = tour[:a] + tour[c:d+1] + tour[b+1:c] + tour[a:b+1] + tour[d+1:] L0 = L1 =0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 else : a = random.randint(0,N-2) b = random.randint(a+1,N-1) tour1 = tour[:a+1] + tour[b:a:-1] + tour[b+1:] L0 = L1 =0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 # while not finished # create a new tour from the current tour # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *= 0.9998 # lower the temperature print(tour) | # 6331232921 293 (2020-09-13 22:48) %diff = 1.94 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.011 : # while not finished # create a new tour from the current tour r = random.random() if r < 0.15: i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 à ¹‚€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) elif r < 0.45: a = random.randint(0,N-5) b = random.randint(a+1,N-3) c = random.randint(b+1, N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 =0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r < 0.60 : a = random.randint(0,N-4) b = a+1 x = random.randint(b+1,N-2) tour1 = tour[:a+1] + tour[a+1:a+2] + tour[b+1:] L0 = L1 =0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r<0.8 : a = random.randint(0,N-4) b = random.randint(a+1,N-3) c = random.randint(b+1,N-2) d = random.randint(c+1,N-1) tour1 = tour[:a] + tour[c:d+1] + tour[b+1:c] + tour[a:b+1] + tour[d+1:] L0 = L1 =0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 else : a = random.randint(0,N-2) b = random.randint(a+1,N-1) tour1 = tour[:a+1] + tour[b:a:-1] + tour[b+1:] L0 = L1 =0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *= 0.9998 # lower the temperature print(tour) animate(X, Y, tour_log[-1:] ) # let's animate | # 6331011521 224 (2020-09-13 22:49) %diff = 0.0 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.001 : # while not finished # create a new tour from the current tour r = random.random() if r < 0.2: i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 à ¹‚€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) elif r<0.4: a = random.randint(0,N-5) b = random.randint(a+1,N-3) c = random.randint(b+1, N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 =0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r<0.6 : a = random.randint(0,N-4) b = a+1 x = random.randint(b+1,N-2) tour1 = tour[:a+1] + tour[a+1:a+2] + tour[b+1:] L0 = L1 =0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r<0.8 : a = random.randint(0,N-4) b = random.randint(a+1,N-3) c = random.randint(b+1,N-2) d = random.randint(c+1,N-1) tour1 = tour[:a] + tour[c:d+1] + tour[b+1:c] + tour[a:b+1] + tour[d+1:] L0 = L1 =0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 else : a = random.randint(0,N-2) b = random.randint(a+1,N-1) tour1 = tour[:a+1] + tour[b:a:-1] + tour[b+1:] L0 = L1 =0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *= 0.9998 # lower the temperature print(tour) |
_main_: cluster #2 (2)
| # 6331214621 280 (2020-09-13 17:21) %diff = 0.0 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.0001 : # while not finished # create a new tour from the current tour r = random.random() if r<0.2: i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) elif r<0.4: #ขวาบน a = random.randint(0,N-5) b = random.randint(a+2,N-3) c = random.randint(b+1,N-2) d = c+1 tour1 = tour[:a+1]+tour[b:c+1]+tour[a+1:b]+tour[d:] L0=L1=0 for i in range(N): L0 += dist(tour[i-1],tour[i]) L1 += dist(tour1[i-1],tour1[i]) dE = L1-L0 elif r<0.6: #ซ้ายบน a = random.randint(0,N-3) b = a+1 c = random.randint(b+1,N) tour1 = tour[:a+1]+tour[c:c+1]+tour[b:c]+tour[c+1:] L0=L1=0 for i in range(N): L0 += dist(tour[i-1],tour[i]) L1 += dist(tour1[i-1],tour1[i]) dE = L1-L0 elif r<0.8: #ซ้ายล่าง a = random.randint(0,N-1) b = random.randint(a+1,N) if a==0: tour1 = tour[b::-1]+tour[b+1:] else: tour1 = tour[:a]+tour[b:a-1:-1]+tour[b+1:] L0=L1=0 for i in range(N): L0 += dist(tour[i-1],tour[i]) L1 += dist(tour1[i-1],tour1[i]) dE = L1-L0 else: #ขวาล่าง a = random.randint(0,N-3) b = random.randint(a+1,N-2) c = random.randint(b+1,N-1) d = random.randint(c+1,N) tour1 = tour[:a]+tour[c:d+1]+tour[b+1:c]+tour[a:b+1]+tour[d+1:] L0=L1=0 for i in range(N): L0 += dist(tour[i-1],tour[i]) L1 += dist(tour1[i-1],tour1[i]) dE = L1-L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T*=0.9999 # lower the temperaturea print(tour) | # 6331210021 277 (2020-09-13 19:10) %diff = 0.0 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.0001 : # while not finished # create a new tour from the current tour r = random.random() if r<0.2: i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) elif r<0.4: a = random.randint(0,N-5) b = random.randint(a+2,N-3) c = random.randint(b+1,N-2) d = c+1 tour1 = tour[:a+1]+tour[b:c+1]+tour[a+1:b]+tour[d:] L0=L1=0 for i in range(N): L0 += dist(tour[i-1],tour[i]) L1 += dist(tour1[i-1],tour1[i]) dE = L1-L0 elif r<0.6: a = random.randint(0,N-3) b = a+1 c = random.randint(b+1,N) tour1 = tour[:a+1]+tour[c:c+1]+tour[b:c]+tour[c+1:] L0=L1=0 for i in range(N): L0 += dist(tour[i-1],tour[i]) L1 += dist(tour1[i-1],tour1[i]) dE = L1-L0 elif r<0.8: a = random.randint(0,N-1) b = random.randint(a+1,N) if a==0: tour1 = tour[b::-1]+tour[b+1:] else: tour1 = tour[:a]+tour[b:a-1:-1]+tour[b+1:] L0=L1=0 for i in range(N): L0 += dist(tour[i-1],tour[i]) L1 += dist(tour1[i-1],tour1[i]) dE = L1-L0 else: a = random.randint(0,N-3) b = random.randint(a+1,N-2) c = random.randint(b+1,N-1) d = random.randint(c+1,N) tour1 = tour[:a]+tour[c:d+1]+tour[b+1:c]+tour[a:b+1]+tour[d+1:] L0=L1=0 for i in range(N): L0 += dist(tour[i-1],tour[i]) L1 += dist(tour1[i-1],tour1[i]) dE = L1-L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T*=0.9999 # lower the temperaturea print(tour) |
_main_: cluster #3 (5)
| # 6331404521 298 (2020-09-13 22:15) %diff = 0.0 map_name = input("Map file name: ") X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.001 : # while not finished r = random.random() if r < 0.2 : i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) tour1[i], tour1[j] = tour1[j], tour1[i] dE = dist(tour1[i-1], tour1[i]) + \ dist(tour1[i], tour1[i+1]) + \ dist(tour1[j-1], tour1[j]) + \ dist(tour1[j], tour1[(j+1)%N]) - \ dist(tour[i-1], tour[i]) - \ dist(tour[i], tour[i+1]) - \ dist(tour[j-1], tour[j]) - \ dist(tour[j], tour[(j+1)%N]) elif r < 0.4 : q = random.randint(0, N-5) w = random.randint(q+1, N-3) e = random.randint(w+1, N-2) r = e+1 tour1 = tour[:q+1] + tour[w:e+1] + tour[q+1:w] + tour[r:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r < 0.6 : a = random.randint(0, N-5) b = random.randint(a+1, N-4) c = random.randint(b+1, N-3) d = random.randint(c+1, N-2) tour1 = tour[:a] + tour[c:d+1] + tour[b+1:c] + \ tour[a:b+1] + tour[d+1:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r < 0.8 : s = random.randint(0, N-2) f = random.randint(s+1, N-1) tour1 = tour[:s+1] + tour[f:s:-1] + tour[f+1:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 else : x = random.randint(0, N-3) y = x+1 z = random.randint(y+1, N-1) tour1 = tour[:x] + tour[x:x+1] + tour[z:z+1] + tour[y:z] + tour[z+1:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *= 0.9999 # lower the temperature print(tour) | # 6330007921 56 (2020-09-13 23:14) %diff = 0.0 map_name = input("Map file name: ") X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.001 : # while not finished r = random.random() if r < 0.2 : i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) tour1[i], tour1[j] = tour1[j], tour1[i] dE = dist(tour1[i-1], tour1[i]) + \ dist(tour1[i], tour1[i+1]) + \ dist(tour1[j-1], tour1[j]) + \ dist(tour1[j], tour1[(j+1)%N]) - \ dist(tour[i-1], tour[i]) - \ dist(tour[i], tour[i+1]) - \ dist(tour[j-1], tour[j]) - \ dist(tour[j], tour[(j+1)%N]) elif r < 0.4 : q = random.randint(0, N-5) w = random.randint(q+1, N-3) e = random.randint(w+1, N-2) r = e+1 tour1 = tour[:q+1] + tour[w:e+1] + tour[q+1:w] + tour[r:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r < 0.6 : a = random.randint(0, N-5) b = random.randint(a+1, N-4) c = random.randint(b+1, N-3) d = random.randint(c+1, N-2) tour1 = tour[:a] + tour[c:d+1] + tour[b+1:c] + \ tour[a:b+1] + tour[d+1:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r < 0.8 : s = random.randint(0, N-2) f = random.randint(s+1, N-1) tour1 = tour[:s+1] + tour[f:s:-1] + tour[f+1:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 else : x = random.randint(0, N-3) y = x+1 z = random.randint(y+1, N-1) tour1 = tour[:x] + tour[x:x+1] + tour[z:z+1] + tour[y:z] + tour[z+1:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *= 0.9999 # lower the temperature print(tour) | # 6331219821 285 (2020-09-13 23:19) %diff = 0.0 map_name = input("Map file name: ") X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.001 : # while not finished r = random.random() if r < 0.2 : i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) tour1[i], tour1[j] = tour1[j], tour1[i] dE = dist(tour1[i-1], tour1[i]) + \ dist(tour1[i], tour1[i+1]) + \ dist(tour1[j-1], tour1[j]) + \ dist(tour1[j], tour1[(j+1)%N]) - \ dist(tour[i-1], tour[i]) - \ dist(tour[i], tour[i+1]) - \ dist(tour[j-1], tour[j]) - \ dist(tour[j], tour[(j+1)%N]) elif r < 0.4 : q = random.randint(0, N-5) w = random.randint(q+1, N-3) e = random.randint(w+1, N-2) r = e+1 tour1 = tour[:q+1] + tour[w:e+1] + tour[q+1:w] + tour[r:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r < 0.6 : a = random.randint(0, N-5) b = random.randint(a+1, N-4) c = random.randint(b+1, N-3) d = random.randint(c+1, N-2) tour1 = tour[:a] + tour[c:d+1] + tour[b+1:c] + \ tour[a:b+1] + tour[d+1:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r < 0.8 : s = random.randint(0, N-2) f = random.randint(s+1, N-1) tour1 = tour[:s+1] + tour[f:s:-1] + tour[f+1:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 else : x = random.randint(0, N-3) y = x+1 z = random.randint(y+1, N-1) tour1 = tour[:x] + tour[x:x+1] + tour[z:z+1] + tour[y:z] + tour[z+1:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *= 0.9999 # lower the temperature print(tour) | # 6331116821 252 (2020-09-13 23:29) %diff = 0.0 map_name = input("Map file name: ") X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.001 : # while not finished r = random.random() if r < 0.2 : i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) tour1[i], tour1[j] = tour1[j], tour1[i] dE = dist(tour1[i-1], tour1[i]) + \ dist(tour1[i], tour1[i+1]) + \ dist(tour1[j-1], tour1[j]) + \ dist(tour1[j], tour1[(j+1)%N]) - \ dist(tour[i-1], tour[i]) - \ dist(tour[i], tour[i+1]) - \ dist(tour[j-1], tour[j]) - \ dist(tour[j], tour[(j+1)%N]) elif r < 0.4 : q = random.randint(0, N-5) w = random.randint(q+1, N-3) e = random.randint(w+1, N-2) r = e+1 tour1 = tour[:q+1] + tour[w:e+1] + tour[q+1:w] + tour[r:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r < 0.6 : a = random.randint(0, N-5) b = random.randint(a+1, N-4) c = random.randint(b+1, N-3) d = random.randint(c+1, N-2) tour1 = tour[:a] + tour[c:d+1] + tour[b+1:c] + \ tour[a:b+1] + tour[d+1:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r < 0.8 : s = random.randint(0, N-2) f = random.randint(s+1, N-1) tour1 = tour[:s+1] + tour[f:s:-1] + tour[f+1:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 else : x = random.randint(0, N-3) y = x+1 z = random.randint(y+1, N-1) tour1 = tour[:x] + tour[x:x+1] + tour[z:z+1] + tour[y:z] + tour[z+1:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *= 0.9999 # lower the temperature print(tour) | # 6331130521 265 (2020-09-13 23:56) %diff = 1.07 map_name = input("Map name: ") X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 1e-10 : # while not finished r = random.random() if r < 0.2 : i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) tour1[i], tour1[j] = tour1[j], tour1[i] dE = dist(tour1[i-1], tour1[i]) + \ dist(tour1[i], tour1[i+1]) + \ dist(tour1[j-1], tour1[j]) + \ dist(tour1[j], tour1[(j+1)%N]) - \ dist(tour[i-1], tour[i]) - \ dist(tour[i], tour[i+1]) - \ dist(tour[j-1], tour[j]) - \ dist(tour[j], tour[(j+1)%N]) elif r < 0.33 : q = random.randint(0, N-5) w = random.randint(q+1, N-3) e = random.randint(w+1, N-2) r = e+1 tour1 = tour[:q+1] + tour[w:e+1] + tour[q+1:w] + tour[r:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r < 0.6 : a = random.randint(0, N-5) b = random.randint(a+1, N-4) c = random.randint(b+1, N-3) d = random.randint(c+1, N-2) tour1 = tour[:a] + tour[c:d+1] + tour[b+1:c] + \ tour[a:b+1] + tour[d+1:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r < 0.8 : s = random.randint(0, N-2) f = random.randint(s+1, N-1) tour1 = tour[:s+1] + tour[f:s:-1] + tour[f+1:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 else : x = random.randint(0, N-3) y = x+1 z = random.randint(y+1, N-1) tour1 = tour[:x] + tour[x:x+1] + tour[z:z+1] + tour[y:z] + tour[z+1:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *= 0.99955 # lower the temperature print(tour) |
_main_: cluster #4 (2)
| # 6330083521 127 (2020-09-12 23:03) %diff = 0.0 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.000001 : # while not finished # # create a new tour from the current tour r = random.random() if r < 0.01 : i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) elif r<0.8: a = random.randint(1,N-3) b = random.randint(a+2,N-1) tour1 = tour[:a]+tour[b:a-1:-1]+tour[b+1:] dE = dist(tour1[a-1], tour1[a ]) + \ dist(tour1[a ], tour1[a+1 ]) + \ dist(tour1[b-1], tour1[b ]) + \ dist(tour1[b ], tour1[(b+1)%N]) - \ dist(tour[ a-1], tour[ a ]) - \ dist(tour[ a ], tour[ a+1 ]) - \ dist(tour[ b-1], tour[ b ]) - \ dist(tour[ b ], tour[(b+1)%N ]) else: a = random.randint(0, N-5) b = random.randint(a+1, N-3) c = random.randint(b+1, N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 = 0 for i in range(N) : L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T = 0.9998*T # lower the temperature print(tour) | # 6330044021 92 (2020-09-13 21:46) %diff = 0.0 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.000001 : # while not finished # # create a new tour from the current tour r = random.random() if r < 0.01 : i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) elif r<0.8: a = random.randint(1,N-3) b = random.randint(a+2,N-1) tour1 = tour[:a]+tour[b:a-1:-1]+tour[b+1:] dE = dist(tour1[a-1], tour1[a ]) + \ dist(tour1[a ], tour1[a+1 ]) + \ dist(tour1[b-1], tour1[b ]) + \ dist(tour1[b ], tour1[(b+1)%N]) - \ dist(tour[ a-1], tour[ a ]) - \ dist(tour[ a ], tour[ a+1 ]) - \ dist(tour[ b-1], tour[ b ]) - \ dist(tour[ b ], tour[(b+1)%N ]) else: a = random.randint(0, N-5) b = random.randint(a+1, N-3) c = random.randint(b+1, N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 = 0 for i in range(N) : L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T = 0.9998*T # lower the temperature print(tour) |
_main_: cluster #5 (27)
| # 6330131021 174 (2020-09-12 23:14) %diff = 0.61 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #----------- let's the SA begins ------------------- loop = 0 T = N*10 # starting temperature while T > 0.0001: # while not finished # create a new tour from the current tour r = random.random() if r < 0.3: i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ] , tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ] , tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ] , tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ] , tour[(j+1)%N ]) else: a = random.randint(0,N-5) b = random.randint(a+1,N-3) c = random.randint(b+1,N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T): tour = tour1 # lower the temperature T = 0.999*T print(tour) | # 6330061721 108 (2020-09-13 03:39) %diff = 1.67 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.001 : # while not finished # create a new tour from the current tour r = random.random() if r < 0.5 : i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else : a = random.randint(0, N-5) b = random.randint(a+1, N-2) c = random.randint(b+1, N-1) d = c + 1 tour1 = tour[:a+1]+tour[b:c+1]+tour[d:]+tour[a+1:b] L0 = L1 = 0 for i in range(N) : L0 += dist(tour[i-1], tour [i]) L1 += dist(tour1[i-1], tour1 [i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *= 0.9999 # lower the temperature print(tour) | # 6330096721 140 (2020-09-13 13:13) %diff = 0.75 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.000001 : # while not finished # create a new tour from the current tour r = random.random() if r <= 0.2: i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else : a = random.randint(0,N-5) b = random.randint(a+1,N-3) c = random.randint(b+1,N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 = 0 for i in range(N): L0 +=dist(tour[i-1],tour[i]) L1 +=dist(tour1[i-1],tour1[i]) dE = L1-L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *=0.9999 # lower the temperature print(tour) | # 6331021821 233 (2020-09-13 13:27) %diff = 0.45 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.001 : # while not finished # create a new tour from the current tour r = random.random() if r < 0.5: i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 – length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else: a = random.randint(0, N-5) b = random.randint(a+1, N-3) c = random.randint(b+1, N-2) d = c+1 tour1 = tour[0:a+1:] + tour[b:c+1] + tour[a+1:b] + tour[d::] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *= 0.9999 # lower the temperature print(tour) | # 6330122321 166 (2020-09-13 14:18) %diff = 0.75 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.000015 : # while not finished # create a new tour from the current tour r = random.random() if r < 0.18: i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else : a = random.randint(0,N-5) b = random.randint(a+1,N-3) c = random.randint(b+1,N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 = 0 for i in range(N): L0 +=dist(tour[i-1],tour[i]) L1 +=dist(tour1[i-1],tour1[i]) dE = L1-L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *=0.9998 # lower the temperature print(tour) | # 6330113721 157 (2020-09-13 15:14) %diff = 0.45 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.0001 : # while not finished # create a new tour from the current tour r = random.random() if r < 0.5 : i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else : a = random.randint(0, N-5) b = random.randint(a+1, N-3) c = random.randint(b+1, N-2) d = c+1 tour1 = tour[:a+1]+tour[b:c+1]+tour[a+1:b]+tour[d:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1-L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *= 0.99995 # lower the temperature print(tour) | # 6330128121 171 (2020-09-13 15:35) %diff = 1.21 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.00078: # while not finished r = random.random() if r < 0.5: i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else: a= random.randint(0 , N-5) b= random.randint(a+1 , N-3) c= random.randint(b+1 , N-2) d= c+1 tour1 =tour[:a+1] + tour[b:c+2] + tour[a:b] + tour[d:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1] , tour[i]) L1 += dist(tour[i-1] , tour[i]) dE = L1 - L0 if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *=0.999 # lower the temperature print(tour) | # 6330102821 146 (2020-09-13 17:35) %diff = 0.15 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.001 : # while not finished # create a new tour from the current tour r = random.random() if r < 0.3: i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else : a = random.randint(0,N-5) b = random.randint(a+1,N-3) c = random.randint(b+1,N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 = 0 for i in range(N): L0 +=dist(tour[i-1],tour[i]) L1 +=dist(tour1[i-1],tour1[i]) dE = L1-L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *=0.9999 # lower the temperature print(tour) | # 6330013621 62 (2020-09-13 17:58) %diff = 0.76 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.001 : # while not finished # create a new tour from the current tour r = random.random() if r < 0.9 : i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else : a = random.randint(0, N-5) b = random.randint(a+1, N-3) c = random.randint(b+1, N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T = 0.99999*T # lower the temperature print(tour) | # 6330039021 87 (2020-09-13 18:03) %diff = 0.0 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.001 : # while not finished # create a new tour from the current tour r = random.random() if r < 0.5: #always false i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else : # prob = 0.5 a = random.randint(0, N-5) b = random.randint(a+1, N-3) c = random.randint(b+1, N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *= 0.9999 # lower the temperature print(tour) | # 6230176121 11 (2020-09-13 18:56) %diff = 0.15 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.001 : # while not finished # create a new tour from the current tour r = random.random() if r < 0.21 : i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 - length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else : a = random.randint(0, N-5) b = random.randint(a+1 , N-3) c = random.randint(b+1 , N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 = 0 for i in range(N) : L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T): tour = tour1 T *= 0.9999 # lower the temperature print(tour) | # 6331003521 217 (2020-09-13 19:54) %diff = 1.51 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.001 : loop += 1 # while not finished # create a new tour from the current tour r = random.random() if r < 0.5: i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else : a = random.randint(0,N-5) b = random.randint(a+1,N-3) c = random.randint(b+1,N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1],tour[i]) L1 += dist(tour1[i-1],tour1[i]) dE = L1-L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *= 0.9# lower the temperature print(tour) | # 6331008721 221 (2020-09-13 20:17) %diff = 0.0 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.001 : # while not finished # create a new tour from the current tour r = random.random() if r < 0.5: # always false i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else: # prob = 0.5 a = random.randint(0, N-5) b = random.randint(a+1, N-3) c = random.randint(b+1, N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 =0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *= 0.9999 # lower the temperature print(tour) | # 6331407421 300 (2020-09-13 21:33) %diff = 0.46 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.001 : # while not finished # create a new tour from the current tour r = random.random() if r < 0.5 : i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else: a = random.randint(0,N-6) b = random.randint(a+1,N-4) c = random.randint(b+1,N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *= 0.999 # lower the temperature print(tour) | # 6330070321 115 (2020-09-13 21:58) %diff = 0.45 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.001 : # while not finished # create a new tour from the current tour r = random.random() if r<0.6: i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else: a = random.randint(0,N-6) b = random.randint(a+1,N-3) c = random.randint(b+1,N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1],tour[i]) L1 += dist(tour[i-1],tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T*=0.9999 # lower the temperature print(tour) | # 6331104221 242 (2020-09-13 22:05) %diff = 0.3 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.001 : # while not finished # create a new tour from the current tour r = random.random() if r < 0.555: i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else: #prob = 0.55 a = random.randint(0, N-5) b = random.randint(a+1, N-3) c = random.randint(b+1, N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *= 0.999 # lower the temperature print(tour) | # 6330121721 165 (2020-09-13 22:10) %diff = 0.15 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.001 : # while not finished # create a new tour from the current tour r = random.random() if r < 0.26: i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else : a = random.randint(0,N-5) b = random.randint(a+1,N-3) c = random.randint(b+1,N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 = 0 for i in range(N): L0 +=dist(tour[i-1],tour[i]) L1 +=dist(tour1[i-1],tour1[i]) dE = L1-L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *=0.9999 # lower the temperature print(tour) | # 6331017321 230 (2020-09-13 22:13) %diff = 0.75 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T> 0.0001 : # while not finished # create a new tour from the current tour r=random.random() if r < 0.5: #always false i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else: # prob = 0.5 a = random.randint(0, N-5) b = random.randint(a+1, N-3) c = random.randint(b+1, N-2) d = c+1 tour1 = tour[ :a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < (math.exp(-dE/T)) : tour = tour1 T = 0.9999*T # lower the temperature print(tour) | # 6331109421 246 (2020-09-13 22:20) %diff = 1.49 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.000000001 : # while not finished # create a new tour from the current tour r = random.random() if r < 0.5 : #always false i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else : #prob = 0.5 a = random.randiant(0, N-5) b = random.randiant(a+1, N-3) c = random.randiant(b+1, N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 = 0 for i in range(N) : L0 += dist(tour[i-1], tour[i]) L1 += dist(tour[i-1], tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *= 0.9999 # lower the temperature print(tour) | # 6331112221 248 (2020-09-13 22:20) %diff = 0.3 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.0001 : # while not finished # create a new tour from the current tour r = random.random() if r < 0.5: # always false i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else: # prob = 0.5 a = random.randint(0, N-5) b = random.randint(a+1, N-3) c = random.randint(b+1, N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1],tour[i]) L1 += dist(tour1[i-1],tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *= 0.999 # lower the temperature print(tour) | # 6331012121 225 (2020-09-13 22:34) %diff = 0.76 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T>0.001: # while not finished # create a new tour from the current tour r = random.random() if r < 0.1: i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 – length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else : a = random.randint(0,N-5) b = random.randint(a+1,N-3) c = random.randint(b+1,N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1],tour[i]) L1 += dist(tour1[i-1],tour1[i]) dE = L1-L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T = 0.999548*T # lower the temperature print(tour) | # 6331209521 276 (2020-09-13 22:34) %diff = 0.45 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.0001 : # while not finished # create a new tour from the current tour r = random.random() if r < 0.5: i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else: a = random.randint(0, N-4) b = random.randint(a+1, N-3) c = random.randint(b+1, N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T): tour = tour1 T *= 0.99992 # lower the temperature print(tour) | # 6231013721 25 (2020-09-13 22:44) %diff = 0.3 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.001 : # while not finished # create a new tour from the current tour r = random.random() if r < 0.25: i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 – length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else: a = random.randint(0, N-5) b = random.randint(a+1, N-3) c = random.randint(b+1, N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *= 0.999 # lower the temperature print(tour) | # 6231128221 45 (2020-09-13 23:02) %diff = 0.9 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.00001 : # while not finished # create a new tour from the current tour r = random.random() if r < 0.8: i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else: # prob = 0.2 a = random.randint(0,N-5) b = random.randint(a+1,N-2) c = random.randint(b+1,N) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *= 0.9999 # lower the temperature print(tour) | # 6230585121 16 (2020-09-13 23:21) %diff = 0.15 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.001 : # while not finished # create a new tour from the current tour r = random.random() if r < 0.3: i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else: a = random.randint(0, N-5) b = random.randint(a+1, N-3) c = random.randint(b+1, N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *= 0.9999 # lower the temperature print(tour) | # 6330125221 168 (2020-09-13 23:36) %diff = 0.61 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T >0.0001 : # while not finished # create a new tour from the current tour r= random.random() if r<0.7: i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else: a = random.randint(0,N-6) b = random.randint(a+1,N-4) c = random.randint(b+1,N-2) d = c+1 tour1= tour[:a+1]+tour[b:c+1]+tour[a+1:b]+tour[d:] L0=L1=0 for i in range(N): L0 += dist(tour[i-1],tour[i]) L1 += dist(tour1[i-1],tour1[i]) dE = L1-L0 # accept new tour if shorter or within prob. if dE<0 or random.random()<math.exp(-dE/T) : tour = tour1 T *= 0.9999 # lower the temperature print(tour) | # 6330025121 74 (2020-09-13 23:57) %diff = 1.51 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 10**(-225) : # while not finished # create a new tour from the current tour r = random.random() if r < 0.5 : i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else: #prob = 0.5 a = random.randint(0,N-5) b = random.randint(a+1,N-3) c = random.randint(b+1,N-2) d = c+1 tour1 = tour[:a+1]+tour[b:c+1]+tour[a+1:b]+tour[d:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1-L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *= 0.99 # lower the temperature print(tour) |
_main_: cluster #6 (2)
| # 6331137021 270 (2020-09-13 23:15) %diff = 0.0 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*100 # starting temperature while T > 0.001 : # while not finished # create a new tour from the current tour r = random.random() dE = 0 if r< 0.5:# i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else: # prob = 0.5 a = random.randint(0, N-5) b = random.randint(a+1, N-3) c = random.randint(b+1, N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour[i-1], tour1[i]) de = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-N*100/T) : tour = tour1 T *= 0.9999 # lower the temperature # keep tour changes in tour_log loop += 1 if loop % N == 0: tour_log += [[T, tour]] tour_log += [[T, tour]] # the final tour print(tour) animate(X, Y, tour_log[-1000:] ) # let's animate | # 6331113921 249 (2020-09-13 23:34) %diff = 0.0 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*100 # starting temperature while T > 0.001 : # while not finished # create a new tour from the current tour r = random.random() dE = 0 if r< 0.5:# i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else: # prob = 0.5 a = random.randint(0, N-5) b = random.randint(a+1, N-3) c = random.randint(b+1, N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour[i-1], tour1[i]) de = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-N*100/T) : tour = tour1 T *= 0.9999 # lower the temperature # keep tour changes in tour_log loop += 1 if loop % N == 0: tour_log += [[T, tour]] tour_log += [[T, tour]] # the final tour print(tour) animate(X, Y, tour_log[-1000:] ) # let's animate |
_main_: cluster #7 (3)
| # 6331401621 296 (2020-09-13 20:10) %diff = 0.0 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T >= 0.0001: # while not finished g = random.random() # create a new tour from the current tour if g < 0.01: x = random.randint(0, N-2) y = random.randint(x+1, N-1) tour1 = list(tour) # copy list tour1[x], tour1[y] = tour1[y], tour1[x] # swap # compute dE = length_of_tour1,length_of_tour dE = dist(tour1[x-1], tour1[x ]) + \ dist(tour1[x ], tour1[x+1 ]) + \ dist(tour1[y-1], tour1[y ]) + \ dist(tour1[y ], tour1[(y+1)%N]) - \ dist(tour[ x-1], tour[ x ]) - \ dist(tour[ x ], tour[ x+1 ]) - \ dist(tour[ y-1], tour[ y ]) - \ dist(tour[ y ], tour[(y+1)%N ]) elif g < 0.03: x = random.randint(0, N-2) y = random.randint(x+1, N-1) tour1 = tour[:x+1] + [tour[y]] + tour[x+1:y] + tour[y+1:] dE = dist(tour[x], tour[y]) + \ dist(tour[y], tour[x+1]) + \ dist(tour[y-1], tour[(y+1)%N]) - \ dist(tour[x], tour[x+1]) - \ dist(tour[y-1], tour[y]) - \ dist(tour[y], tour[(y+1)%N ]) elif g < 0.05: x = random.randint(0, N-3) y = random.randint(x+1, N-2) z = random.randint(y+1, N-1) tour1 = tour[:x+1] + tour[y:z+1] + tour[x+1:y] + tour[z+1:] dE = dist(tour[x], tour[y]) + \ dist(tour[z], tour[x+1]) + \ dist(tour[y-1], tour[(z+1)%N]) - \ dist(tour[x], tour[x+1]) - \ dist(tour[y-1], tour[y]) - \ dist(tour[z], tour[(z+1)%N ]) elif g < 0.07: x = random.randint(0, N-2) y = random.randint(x+1, N-1) z = tour[x:y+1] tour1 = tour[:x] + z[::-1] + tour[y+1:] dE = dist(tour[x-1], tour[y]) + \ dist(tour[x], tour[(y+1)%N]) - \ dist(tour[x-1], tour[x]) - \ dist(tour[y], tour[(y+1)%N ]) else: w = random.randint(0, N-4) x = random.randint(w+1, N-3) y = random.randint(x+1, N-2) z = random.randint(y+1, N-1) tour1 = tour[:w] + tour[y:z+1] + tour[x+1:y] + tour[w:x+1] + tour[z+1:] dE = dist(tour[w-1], tour[y]) + \ dist(tour[z], tour[x+1]) + \ dist(tour[y-1], tour[w]) + \ dist(tour[x], tour[(z+1)%N]) - \ dist(tour[w-1], tour[w]) - \ dist(tour[x], tour[x+1]) - \ dist(tour[y-1], tour[y]) - \ dist(tour[z], tour[(z+1)%N ]) # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *= (0.99999) # lower the temperature print(tour) | # 6331510321 318 (2020-09-13 22:19) %diff = 0.2 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T >= 0.0001: # while not finished K = random.random() # create a new tour from the current tour if K < 0.01: x = random.randint(0, N-2) y = random.randint(x+1, N-1) tour1 = list(tour) # copy list tour1[x], tour1[y] = tour1[y], tour1[x] # swap # compute dE = length_of_tour1,length_of_tour dE = dist(tour1[x-1], tour1[x ]) + \ dist(tour1[x ], tour1[x+1 ]) + \ dist(tour1[y-1], tour1[y ]) + \ dist(tour1[y ], tour1[(y+1)%N]) - \ dist(tour[ x-1], tour[ x ]) - \ dist(tour[ x ], tour[ x+1 ]) - \ dist(tour[ y-1], tour[ y ]) - \ dist(tour[ y ], tour[(y+1)%N ]) elif K < 0.04: x = random.randint(0, N-2) y = random.randint(x+1, N-1) tour1 = tour[:x+1] + [tour[y]] + tour[x+1:y] + tour[y+1:] dE = dist(tour[x], tour[y]) + \ dist(tour[y], tour[x+1]) + \ dist(tour[y-1], tour[(y+1)%N]) - \ dist(tour[x], tour[x+1]) - \ dist(tour[y-1], tour[y]) - \ dist(tour[y], tour[(y+1)%N ]) elif K < 0.06: x = random.randint(0, N-3) y = random.randint(x+1, N-2) z = random.randint(y+1, N-1) tour1 = tour[:x+1] + tour[y:z+1] + tour[x+1:y] + tour[z+1:] dE = dist(tour[x], tour[y]) + \ dist(tour[z], tour[x+1]) + \ dist(tour[y-1], tour[(z+1)%N]) - \ dist(tour[x], tour[x+1]) - \ dist(tour[y-1], tour[y]) - \ dist(tour[z], tour[(z+1)%N ]) elif K < 0.08: x = random.randint(0, N-2) y = random.randint(x+1, N-1) z = tour[x:y+1] tour1 = tour[:x] + z[::-1] + tour[y+1:] dE = dist(tour[x-1], tour[y]) + \ dist(tour[x], tour[(y+1)%N]) - \ dist(tour[x-1], tour[x]) - \ dist(tour[y], tour[(y+1)%N ]) else: w = random.randint(0, N-4) x = random.randint(w+1, N-3) y = random.randint(x+1, N-2) z = random.randint(y+1, N-1) tour1 = tour[:w] + tour[y:z+1] + tour[x+1:y] + tour[w:x+1] + tour[z+1:] dE = dist(tour[w-1], tour[y]) + \ dist(tour[z], tour[x+1]) + \ dist(tour[y-1], tour[w]) + \ dist(tour[x], tour[(z+1)%N]) - \ dist(tour[w-1], tour[w]) - \ dist(tour[x], tour[x+1]) - \ dist(tour[y-1], tour[y]) - \ dist(tour[z], tour[(z+1)%N ]) # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *= (0.99999) # lower the temperature print(tour) | # 6330099621 143 (2020-09-13 23:45) %diff = 0.0 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T >= 0.0001: # while not finished g = random.random() # create a new tour from the current tour if g < 0.01: x = random.randint(0, N-2) y = random.randint(x+1, N-1) tour1 = list(tour) # copy list tour1[x], tour1[y] = tour1[y], tour1[x] # swap # compute dE = length_of_tour1,length_of_tour dE = dist(tour1[x-1], tour1[x ]) + \ dist(tour1[x ], tour1[x+1 ]) + \ dist(tour1[y-1], tour1[y ]) + \ dist(tour1[y ], tour1[(y+1)%N]) - \ dist(tour[ x-1], tour[ x ]) - \ dist(tour[ x ], tour[ x+1 ]) - \ dist(tour[ y-1], tour[ y ]) - \ dist(tour[ y ], tour[(y+1)%N ]) elif g < 0.03: x = random.randint(0, N-2) y = random.randint(x+1, N-1) tour1 = tour[:x+1] + [tour[y]] + tour[x+1:y] + tour[y+1:] dE = dist(tour[x], tour[y]) + \ dist(tour[y], tour[x+1]) + \ dist(tour[y-1], tour[(y+1)%N]) - \ dist(tour[x], tour[x+1]) - \ dist(tour[y-1], tour[y]) - \ dist(tour[y], tour[(y+1)%N ]) elif g < 0.05: x = random.randint(0, N-3) y = random.randint(x+1, N-2) z = random.randint(y+1, N-1) tour1 = tour[:x+1] + tour[y:z+1] + tour[x+1:y] + tour[z+1:] dE = dist(tour[x], tour[y]) + \ dist(tour[z], tour[x+1]) + \ dist(tour[y-1], tour[(z+1)%N]) - \ dist(tour[x], tour[x+1]) - \ dist(tour[y-1], tour[y]) - \ dist(tour[z], tour[(z+1)%N ]) elif g < 0.07: x = random.randint(0, N-2) y = random.randint(x+1, N-1) z = tour[x:y+1] tour1 = tour[:x] + z[::-1] + tour[y+1:] dE = dist(tour[x-1], tour[y]) + \ dist(tour[x], tour[(y+1)%N]) - \ dist(tour[x-1], tour[x]) - \ dist(tour[y], tour[(y+1)%N ]) else: w = random.randint(0, N-4) x = random.randint(w+1, N-3) y = random.randint(x+1, N-2) z = random.randint(y+1, N-1) tour1 = tour[:w] + tour[y:z+1] + tour[x+1:y] + tour[w:x+1] + tour[z+1:] dE = dist(tour[w-1], tour[y]) + \ dist(tour[z], tour[x+1]) + \ dist(tour[y-1], tour[w]) + \ dist(tour[x], tour[(z+1)%N]) - \ dist(tour[w-1], tour[w]) - \ dist(tour[x], tour[x+1]) - \ dist(tour[y-1], tour[y]) - \ dist(tour[z], tour[(z+1)%N ]) # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *= (0.99999) # lower the temperature print(tour) |
_main_: cluster #8 (2)
| # 6330028021 77 (2020-09-13 20:50) %diff = 0.0 map_name = str(input()) X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] # --- let's the SA begins -------------- loop = 0 T = N * 10 # starting temperature while T > 0.0001: # while not finished # create a new tour from the current tour if N <= 38: r = random.random() if r < 0.9: i = random.randint(0, N - 2) j = random.randint(i + 1, N - 1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i - 1], tour1[i]) + \ dist(tour1[i], tour1[i + 1]) + \ dist(tour1[j - 1], tour1[j]) + \ dist(tour1[j], tour1[(j + 1) % N]) - \ dist(tour[i - 1], tour[i]) - \ dist(tour[i], tour[i + 1]) - \ dist(tour[j - 1], tour[j]) - \ dist(tour[j], tour[(j + 1) % N]) else: a = random.randint(0, N - 5) b = random.randint(a + 1, N - 3) c = random.randint(b + 1, N - 2) d = c + 1 tour1 = tour[:a + 1] + tour[b:c + 1] + tour[a + 1:b] + tour[d:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i - 1], tour[i]) L1 += dist(tour1[i - 1], tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.e ** (-dE / T): tour = tour1 T = 0.99999 * T else: T = 0.99999 * T # lower the temperature else: r = random.random() if r < 0.15 and T>0.01: i = random.randint(0, N - 2) j = random.randint(i + 1, N - 1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap dE = dist(tour1[i - 1], tour1[i]) + \ dist(tour1[i], tour1[i + 1]) + \ dist(tour1[j - 1], tour1[j]) + \ dist(tour1[j], tour1[(j + 1) % N]) - \ dist(tour[i - 1], tour[i]) - \ dist(tour[i], tour[i + 1]) - \ dist(tour[j - 1], tour[j]) - \ dist(tour[j], tour[(j + 1) % N]) elif r < 0.85 and T>0.01: a = random.randint(0, N-4) b = random.randint(a+1, N-3) c = random.randint(b+1, N-2) tour1 = list(tour[:a]) tour1 = tour1 + list(tour[b:c+1]) tour1 = tour1 + list(tour[a:b]) tour1 = tour1 + list(tour[c+1:]) dE = dist(tour[c], tour[a]) + \ dist(tour[b-1], tour[c+1]) + \ dist(tour[b], tour[a-1]) - \ dist(tour[a-1], tour[a]) - \ dist(tour[b-1], tour[b]) - \ dist(tour[c], tour[c+1]) else: a = random.randint(0, N - 2) b = random.randint(a + 1, N - 1) tour1 = list(tour[:a]) tour1 = tour1 + list(tour[a+1:b+1]) tour1 = tour1 + list(tour[a:a+1]) tour1 = tour1 + list(tour[b+1:]) dE = dist(tour[a+1], tour[a-1]) + \ dist(tour[b], tour[a]) + \ dist(tour[a], tour[(b+1)%N]) - \ dist(tour[a - 1], tour[a]) - \ dist(tour[a], tour[a+1]) - \ dist(tour[b], tour[(b+1)%N]) if dE < 0 or random.random() < math.e ** (-dE*2/T): tour = tour1 T=0.99999*T else : T=0.99999*T # lower the temperature print(tour) # let's animate | # 6330141221 182 (2020-09-13 20:57) %diff = 0.0 map_name = str(input()) X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] # --- let's the SA begins -------------- loop = 0 T = N * 10 # starting temperature while T > 0.0001: # while not finished # create a new tour from the current tour if N <= 38: r = random.random() if r < 0.9: i = random.randint(0, N - 2) j = random.randint(i + 1, N - 1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i - 1], tour1[i]) + \ dist(tour1[i], tour1[i + 1]) + \ dist(tour1[j - 1], tour1[j]) + \ dist(tour1[j], tour1[(j + 1) % N]) - \ dist(tour[i - 1], tour[i]) - \ dist(tour[i], tour[i + 1]) - \ dist(tour[j - 1], tour[j]) - \ dist(tour[j], tour[(j + 1) % N]) else: a = random.randint(0, N - 5) b = random.randint(a + 1, N - 3) c = random.randint(b + 1, N - 2) d = c + 1 tour1 = tour[:a + 1] + tour[b:c + 1] + tour[a + 1:b] + tour[d:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i - 1], tour[i]) L1 += dist(tour1[i - 1], tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.e ** (-dE / T): tour = tour1 T = 0.99999 * T else: T = 0.99999 * T # lower the temperature else: r = random.random() if r < 0.15 and T>0.01: i = random.randint(0, N - 2) j = random.randint(i + 1, N - 1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap dE = dist(tour1[i - 1], tour1[i]) + \ dist(tour1[i], tour1[i + 1]) + \ dist(tour1[j - 1], tour1[j]) + \ dist(tour1[j], tour1[(j + 1) % N]) - \ dist(tour[i - 1], tour[i]) - \ dist(tour[i], tour[i + 1]) - \ dist(tour[j - 1], tour[j]) - \ dist(tour[j], tour[(j + 1) % N]) elif r < 0.85 and T>0.01: a = random.randint(0, N-4) b = random.randint(a+1, N-3) c = random.randint(b+1, N-2) tour1 = list(tour[:a]) tour1 = tour1 + list(tour[b:c+1]) tour1 = tour1 + list(tour[a:b]) tour1 = tour1 + list(tour[c+1:]) dE = dist(tour[c], tour[a]) + \ dist(tour[b-1], tour[c+1]) + \ dist(tour[b], tour[a-1]) - \ dist(tour[a-1], tour[a]) - \ dist(tour[b-1], tour[b]) - \ dist(tour[c], tour[c+1]) else: a = random.randint(0, N - 2) b = random.randint(a + 1, N - 1) tour1 = list(tour[:a]) tour1 = tour1 + list(tour[a+1:b+1]) tour1 = tour1 + list(tour[a:a+1]) tour1 = tour1 + list(tour[b+1:]) dE = dist(tour[a+1], tour[a-1]) + \ dist(tour[b], tour[a]) + \ dist(tour[a], tour[(b+1)%N]) - \ dist(tour[a - 1], tour[a]) - \ dist(tour[a], tour[a+1]) - \ dist(tour[b], tour[(b+1)%N]) if dE < 0 or random.random() < math.e ** (-dE*2/T): tour = tour1 T=0.99999*T else : T=0.99999*T # lower the temperature print(tour) # let's animate |
_main_: cluster #9 (4)
| # 6330103421 147 (2020-09-13 22:23) %diff = 0.0 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.0001: # while not finished # create a new tour from the current tour tour1 = list(tour) r = random.random() if r <= 0.1: i = random.randint(0,N-2) #a, i+1=b j = random.randint(i+1,N-1) #x tour1 = tour1[:i+1]+tour1[j:j+1:]+tour1[i+1:j:]+tour1[j+1::] dE = dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[i+1], tour1[(i+2)%N]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) elif r <= 0.3: i = random.randint(0,N-3) #a j = random.randint(i+1,N-2) #b k = random.randint(j+1,N-1) #c, j+1=d tour1 = tour1[:i+1]+tour1[j:k+1:]+tour1[i+1:j]+tour1[k+1:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r <= 0.8: i = random.randint(0,N-2) #a j = random.randint(i+1,N-1) #b tour1 = tour1[:i] + tour1[j:i:-1] + tour1[i:i+1] + tour1[j+1:] L0 = L1 = 0 dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ j ], tour[ (j+1)%N]) elif r <= 0.9: i = random.randint(0,N-4) #a j = random.randint(i+1,N-3) #b k = random.randint(j+1,N-2) #c l = random.randint(k+1,N-1) #d tour1 = tour1[:i]+tour1[k:l+1]+tour1[j+1:k]+tour1[i:j+1]+tour1[l+1::] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r <= 1 : i = random.randint(0,N-2) #a j = random.randint(i+1,N-1) #b tour1[i],tour1[j] = tour1[j],tour1[i] dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) # accept new tour if shorter or within prob. a = random.random() if dE < 0 or a < math.exp(-dE/T) : tour = tour1 T *= 0.9999 # lower the temperature # keep tour changes in tour_log loop += 1 if loop % N == 0: tour_log += [[T, tour]] tour_log += [[T, tour]] # the final tour print(tour) animate(X, Y, tour_log[-1:] ) # let's animate | # 6330002721 51 (2020-09-13 22:56) %diff = 0.65 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.00001: # while not finished # create a new tour from the current tour tour1 = list(tour) s = random.random() if s <= 0.1: i = random.randint(0,N-2) #a, i+1=b j = random.randint(i+1,N-1) #x tour1 = tour1[:i+1]+tour1[j:j+1:]+tour1[i+1:j:]+tour1[j+1::] dE = dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[i+1], tour1[(i+2)%N]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) elif s <= 0.3: i = random.randint(0,N-3) #a j = random.randint(i+1,N-2) #b k = random.randint(j+1,N-1) #c, j+1=d tour1 = tour1[:i+1]+tour1[j:k+1:]+tour1[i+1:j]+tour1[k+1:] A = B = 0 for i in range(N): A += dist(tour[i-1], tour[i]) B += dist(tour1[i-1], tour1[i]) dE = B - A elif s <= 0.8: i = random.randint(0,N-2) j = random.randint(i+1,N-1) tour1 = tour1[:i] + tour1[j:i:-1] + tour1[i:i+1] + tour1[j+1:] A = B = 0 dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ j ], tour[ (j+1)%N]) elif s <= 0.9: i = random.randint(0,N-4) j = random.randint(i+1,N-3) k = random.randint(j+1,N-2) l = random.randint(k+1,N-1) tour1 = tour1[:i]+tour1[k:l+1]+tour1[j+1:k]+tour1[i:j+1]+tour1[l+1::] A = B = 0 for i in range(N): A += dist(tour[i-1], tour[i]) B += dist(tour1[i-1], tour1[i]) dE = B - A elif s <= 1 : i = random.randint(0,N-2) j = random.randint(i+1,N-1) tour1[i],tour1[j] = tour1[j],tour1[i] dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) # accept new tour if shorter or within prob. s = random.random() if dE < 0 or s < math.exp(-dE/T) : tour = tour1 T *= 0.9999 # lower the temperature # keep tour changes in tour_log loop += 1 if loop % N == 0: tour_log += [[T, tour]] tour_log += [[T, tour]] # the final tour print(tour) animate(X, Y, tour_log[-1:] ) # let's animate | # 6330086421 130 (2020-09-13 23:09) %diff = 0.0 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.0001: # while not finished # create a new tour from the current tour tour1 = list(tour) r = random.random() if r <= 0.1: i = random.randint(0,N-2) #a, i+1=b j = random.randint(i+1,N-1) #x tour1 = tour1[:i+1]+tour1[j:j+1:]+tour1[i+1:j:]+tour1[j+1::] dE = dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[i+1], tour1[(i+2)%N]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) elif r <= 0.3: i = random.randint(0,N-3) #a j = random.randint(i+1,N-2) #b k = random.randint(j+1,N-1) #c, j+1=d tour1 = tour1[:i+1]+tour1[j:k+1:]+tour1[i+1:j]+tour1[k+1:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r <= 0.8: i = random.randint(0,N-2) #a j = random.randint(i+1,N-1) #b tour1 = tour1[:i] + tour1[j:i:-1] + tour1[i:i+1] + tour1[j+1:] L0 = L1 = 0 dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ j ], tour[ (j+1)%N]) elif r <= 0.9: i = random.randint(0,N-4) #a j = random.randint(i+1,N-3) #b k = random.randint(j+1,N-2) #c l = random.randint(k+1,N-1) #d tour1 = tour1[:i]+tour1[k:l+1]+tour1[j+1:k]+tour1[i:j+1]+tour1[l+1::] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r <= 1 : i = random.randint(0,N-2) #a j = random.randint(i+1,N-1) #b tour1[i],tour1[j] = tour1[j],tour1[i] dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) # accept new tour if shorter or within prob. a = random.random() if dE < 0 or a < math.exp(-dE/T) : tour = tour1 T *= 0.9999 # lower the temperature # keep tour changes in tour_log loop += 1 if loop % N == 0: tour_log += [[T, tour]] tour_log += [[T, tour]] # the final tour print(tour) animate(X, Y, tour_log[-1:] ) # let's animate | # 6330107021 151 (2020-09-13 23:58) %diff = 0.51 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.001: # while not finished # create a new tour from the current tour tour1+list(tour) r = random.random() if r<=0.1: i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = tour1[:i+1]+tour1[j:j+1:]+tour1[i+1:j:]+tour1[j+1::] dE = dist(tour1[i], tour1[i+1 ]) + \ dist(tour1[i+1], tour1[(i+2)%N]) + \ dist(tour1[j], tour1[(j+1)%N ]) + \ dist(tour1[i ], tour1[i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[ (j+1)%N]) elif r<=0.3: i=random.randint(0,N-3)#a j=random.randint(i+1,N-2)#b k=random.randint(j+1,N-1)#c,j+1=d tour1=tour1[:i+1]+tour1[j:k+1:]+tour1[i+1:j]+tour1[k+1:] L0=L1=0 for i in range(N): L0 +=dist(tour[i-1],tour[i]) L1 +=dist(tour1[i-1],tour1[i]) dE=L1-L0 elif r<=0.8: i=random.randint(0,N-2)#a j=random.randint(i+1,N-1)#b tour1=tour1[:i]+tour1[j:i:-1]+tour1[i:i+1]+tour1[j+1:] L0=L1=0 dE=dist(tour[i-1],tour1[i])+\ dist(tour1[j],tour1[(j+1)%N])-\ dist(tour[i-1],tour[i])-\ dist(tour[j],tour[(j+1)%N]) elif r<=0.9: i=random.randint(0,N-4)#a j=random.randint(i+1,N-3)#b k=random.randint(j+1,N-2)#c l=random.randint(k+1,N-1)#d tour1=tour1[:i]+tour1[k:l+1]+tour1[j+1:k]+tour1[i:j+1]+tour1[l+1::] L0=L1=0 for i in range(N): L0 +=dist(tour[i-1],tour[i]) L1 +=dist(tour1[i-1],tour1[i]) dE=L1-L0 elif r<=1: i=random.randint(0,N-2)#a j=random.randint(i+1,N-1)#b tour1[i],tour1[j]=tour1[j],tour1[i] dE=dist(tour1[i-1],tour1[i])+\ dist(tour1[i],tour1[i+1])+\ dist(tour1[j-1],tour1[j])+\ dist(tour1[j],tour1[(j+1)%N])-\ dist(tour[i-1],tour[i])-\ dist(tour[i],tour[i+1])-\ dist(tour[j-1],tour[j])-\ dist(tour[j],tour[(j+1)%N]) # accept new tour if shorter or within prob. a=random.random() if dE<0 or a<math.exp(-dE/T) : tour = tour1 T*=0.9999 # lower the temperature # keep tour changes in tour_log loop += 1 if loop % N == 0: tour_log += [[T, tour]] tour_log += [[T, tour]] # the final tour print(tour) animate(X, Y, tour_log[-1:] ) # let's animate |
_main_: cluster #10 (3)
| # 6330095021 139 (2020-09-13 23:43) %diff = 0.0 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.0001 : # while not finished # create a new tour from the current tour rannn = random.randint(0, 1) if rannn == 0: i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap elif rannn == 1: i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) tourA = tour1[:i+1] tourB = tour1[i+1:j] tourC = tour1[j] tourD = tour1[j+1:] tour1 = tourA + [tourC] + tourB + tourD # compute dE = length_of_tour1 โ€“ length_of_tour if rannn == 0: dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) elif rannn == 1: dE = dist(tour1[i], tour1[i+1]) + \ dist(tour1[i+1], tour1[(i+2)%N]) + \ dist(tour1[j], tour1[(j+1)%N]) - \ dist(tour[i], tour[i+1]) - \ dist(tour[j-1], tour[j]) - \ dist(tour[j], tour[(j+1)%N]) # accept new tour if shorter or within prob. if (dE < 0) or random.random() < math.exp(-dE/T) : tour = tour1 T *= 0.9999 # lower the temperature print(tour) | # 6330167621 205 (2020-09-13 23:58) %diff = 0.0 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] # --- let's the SA begins -------------- loop = 0 T = N * 10 # starting temperature while T > 0.0001: # while not finished # create a new tour from the current tour da = random.randint(0, 1) if da == 0: i = random.randint(0, N - 2) j = random.randint(i + 1, N - 1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap elif da == 1: i = random.randint(0, N - 2) j = random.randint(i + 1, N - 1) tour1 = list(tour) tour1_1 = tour1[:i + 1] tour1_2 = tour1[i + 1:j] tour1_3 = tour1[j] tour1_4 = tour1[j + 1:] tour1 = tour1_1 + [tour1_3] + tour1_2 + tour1_4 #elif da == 2: #i = random.randint(0, N-5) #j = random.randint(i+1, N-3) #k = random.randint(j+1, N-2) # l = k+1 #tour1 = list(tour) #tour1_1 = tour1[:i+1] # tour1_2 = tour1[i+1:j] # tour1_3 = tour1[j:k+1] # tour1_4 = tour1[l:] #tour1 = tour1_1 + tour1_3 + tour1_2 + tour1_4 #elif da == 3: #i = random.randint(0, N-2) #j = random.randint(i+1, N-1) #tour1 = list(tour) #tour1_1 = tour1[:i] #tour1_2 = tour1[i:j+1] #tour1_3 = tour1[j+1:] #tour1_4 = tour1_2[::-1] #tour1 = tour1_1 + tour1_4 + tour1_3 # elif da == 3: #i = random.randint(0, N - 4) # j = random.randint(i + 1, N - 3) #k = random.randint(j + 1, N - 2) #l = random.randint(k + 1, N - 1) #tour1 = list(tour) #tour1_1 = tour1[:i] #tour1_2 = tour1[i:j + 1] #tour1_3 = tour1[j + 1:k] # tour1_4 = tour1[k:l+1] #tour1_5 = tour1[l+1:] #tour1 = tour1_1 + tour1_4 + tour1_3 + tour1_2 + tour1_5 # compute dE = length_of_tour1 โ€“ length_of_tour if da == 0: dE = dist(tour1[i - 1], tour1[i]) + \ dist(tour1[i], tour1[i + 1]) + \ dist(tour1[j - 1], tour1[j]) + \ dist(tour1[j], tour1[(j + 1) % N]) - \ dist(tour[i - 1], tour[i]) - \ dist(tour[i], tour[i + 1]) - \ dist(tour[j - 1], tour[j]) - \ dist(tour[j], tour[(j + 1) % N]) elif da == 1: dE = dist(tour1[i], tour1[i + 1]) + \ dist(tour1[i + 1], tour1[(i + 2) % N]) + \ dist(tour1[j], tour1[(j + 1) % N]) - \ dist(tour[i], tour[i + 1]) - \ dist(tour[j - 1], tour[j]) - \ dist(tour[j], tour[(j + 1) % N]) # elif da == 2: #dE = dist(tour1[i], tour1[i+1]) + \ # dist(tour1[j], tour1[j+1]) + \ #dist(tour1[k], tour1[l]%N) - \ # dist(tour[i], tour[i+1]) - \ # dist(tour[j-1], tour[j]) - \ #dist(tour[k], tour[l]%N) #elif da == 3: # accept new tour if shorter or within prob. if (dE < 0) or random.random() < math.exp(-dE / T): tour = tour1 T *= 0.9999 # lower the temperature print(tour) | # 6330094421 138 (2020-09-13 23:59) %diff = 0.13 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] # --- let's the SA begins -------------- loop = 0 T = N * 10 # starting temperature while T > 0.0001: # while not finished # create a new tour from the current tour rannum = random.randint(0, 3) if rannum == 0: i = random.randint(0, N - 2) j = random.randint(i + 1, N - 1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap elif rannum == 1: i = random.randint(0, N - 2) j = random.randint(i + 1, N - 1) tour1 = list(tour) tour11 = tour1[:i + 1] tour12 = tour1[i + 1:j] tour13 = tour1[j] tour14 = tour1[j + 1:] tour1 = tour11 + [tour13] + tour12 + tour14 # elif rannum == 2: # i = random.randint(0, N - 5) # j = random.randint(i + 1, N - 3) # k = random.randint(j + 1, N - 2) # l = k + 1 # # tour1 = list(tour) # tour11 = tour1[:i + 1] # tour12 = tour1[i + 1:j] # tour13 = tour1[j:k + 1] # tour14 = tour1[l:] # # tour1 = tour11 + tour13 + tour12 + tour14 # elif rannum == 4: # i = random.randint(0, N - 2) # j = random.randint(i + 1, N - 1) # # tour1 = list(tour) # tour11 = tour1[:i] # tour12 = tour1[i:j + 1] # tour13 = tour1[j + 1:] # tour14 = tour12[::-1] # # tour1 = tour11 + tour14 + tour13 # # reverse doesn't do anything better than swapping a, b = b, a # elif rannum == 3: # i = random.randint(0, N - 4) # j = random.randint(i + 1, N - 3) # k = random.randint(j + 1, N - 2) # l = random.randint(k + 1, N - 1) # # tour1 = list(tour) # tour11 = tour1[:i] # tour12 = tour1[i:j + 1] # tour13 = tour1[j + 1:k] # tour14 = tour1[k:l + 1] # tour15 = tour1[l+1:] # tour1 = tour11 + tour14 + tour13 + tour12 + tour15 if rannum == 0: dE = dist(tour1[i - 1], tour1[i]) + \ dist(tour1[i], tour1[i + 1]) + \ dist(tour1[j - 1], tour1[j]) + \ dist(tour1[j], tour1[(j + 1) % N]) - \ dist(tour[i - 1], tour[i]) - \ dist(tour[i], tour[i + 1]) - \ dist(tour[j - 1], tour[j]) - \ dist(tour[j], tour[(j + 1) % N]) elif rannum == 1: dE = dist(tour1[i], tour1[i + 1]) + \ dist(tour1[i + 1], tour1[(i + 2) % N]) + \ dist(tour1[j], tour1[(j + 1) % N]) - \ dist(tour[i], tour[i + 1]) - \ dist(tour[j - 1], tour[j]) - \ dist(tour[j], tour[(j + 1) % N]) # elif rannum == 2: # dE = dist(tour1[i], tour1[i+1]) + \ # dist(tour1[j], tour1[j+1]) + \ # dist(tour1[k], tour1[l]) - \ # dist(tour[i], tour[i+1]) - \ # dist(tour[j-1], tour[j]) - \ # dist(tour[k], tour[l]) # elif rannum == 3: # dE = dist(tour1[i-1], tour1[i]) + \ # dist(tour1[j-1], tour1[j]) + \ # dist(tour1[j], tour1[j+1]) + \ # dist(tour1[l], tour1[(l+1)%N]) - \ # dist(tour1[i-1], tour1[i]) - \ # dist(tour[j], tour[j+1]) - \ # dist(tour[l], tour[(l+1)%N]) # accept new tour if shorter or within prob. if (dE < 0) or random.random() < math.exp(-dE / T): tour = tour1 T *= 0.9999 # lower the temperature print(tour) |
_main_: cluster #11 (2)
| # 6231117321 40 (2020-09-13 23:07) %diff = 0.08 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while (T > 0.02**(N//170+1)): # while not finished # create a new tour from the current tour r = random.random() s = 0 s2 = N//2 s3 = N//3 if (r < 0.7): i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap elif (T < 2): i = s%N j = random.randint(0, N-2) k = s2%N l = random.randint(k+1, N-2) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap tour1[k], tour1[l] = tour1[k], tour1[l] s += 1 s2 += 1 elif (r < 0.8): i = random.randint(0, N-2) j = random.randint(i+1, N-1) k = random.randint(j+1, N) tour1 = tour[:i+1]+tour[j:k+1]+tour[i+1:j]+tour[k+1:] elif (r < 0.9): i = random.randint(1, N-2) j = random.randint(i+1, N-1) tour1 = tour[:i]+tour[j:i-1:-1]+tour[j+1:] elif (r < 1): i = random.randint(0, N//2-3) j = random.randint(i+1, N//2-2) diff = j-i+1 k = random.randint(N//2+1,N-diff) tour1 = tour[:i]+tour[k:k+diff]+tour[j+1:k]+tour[i:j+1]+tour[k+diff:] # copy list # compute dE = length_of_tour1 – length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) # accept new tour if shorter or within prob. if (dE < 0 or random.random() < math.exp(-dE/T)): tour = tour1 if (T >= 2): T *= 0.999 # lower the temperature elif (T >= 1): T *= 0.9995 elif (T >= 0.05): T *= 0.9999 else: T *= 0.99995 # keep tour changes in tour_log loop += 1 if loop % N == 0: tour_log += [[T, tour]] tour_log += [[T, tour]] # the final tour print(tour) animate(X, Y, tour_log ) # let's animate | # 6231514821 48 (2020-09-13 23:24) %diff = 0.08 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while (T > 0.02**(N//100+1)): # while not finished # create a new tour from the current tour r = random.random() s = 0 s2 = N//2 s3 = N//3 if (r < 0.7): i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap elif (T < 2): i = s%N j = random.randint(0, N-2) k = s2%N l = random.randint(k+1, N-2) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap tour1[k], tour1[l] = tour1[k], tour1[l] s += 1 s2 += 1 elif (r < 0.8): i = random.randint(0, N-2) j = random.randint(i+1, N-1) k = random.randint(j+1, N) tour1 = tour[:i+1]+tour[j:k+1]+tour[i+1:j]+tour[k+1:] elif (r < 0.9): i = random.randint(1, N-2) j = random.randint(i+1, N-1) tour1 = tour[:i]+tour[j:i-1:-1]+tour[j+1:] elif (r < 1): i = random.randint(0, N//2-3) j = random.randint(i+1, N//2-2) diff = j-i+1 k = random.randint(N//2+1,N-diff) tour1 = tour[:i]+tour[k:k+diff]+tour[j+1:k]+tour[i:j+1]+tour[k+diff:] # copy list # compute dE = length_of_tour1 – length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) # accept new tour if shorter or within prob. if (dE < 0 or random.random() < math.exp(-dE/T)): tour = tour1 if (T >= 2): T *= 0.999 # lower the temperature elif (T >= 1): T *= 0.9995 elif (T >= 0.05): T *= 0.9999 else: T *= 0.99995 # keep tour changes in tour_log loop += 1 if loop % N == 0: tour_log += [[T, tour]] tour_log += [[T, tour]] # the final tour print(tour) animate(X, Y, tour_log ) # let's animate |
_main_: cluster #12 (2)
| # 6331119721 255 (2020-09-13 18:36) %diff = 0.13 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while not( T<0.0001 ) : # while not finished # create a new tour from the current tour r = random.randint(0,1) if r <= 0.5 : i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 เน�โ�ฌโ€� length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else: a = random.randint(0,N-5) b = random.randint(a+1,N-3) c = random.randint(b+1,N-2) d = c+1 tour1 = tour[:a+1:] + tour[b:c+1:] + tour[a+1:b:] + tour[d::] L0 = 0 L1 = 0 for i in range(N): L0 += dist(tour[i-1],tour[i]) L1 += dist(tour1[i-1],tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.randint(0,1)<(math.e)**(-dE/T): tour = tour1 T = 0.9999*T # lower the temperature # keep tour changes in tour_log loop += 1 if loop % N == 0: tour_log += [[T, tour]] tour_log += [[T, tour]] # the final tour print(tour) animate(X, Y, tour_log[-1::] ) # let's animate | # 6331125421 261 (2020-09-13 23:00) %diff = 0.13 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while not( T<0.0001 ) : # while not finished # create a new tour from the current tour r = random.randint(0,1) if r <= 0.65 : i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 เนโฌโ€ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else: a = random.randint(0,N-5) b = random.randint(a+1,N-3) c = random.randint(b+1,N-2) d = c+1 tour1 = tour[:a+1:] + tour[b:c+1:] + tour[a+1:b:] + tour[d::] L0 = 0 L1 = 0 for i in range(N): L0 += dist(tour[i-1],tour[i]) L1 += dist(tour1[i-1],tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.randint(0,1)<(math.e)**(-dE/T): tour = tour1 T = 0.9999*T # lower the temperature # keep tour changes in tour_log loop += 1 if loop % N == 0: tour_log += [[T, tour]] tour_log += [[T, tour]] # the final tour print(tour) animate(X, Y, tour_log[-1::] ) # let's animate |
_main_: cluster #13 (2)
| # 6330057221 105 (2020-09-13 20:03) %diff = 0.18 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T>0.00001 : # while not finished # create a new tour from the current tour r=random.random() if r < 0.3: i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) elif r < 0.6: h = random.randint(0,N-4) k = random.randint(h+1,N-3) m = random.randint(k+1,N-2) n = random.randint(m+1,N-1) tour1 = tour[0:h]+tour[m:n+1]+tour[k+1:m]+tour[h:k+1]+tour[n+1:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1-L0 elif r < 0.7: x = random.randint(0,N-3) y = x+1 z = random.randint(y+1,N-1) tour1 = tour[0:x+1]+tour[z:z+1]+tour[y:z]+tour[z+1:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1-L0 else: a = random.randint(0,N-5) b = random.randint(a+1,N-3) c = random.randint(b+1,N-2) d = c+1 tour1 = tour[0:a+1]+tour[b:c+1]+tour[a+1:b]+tour[d:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1-L0 # accept new tour if shorter or within prob. if dE<0 or random.random() < math.exp(-dE/T): tour = tour1 T = 0.9999*T # lower the temperature print(tour) | # 6331803221 331 (2020-09-13 20:50) %diff = 0.18 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T>0.00001 : # while not finished # create a new tour from the current tour r=random.random() if r < 0.3: i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) elif r < 0.5: h = random.randint(0,N-4) k = random.randint(h+1,N-3) m = random.randint(k+1,N-2) n = random.randint(m+1,N-1) tour1 = tour[0:h]+tour[m:n+1]+tour[k+1:m]+tour[h:k+1]+tour[n+1:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1-L0 elif r < 0.6: x = random.randint(0,N-3) y = x+1 z = random.randint(y+1,N-1) tour1 = tour[0:x+1]+tour[z:z+1]+tour[y:z]+tour[z+1:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1-L0 else: a = random.randint(0,N-5) b = random.randint(a+1,N-3) c = random.randint(b+1,N-2) d = c+1 tour1 = tour[0:a+1]+tour[b:c+1]+tour[a+1:b]+tour[d:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1-L0 # accept new tour if shorter or within prob. if dE<0 or random.random() < math.exp(-dE/T): tour = tour1 T = 0.9999*T # lower the temperature print(tour) |
_main_: cluster #14 (3)
| # 6231502221 46 (2020-09-13 23:02) %diff = 0.18 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while (T > 0.02**(N//180+1)): # while not finished # create a new tour from the current tour r = random.random() s = 0 s2 = N//2 s3 = N//3 if (r < 0.7): i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap elif (T < 2): i = s%N j = random.randint(0, N-2) k = s2%N l = random.randint(k+1, N-2) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap tour1[k], tour1[l] = tour1[k], tour1[l] s += 1 s2 += 1 elif (r < 0.8): i = random.randint(0, N-2) j = random.randint(i+1, N-1) k = random.randint(j+1, N) tour1 = tour[:i+1]+tour[j:k+1]+tour[i+1:j]+tour[k+1:] elif (r < 0.9): i = random.randint(1, N-2) j = random.randint(i+1, N-1) tour1 = tour[:i]+tour[j:i-1:-1]+tour[j+1:] elif (r < 1): i = random.randint(0, N//2-3) j = random.randint(i+1, N//2-2) diff = j-i+1 k = random.randint(N//2+1,N-diff) tour1 = tour[:i]+tour[k:k+diff]+tour[j+1:k]+tour[i:j+1]+tour[k+diff:] # copy list # compute dE = length_of_tour1 – length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) # accept new tour if shorter or within prob. if (dE < 0 or random.random() < math.exp(-dE/T)): tour = tour1 if (T >= 2): T *= 0.999 # lower the temperature elif (T >= 1): T *= 0.9995 elif (T >= 0.05): T *= 0.9999 else: T *= 0.99995 print(tour) | # 6231125321 43 (2020-09-13 23:05) %diff = 0.18 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while (T > 0.02**(N//220+1)): # while not finished # create a new tour from the current tour r = random.random() s = 0 s2 = N//2 s3 = N//3 if (r < 0.7): i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap elif (T < 2): i = s%N j = random.randint(0, N-2) k = s2%N l = random.randint(k+1, N-2) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap tour1[k], tour1[l] = tour1[k], tour1[l] s += 1 s2 += 1 elif (r < 0.8): i = random.randint(0, N-2) j = random.randint(i+1, N-1) k = random.randint(j+1, N) tour1 = tour[:i+1]+tour[j:k+1]+tour[i+1:j]+tour[k+1:] elif (r < 0.9): i = random.randint(1, N-2) j = random.randint(i+1, N-1) tour1 = tour[:i]+tour[j:i-1:-1]+tour[j+1:] elif (r < 1): i = random.randint(0, N//2-3) j = random.randint(i+1, N//2-2) diff = j-i+1 k = random.randint(N//2+1,N-diff) tour1 = tour[:i]+tour[k:k+diff]+tour[j+1:k]+tour[i:j+1]+tour[k+diff:] # copy list # compute dE = length_of_tour1 – length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) # accept new tour if shorter or within prob. if (dE < 0 or random.random() < math.exp(-dE/T)): tour = tour1 if (T >= 2): T *= 0.999 # lower the temperature elif (T >= 1): T *= 0.9995 elif (T >= 0.05): T *= 0.9999 else: T *= 0.99995 print(tour) | # 6231103521 33 (2020-09-13 23:41) %diff = 0.18 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while (T > 0.02**(N//183+1)): # while not finished # create a new tour from the current tour r = random.random() s = 0 s2 = N//2 s3 = N//3 if (r < 0.7): i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap elif (T < 2): i = s%N j = random.randint(0, N-2) k = s2%N l = random.randint(k+1, N-2) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap tour1[k], tour1[l] = tour1[k], tour1[l] s += 1 s2 += 1 elif (r < 0.8): i = random.randint(0, N-2) j = random.randint(i+1, N-1) k = random.randint(j+1, N) tour1 = tour[:i+1]+tour[j:k+1]+tour[i+1:j]+tour[k+1:] elif (r < 0.9): i = random.randint(1, N-2) j = random.randint(i+1, N-1) tour1 = tour[:i]+tour[j:i-1:-1]+tour[j+1:] elif (r < 1): i = random.randint(0, N//2-3) j = random.randint(i+1, N//2-2) diff = j-i+1 k = random.randint(N//2+1,N-diff) tour1 = tour[:i]+tour[k:k+diff]+tour[j+1:k]+tour[i:j+1]+tour[k+diff:] # copy list # compute dE = length_of_tour1 – length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) # accept new tour if shorter or within prob. if (dE < 0 or random.random() < math.exp(-dE/T)): tour = tour1 if (T >= 2): # lower the temperature T *= 0.999 elif (T >= 1): T *= 0.9995 elif (T >= 0.05): T *= 0.9999 else: T *= 0.99995 print(tour) |
_main_: cluster #15 (4)
| # 6331408021 301 (2020-09-13 17:29) %diff = 0.23 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.001 : # while not finished r = random.random() if r < 0.2 : i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) tour1[i], tour1[j] = tour1[j], tour1[i] dE = dist(tour1[i-1], tour1[i]) + \ dist(tour1[i], tour1[i+1]) + \ dist(tour1[j-1], tour1[j]) + \ dist(tour1[j], tour1[(j+1)%N]) - \ dist(tour[i-1], tour[i]) - \ dist(tour[i], tour[i+1]) - \ dist(tour[j-1], tour[j]) - \ dist(tour[j], tour[(j+1)%N]) elif r < 0.4 : a = random.randint(0, N-5) b = random.randint(a+1, N-3) c = random.randint(b+1, N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r < 0.6 : a = random.randint(0, N-5) b = random.randint(a+1, N-4) c = random.randint(b+1, N-3) d = random.randint(c+1, N-2) tour1 = tour[:a] + tour[c:d+1] + tour[b+1:c] + \ tour[a:b+1] + tour[d+1:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r < 0.8 : a = random.randint(0, N-2) b = random.randint(a+1, N-1) tour1 = tour[:a+1] + tour[b:a:-1] + tour[b+1:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 else : a = random.randint(0, N-3) b = a+1 c = random.randint(b+1, N-1) tour1 = tour[:a] + tour[a:a+1] + tour[c:c+1] + tour[b:c] + tour[c+1:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *= 0.9999 # lower the temperature print(tour) | # 6331421121 311 (2020-09-13 23:31) %diff = 1.25 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.001 : # while not finished r = random.random() if r < 0.2 : i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) tour1[i], tour1[j] = tour1[j], tour1[i] dE = dist(tour1[i-1], tour1[i]) + \ dist(tour1[i], tour1[i+1]) + \ dist(tour1[j-1], tour1[j]) + \ dist(tour1[j], tour1[(j+1)%N]) - \ dist(tour[i-1], tour[i]) - \ dist(tour[i], tour[i+1]) - \ dist(tour[j-1], tour[j]) - \ dist(tour[j], tour[(j+1)%N]) elif r < 0.4 : a = random.randint(0, N-5) b = random.randint(a+1, N-3) c = random.randint(b+1, N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r < 0.6 : a = random.randint(0, N-4) b = random.randint(a+1, N-3) c = random.randint(b+1, N-2) d = random.randint(c+1, N-1) tour1 = tour[:a] + tour[c:d+1] + tour[b+1:c] + \ tour[a:b+1] + tour[d+1:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r < 0.8 : a = random.randint(0, N-2) b = random.randint(a+1, N-1) tour1 = tour[:a+1] + tour[b:a:-1] + tour[b+1:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 else : a = random.randint(0, N-3) b = a+1 x = random.randint(b+1, N-1) tour1 = tour[:a+1] + tour[x:x+1] + tour[b:x] + tour[x+1:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *= 0.9999 # lower the temperature print(tour) | # 6331415421 307 (2020-09-13 23:34) %diff = 0.23 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.0001 : # while not finished r = random.random() if r < 0.2 : i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) tour1[i], tour1[j] = tour1[j], tour1[i] dE = dist(tour1[i-1], tour1[i]) + \ dist(tour1[i], tour1[i+1]) + \ dist(tour1[j-1], tour1[j]) + \ dist(tour1[j], tour1[(j+1)%N]) - \ dist(tour[i-1], tour[i]) - \ dist(tour[i], tour[i+1]) - \ dist(tour[j-1], tour[j]) - \ dist(tour[j], tour[(j+1)%N]) elif r < 0.3 : a = random.randint(0, N-5) b = random.randint(a+1, N-3) c = random.randint(b+1, N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r < 0.7 : a = random.randint(0, N-5) b = random.randint(a+1, N-4) c = random.randint(b+1, N-3) d = random.randint(c+1, N-2) tour1 = tour[:a] + tour[c:d+1] + tour[b+1:c] + \ tour[a:b+1] + tour[d+1:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r < 0.8 : a = random.randint(0, N-2) b = random.randint(a+1, N-1) tour1 = tour[:a+1] + tour[b:a:-1] + tour[b+1:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 else : a = random.randint(0, N-3) b = a+1 c = random.randint(b+1, N-1) tour1 = tour[:a] + tour[a:a+1] + tour[c:c+1] + tour[b:c] + tour[c+1:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *= 0.9999 # lower the temperature print(tour) | # 6331413121 306 (2020-09-13 23:38) %diff = 0.39 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.001 : # while not finished r = random.random() if r < 0.25 : i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) tour1[i], tour1[j] = tour1[j], tour1[i] dE = dist(tour1[i-1], tour1[i]) + \ dist(tour1[i], tour1[i+1]) + \ dist(tour1[j-1], tour1[j]) + \ dist(tour1[j], tour1[(j+1)%N]) - \ dist(tour[i-1], tour[i]) - \ dist(tour[i], tour[i+1]) - \ dist(tour[j-1], tour[j]) - \ dist(tour[j], tour[(j+1)%N]) elif r < 0.45 : a = random.randint(0, N-5) b = random.randint(a+1, N-3) c = random.randint(b+1, N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r < 0.65 : a = random.randint(0, N-5) b = random.randint(a+1, N-4) c = random.randint(b+1, N-3) d = random.randint(c+1, N-2) tour1 = tour[:a] + tour[c:d+1] + tour[b+1:c] + \ tour[a:b+1] + tour[d+1:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r < 0.85 : a = random.randint(0, N-2) b = random.randint(a+1, N-1) tour1 = tour[:a+1] + tour[b:a:-1] + tour[b+1:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 else : a = random.randint(0, N-3) b = a+1 c = random.randint(b+1, N-1) tour1 = tour[:a] + tour[a:a+1] + tour[c:c+1] + tour[b:c] + tour[c+1:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *= 0.99998 # lower the temperature print(tour) |
_main_: cluster #16 (3)
| # 6330036021 84 (2020-09-13 19:02) %diff = 0.23 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.0001: # while not finished # create a new tour from the current tour tour1 = list(tour) r = random.random() if r <= 0.021: i = random.randint(0,N-2) #a, i+1=b j = random.randint(i+1,N-1) #x tour1 = tour1[:i+1]+tour1[j:j+1:]+tour1[i+1:j:]+tour1[j+1::] dE = dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[i+1], tour1[(i+2)%N]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) elif r <= 0.223: i = random.randint(0,N-3) #a j = random.randint(i+1,N-2) #b k = random.randint(j+1,N-1) #c, j+1=d tour1 = tour1[:i+1]+tour1[j:k+1:]+tour1[i+1:j]+tour1[k+1:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r <= 0.749: i = random.randint(0,N-2) #a j = random.randint(i+1,N-1) #b tour1 = tour1[:i] + tour1[j:i:-1] + tour1[i:i+1] + tour1[j+1:] L0 = L1 = 0 dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ j ], tour[ (j+1)%N]) elif r <= 0.915: i = random.randint(0,N-4) #a j = random.randint(i+1,N-3) #b k = random.randint(j+1,N-2) #c l = random.randint(k+1,N-1) #d tour1 = tour1[:i]+tour1[k:l+1]+tour1[j+1:k]+tour1[i:j+1]+tour1[l+1::] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r <= 1 : i = random.randint(0,N-2) #a j = random.randint(i+1,N-1) #b tour1[i],tour1[j] = tour1[j],tour1[i] dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) # accept new tour if shorter or within prob. a = random.random() if dE < 0 or a < math.exp(-dE/T) : tour = tour1 T *= 0.99999 # lower the temperature print(tour) | # 6330067521 112 (2020-09-13 19:03) %diff = 0.23 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.0001: # while not finished # create a new tour from the current tour tour1 = list(tour) r = random.random() if r <= 0.018: i = random.randint(0,N-2) #a, i+1=b j = random.randint(i+1,N-1) #x tour1 = tour1[:i+1]+tour1[j:j+1:]+tour1[i+1:j:]+tour1[j+1::] dE = dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[i+1], tour1[(i+2)%N]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) elif r <= 0.223: i = random.randint(0,N-3) #a j = random.randint(i+1,N-2) #b k = random.randint(j+1,N-1) #c, j+1=d tour1 = tour1[:i+1]+tour1[j:k+1:]+tour1[i+1:j]+tour1[k+1:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r <= 0.749: i = random.randint(0,N-2) #a j = random.randint(i+1,N-1) #b tour1 = tour1[:i] + tour1[j:i:-1] + tour1[i:i+1] + tour1[j+1:] L0 = L1 = 0 dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ j ], tour[ (j+1)%N]) elif r <= 0.915: i = random.randint(0,N-4) #a j = random.randint(i+1,N-3) #b k = random.randint(j+1,N-2) #c l = random.randint(k+1,N-1) #d tour1 = tour1[:i]+tour1[k:l+1]+tour1[j+1:k]+tour1[i:j+1]+tour1[l+1::] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r <= 1 : i = random.randint(0,N-2) #a j = random.randint(i+1,N-1) #b tour1[i],tour1[j] = tour1[j],tour1[i] dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) # accept new tour if shorter or within prob. a = random.random() if dE < 0 or a < math.exp(-dE/T) : tour = tour1 T *= 0.99995 # lower the temperature print(tour) | # 6331807821 335 (2020-09-13 23:57) %diff = 1.05 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] loop = 0 T = N*10 # starting temperature while T > 0.0001: # while not finished tour1 = list(tour) r = random.random() if r <= 0.1: i = random.randint(0,N-2) #a, i+1=b j = random.randint(i+1,N-1) #x tour1 = tour1[:i+1]+tour1[j:j+1:]+tour1[i+1:j:]+tour1[j+1::] dE = dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[i+1], tour1[(i+2)%N]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) elif r <= 0.4: i = random.randint(0,N-3) #a j = random.randint(i+1,N-2) #b k = random.randint(j+1,N-1) #c, j+1=d tour1 = tour1[:i+1]+tour1[j:k+1:]+tour1[i+1:j]+tour1[k+1:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r <= 0.9: i = random.randint(0,N-2) #a j = random.randint(i+1,N-1) #b tour1 = tour1[:i] + tour1[j:i:-1] + tour1[i:i+1] + tour1[j+1:] L0 = L1 = 0 dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ j ], tour[ (j+1)%N]) elif r <= 1: i = random.randint(0,N-4) #a j = random.randint(i+1,N-3) #b k = random.randint(j+1,N-2) #c l = random.randint(k+1,N-1) #d tour1 = tour1[:i]+tour1[k:l+1]+tour1[j+1:k]+tour1[i:j+1]+tour1[l+1::] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r <= 1.1 : i = random.randint(0,N-2) #a j = random.randint(i+1,N-1) #b tour1[i],tour1[j] = tour1[j],tour1[i] dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) a = random.random() if dE < 0 or a < math.exp(-dE/T) : tour = tour1 T *= 0.9999 print(tour) |
_main_: cluster #17 (6)
| # 6330049221 97 (2020-09-13 12:24) %diff = 1.31 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while (T > 0.02**(N//100+1)): r = random.random() # while not finished if (r < 0.8): i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) tour1[i], tour1[j] = tour1[j], tour1[i]# swap elif (r < 0.9): i = random.randint(0, N-2) j = random.randint(i+1, N-1) k = random.randint(j+1, N) tour1 = tour[:i+1]+tour[j:k+1]+tour[i+1:j]+tour[k+1:] elif (r < 1): i = random.randint(1, N-2) j = random.randint(i+1, N-1) tour1 = tour[:i]+tour[j:i-1:-1]+tour[j+1:] # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) # accept new tour if shorter or within prob. if (dE < 0 or random.random() < math.exp(-dE/T)) : tour = tour1 if (T >= 2): T *= 0.999 # lower the temperature elif (T >= 1): T *= 0.9995 elif (T >= 0.5): T *= 0.9997 elif (T >= 0.25): T *= 0.9998 else: T *= 0.9999 print(tour) | # 6331215221 281 (2020-09-13 13:57) %diff = 0.24 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while (T > 0.04**(N//100+1)): r = random.random() # while not finished if (r < 0.4): i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap elif (r < 0.6): i = random.randint(0, N-2) j = random.randint(i+1, N-1) k = random.randint(j+1, N) tour1 = tour[:i+1]+tour[j:k+1]+tour[i+1:j]+tour[k+1:] elif (r < 0.9): i = random.randint(1, N-2) j = random.randint(i+1, N-1) tour1 = tour[:i]+tour[j:i-1:-1]+tour[j+1:] # compute dE = length_of_tour1 – length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) # accept new tour if shorter or within prob. if (dE < 0 or random.random() < math.exp(-dE/T)) : tour = tour1 if (T >= 2): T *= 0.999 # lower the temperature elif (T >= 1): T *= 0.9996 elif (T >= 0.5): T *= 0.9997 elif (T >= 0.25): T *= 0.9998 else: T *= 0.9999 print(tour) | # 6331211721 278 (2020-09-13 15:23) %diff = 0.24 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while (T > 0.04**(N//100+1)): r = random.random() # while not finished if (r < 0.5): i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap elif (r < 0.7): i = random.randint(0, N-2) j = random.randint(i+1, N-1) k = random.randint(j+1, N) tour1 = tour[:i+1]+tour[j:k+1]+tour[i+1:j]+tour[k+1:] elif (r < 0.9): i = random.randint(1, N-2) j = random.randint(i+1, N-1) tour1 = tour[:i]+tour[j:i-1:-1]+tour[j+1:] # compute dE = length_of_tour1 – length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) # accept new tour if shorter or within prob. if (dE < 0 or random.random() < math.exp(-dE/T)) : tour = tour1 if (T >= 2): T *= 0.999 # lower the temperature elif (T >= 1): T *= 0.9996 elif (T >= 0.5): T *= 0.9997 elif (T >= 0.25): T *= 0.9998 else: T *= 0.9999 print(tour) | # 6331223221 288 (2020-09-13 15:56) %diff = 0.48 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while (T > 0.04**(N//100+1)): r = random.random() # while not finished if (r < 0.6): i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap elif (r < 0.8): i = random.randint(0, N-2) j = random.randint(i+1, N-1) k = random.randint(j+1, N) tour1 = tour[:i+1]+tour[j:k+1]+tour[i+1:j]+tour[k+1:] elif (r < 1): i = random.randint(1, N-2) j = random.randint(i+1, N-1) tour1 = tour[:i]+tour[j:i-1:-1]+tour[j+1:] # compute dE = length_of_tour1 – length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) # accept new tour if shorter or within prob. if (dE < 0 or random.random() < math.exp(-dE/T)) : tour = tour1 if (T >= 2): T *= 0.999 # lower the temperature elif (T >= 1): T *= 0.9996 elif (T >= 0.5): T *= 0.9997 elif (T >= 0.25): T *= 0.9998 else: T *= 0.9999 print(tour) | # 6331220321 286 (2020-09-13 16:52) %diff = 0.24 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while (T > 0.04**(N//100+1)): r = random.random() # while not finished if (r < 0.4): i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap elif (r < 0.5): i = random.randint(0, N-2) j = random.randint(i+1, N-1) k = random.randint(j+1, N) tour1 = tour[:i+1]+tour[j:k+1]+tour[i+1:j]+tour[k+1:] elif (r < 0.7): i = random.randint(1, N-2) j = random.randint(i+1, N-1) tour1 = tour[:i]+tour[j:i-1:-1]+tour[j+1:] # compute dE = length_of_tour1 – length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) # accept new tour if shorter or within prob. if (dE < 0 or random.random() < math.exp(-dE/T)) : tour = tour1 if (T >= 2): T *= 0.999 # lower the temperature elif (T >= 1): T *= 0.9996 elif (T >= 0.5): T *= 0.9997 elif (T >= 0.25): T *= 0.9998 else: T *= 0.9999 print(tour) | # 6331226121 290 (2020-09-13 22:41) %diff = 0.48 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while (T > 0.08**(N//100+1)): r = random.random() # while not finished if (r < 0.99): i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap elif (r < 0.9): i = random.randint(0, N-2) j = random.randint(i+1, N-1) k = random.randint(j+1, N) tour1 = tour[:i+1]+tour[j:k+1]+tour[i+1:j]+tour[k+1:] elif (r < 1): i = random.randint(1, N-2) j = random.randint(i+1, N-1) tour1 = tour[:i]+tour[j:i-1:-1]+tour[j+1:] # compute dE = length_of_tour1 – length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) # accept new tour if shorter or within prob. if (dE < 0 or random.random() < math.exp(-dE/T)) : tour = tour1 if (T >= 2): T *= 0.999 # lower the temperature elif (T >= 1): T *= 0.9996 elif (T >= 0.5): T *= 0.9997 elif (T >= 0.25): T *= 0.9998 else: T *= 0.9999 print(tour) |
_main_: cluster #18 (3)
| # 6330047021 95 (2020-09-12 15:37) %diff = 0.28 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.00001 : # while not finished a = random.randint(0,N-2) b = a + 1 while True : c = random.randint(0,N-1) if c != a and c != b : break tour1 = list(tour) if c > a : tour1 = tour[:b] + [tour[c]] + tour[b:c] + tour[c+1:] elif c < a : tour1 = tour[:c] + tour[c+1:a+1] + [tour[c]] + tour[b:] # compute dE = length_of_tour1 – length_of_tour if c > a and c > b: dE = dist(tour1[(b-1)%N],tour1[b%N])+ dist(tour1[b%N], tour1[(b+1)%N]) + dist(tour1[c%N],tour1[(c+1)%N]) - \ dist(tour[a%N], tour[b%N]) - dist(tour[(c-1)%N],tour[c%N]) - dist(tour[c%N],tour[(c+1)%N]) elif c < a and c < b: dE = dist(tour1[(c-1)%N],tour1[c%N])+ dist(tour1[(a-1)%N], tour1[(a)%N]) + dist(tour1[a%N],tour1[b%N]) - \ dist(tour[(c-1)%N], tour[c%N]) - dist(tour[c%N],tour[(c+1)%N]) - dist(tour[a%N],tour[b%N]) # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.e**(-dE/T) : tour = tour1 else: T = 0.9999*T # lower the temperature print(tour) | # 6331701921 324 (2020-09-13 19:59) %diff = 1.51 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.00001 : # while not finished a = random.randint(0,N-2) b = a + 1 while True : c = random.randint(0,N-1) if c != a and c != b : break tour1 = list(tour) if c > a : tour1 = tour[:b] + [tour[c]] + tour[b:c] + tour[c+1:] elif c < a : tour1 = tour[:c] + tour[c+1:a+1] + [tour[c]] + tour[b:] # compute dE = length_of_tour1 – length_of_tour if c > a and c > b: dE = dist(tour1[(b-1)%N],tour1[b%N])+ \ dist(tour1[b%N], tour1[(b+1)%N]) + \ dist(tour1[c%N],tour1[(c+1)%N]) - \ dist(tour[a%N], tour[b%N]) - \ dist(tour[(c-1)%N],tour[c%N]) - \ dist(tour[c%N],tour[(c+1)%N]) elif c < a and c < b: dE = dist(tour1[(c-1)%N],tour1[c%N])+ \ dist(tour1[(a-1)%N], tour1[(a)%N]) + \ dist(tour1[a%N],tour1[b%N]) - \ dist(tour[(c-1)%N], tour[c%N]) - \ dist(tour[c%N],tour[(c+1)%N]) - \ dist(tour[a%N],tour[b%N]) # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.e**(-dE/T) : tour = tour1 else: T *= 0.9999 # lower the temperature print(tour) | # 6331705421 328 (2020-09-13 20:15) %diff = 0.28 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.00002 : # while not finished a = random.randint(0,N-2) b = a + 1 while True : c = random.randint(0,N-1) if c != a and c != b : break tour1 = list(tour) if c > a : tour1 = tour[:b] + [tour[c]] + tour[b:c] + tour[c+1:] elif c < a : tour1 = tour[:c] + tour[c+1:a+1] + [tour[c]] + tour[b:] # compute dE = length_of_tour1 – length_of_tour if c > a and c > b: dE = dist(tour1[(b-1)%N],tour1[b%N])+ dist(tour1[b%N], tour1[(b+1)%N]) + dist(tour1[c%N],tour1[(c+1)%N]) - \ dist(tour[a%N], tour[b%N]) - dist(tour[(c-1)%N],tour[c%N]) - dist(tour[c%N],tour[(c+1)%N]) elif c < a and c < b: dE = dist(tour1[(c-1)%N],tour1[c%N])+ dist(tour1[(a-1)%N], tour1[(a)%N]) + dist(tour1[a%N],tour1[b%N]) - \ dist(tour[(c-1)%N], tour[c%N]) - dist(tour[c%N],tour[(c+1)%N]) - dist(tour[a%N],tour[b%N]) # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.e**(-dE/T) : tour = tour1 else: T = 0.999*T # lower the temperature print(tour) |
_main_: cluster #19 (2)
| # 6330144121 184 (2020-09-13 21:37) %diff = 0.3 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] dE = 0 #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.0001 : # while not finished # create a new tour from the current tour r = random.random() if r > 0.5 : i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else : a = random.randint(0,N-5) b = random.randint(a+1,N-3) c = random.randint(b+1,N-2) d = c+1 tour1 = tour[:a+1] + tour[b:d] + tour[a+1:b] + tour[d:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1],tour[i]) L1 += dist(tour1[i-1],tour1[i]) dE = L1-L0 # accept new tour if shorter or within prob. if dE < 0 or random.randint(0,1) < math.exp(-1*dE/T): tour = tour1 T = 0.9999*T # lower the temperature print(tour) | # 6330127521 170 (2020-09-13 23:39) %diff = 0.3 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] dE = 0 #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.00001 : # while not finished # create a new tour from the current tour r = random.random() if r > 0.5 : i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else : a = random.randint(0,N-5) b = random.randint(a+1,N-3) c = random.randint(b+1,N-2) d = c+1 tour1 = tour[:a+1] + tour[b:d] + tour[a+1:b] + tour[d:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1],tour[i]) L1 += dist(tour1[i-1],tour1[i]) dE = L1-L0 # accept new tour if shorter or within prob. if dE < 0 or random.randint(0,1) < math.exp(-1*dE/T): tour = tour1 T = 0.999*T # lower the temperature print(tour) |
_main_: cluster #20 (2)
| # 6330162421 200 (2020-09-13 22:04) %diff = 0.38 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.0001: # while not finished # create a new tour from the current tour tour1 = list(tour) r = random.random() if r <= 0.1: i = random.randint(0,N-2) #a j = random.randint(i+1,N-1) #b tour1[i],tour1[j] = tour1[j],tour1[i] dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) elif r <= 0.7: i = random.randint(0,N-2) #a j = random.randint(i+1,N-1) #b tour1 = tour1[:i] + tour1[j:i:-1] + tour1[i:i+1] + tour1[j+1:] L0 = L1 = 0 dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ j ], tour[ (j+1)%N]) elif r <= 0.85: i = random.randint(0,N-4) #a j = random.randint(i+1,N-3) #b k = random.randint(j+1,N-2) #c l = random.randint(k+1,N-1) #d tour1 = tour1[:i]+tour1[k:l+1]+tour1[j+1:k]+tour1[i:j+1]+tour1[l+1::] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r <= 0.9: i = random.randint(0,N-3) #a j = random.randint(i+1,N-2) #b k = random.randint(j+1,N-1) #c, j+1=d tour1 = tour1[:i+1]+tour1[j:k+1:]+tour1[i+1:j]+tour1[k+1:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r <= 1 : i = random.randint(0,N-2) #a, i+1=b j = random.randint(i+1,N-1) #x tour1 = tour1[:i+1]+tour1[j:j+1:]+tour1[i+1:j:]+tour1[j+1::] dE = dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[i+1], tour1[(i+2)%N]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) # accept new tour if shorter or within prob. a = random.random() if dE < 0 or a < math.exp(-dE/T) : tour = tour1 T *= 0.9999 # lower the temperature print(tour) | # 6330145821 185 (2020-09-13 22:41) %diff = 0.38 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.0001: # while not finished # create a new tour from the current tour tour1 = list(tour) r = random.random() if r <= 0.12: i = random.randint(0,N-2) #a j = random.randint(i+1,N-1) #b tour1[i],tour1[j] = tour1[j],tour1[i] dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) elif r <= 0.68: i = random.randint(0,N-2) #a j = random.randint(i+1,N-1) #b tour1 = tour1[:i] + tour1[j:i:-1] + tour1[i:i+1] + tour1[j+1:] L0 = L1 = 0 dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ j ], tour[ (j+1)%N]) elif r <= 0.82: i = random.randint(0,N-4) #a j = random.randint(i+1,N-3) #b k = random.randint(j+1,N-2) #c l = random.randint(k+1,N-1) #d tour1 = tour1[:i]+tour1[k:l+1]+tour1[j+1:k]+tour1[i:j+1]+tour1[l+1::] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r <= 0.89: i = random.randint(0,N-3) #a j = random.randint(i+1,N-2) #b k = random.randint(j+1,N-1) #c, j+1=d tour1 = tour1[:i+1]+tour1[j:k+1:]+tour1[i+1:j]+tour1[k+1:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r <= 1 : i = random.randint(0,N-2) #a, i+1=b j = random.randint(i+1,N-1) #x tour1 = tour1[:i+1]+tour1[j:j+1:]+tour1[i+1:j:]+tour1[j+1::] dE = dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[i+1], tour1[(i+2)%N]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) # accept new tour if shorter or within prob. a = random.random() if dE < 0 or a < math.exp(-dE/T) : tour = tour1 T *= 0.9999 # lower the temperature print(tour) |
_main_: cluster #21 (3)
| # 6331107121 245 (2020-09-13 23:20) %diff = 0.4 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 while T > 1e-90: r = random.randint(0,1) if r < 0.6 : a = random.randint(0, N-4) b = a+1 x = random.randint(b+1, N-2) L0 = 0 L1 = 0 tour1 = tour[:a+1]+tour[x:x+1]+tour[b:x]+tour[x+1:] dE = dist(tour1[a],tour1[b]) + \ dist(tour1[b],tour1[(b+1)%N]) + \ dist(tour1[x],tour1[x+1]) - \ dist(tour[a],tour[b]) - \ dist(tour[x-1],tour[x]) - \ dist(tour[x],tour[(x+1)%N]) else : a = random.randint(0, N-5) b = random.randint(a+1, N-3) c = random.randint(b+1, N-2) d = c+1 tour1 = tour[:a+1]+tour[b:c+1]+tour[a+1:b]+tour[d:] L0 = 0 L1 = 0 dE = dist(tour1[a],tour1[a+1]) + \ dist(tour1[c-len(tour[a+1:b])],tour1[c-len(tour[a+1:b])+1]) + \ dist(tour1[d-1],tour1[d]) - \ dist(tour[a],tour[a+1]) - \ dist(tour[b-1],tour[b]) - \ dist(tour[c],tour[d]) if dE < 0 or random.randint(0,1) < math.e**(-dE/T) : tour = tour1 T = 0.999*T print(tour) | # 6331103621 241 (2020-09-13 23:58) %diff = 0.93 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 while T > 1e-100: r = random.randint(0,1) if r < 0.6 : a = random.randint(0, N-4) b = a+1 x = random.randint(b+1, N-2) L0 = 0 L1 = 0 tour1 = tour[:a+1]+tour[x:x+1]+tour[b:x]+tour[x+1:] dE = dist(tour1[a],tour1[b]) + \ dist(tour1[b],tour1[(b+1)%N]) + \ dist(tour1[x],tour1[x+1]) - \ dist(tour[a],tour[b]) - \ dist(tour[x-1],tour[x]) - \ dist(tour[x],tour[(x+1)%N]) else : a = random.randint(0, N-5) b = random.randint(a+1, N-3) c = random.randint(b+1, N-2) d = c+1 tour1 = tour[:a+1]+tour[b:c+1]+tour[a+1:b]+tour[d:] L0 = 0 L1 = 0 dE = dist(tour1[a],tour1[a+1]) + \ dist(tour1[c-len(tour[a+1:b])],tour1[c-len(tour[a+1:b])+1]) + \ dist(tour1[d-1],tour1[d]) - \ dist(tour[a],tour[a+1]) - \ dist(tour[b-1],tour[b]) - \ dist(tour[c],tour[d]) if dE < 0 or random.randint(0,1) < math.e**(-dE/T) : tour = tour1 T = 0.9999999*T print(tour) | # 6330089321 133 (2020-09-13 23:59) %diff = 0.4 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 while T > 1e-70: r = random.randint(0,1) if r < 0.7 : m = random.randint(0, N-4) n = m+1 x = random.randint(n+1, N-2) L0 = 0 L1 = 0 tour1 = tour[:m+1]+tour[x:x+1]+tour[n:x]+tour[x+1:] dE = dist(tour1[m],tour1[n]) + \ dist(tour1[n],tour1[(n+1)%N]) + \ dist(tour1[x],tour1[x+1]) - \ dist(tour[m],tour[n]) - \ dist(tour[x-1],tour[x]) - \ dist(tour[x],tour[(x+1)%N]) else : m = random.randint(0, N-5) n = random.randint(m+1, N-3) o = random.randint(n+1, N-2) p = o+1 tour1 = tour[:m+1]+tour[n:o+1]+tour[m+1:n]+tour[p:] L0 = 0 L1 = 0 dE = dist(tour1[m],tour1[m+1]) + \ dist(tour1[o-len(tour[m+1:n])],tour1[o-len(tour[m+1:n])+1]) + \ dist(tour1[p-1],tour1[p]) - \ dist(tour[m],tour[m+1]) - \ dist(tour[n-1],tour[n]) - \ dist(tour[o],tour[p]) if dE < 0 or random.randint(0,1) < math.e**(-dE/T) : tour = tour1 T = 0.999*T print(tour) |
_main_: cluster #22 (4)
| # 6331024721 236 (2020-09-13 00:45) %diff = 0.42 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.001 : # while not finished # create a new tour from the current tour r = random.random() if r < 0.5: i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 – length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else: a = random.randint(0, N-5) b = random.randint(a+1, N-3) c = random.randint(b+1, N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *= 0.9999 # lower the temperature # keep tour changes in tour_log loop += 1 if loop % N == 0: tour_log += [[T, tour]] tour_log += [[T, tour]] # the final tour print(tour) animate(X, Y, tour_log[-500:]) # let's animate | # 6331509821 317 (2020-09-13 20:59) %diff = 1.53 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.001 : # while not finished # create a new tour from the current tour r = random.random() if r < 0: i = random.randint(0,N-2) j = random.randint(i+1,N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else: a = random.randint(0, N-7) b = random.randint(a+1, N-5) c = random.randint(b+1, N-3) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T): tour = tour1 T *= 0.999 # lower the temperature # keep tour changes in tour_log loop += 1 if loop % N == 0: tour_log += [[T, tour]] tour_log += [[T, tour]] # the final tour print(tour) animate(X, Y, tour_log ) # let's animate | # 6331016721 229 (2020-09-13 21:27) %diff = 0.42 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.001 : # while not finished # create a new tour from the current tour r = random.random() if r < 0.5 : i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else: a = random.randint(0, N-5) b = random.randint(a+1, N-3) c = random.randint(b+1, N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *= 0.9999 # lower the temperature # keep tour changes in tour_log loop += 1 if loop % N == 0: tour_log += [[T, tour]] tour_log += [[T, tour]] # the final tour print(tour) animate( X, Y, tour_log[-1:] ) # let's animate | # 6330097321 141 (2020-09-13 23:32) %diff = 0.69 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.0001 : # while not finished # create a new tour from the current tour r = random.random() if r < 0.27: i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else : a = random.randint(0,N-5) b = random.randint(a+1,N-3) c = random.randint(b+1,N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 = 0 for i in range(N): L0 +=dist(tour[i-1],tour[i]) L1 +=dist(tour1[i-1],tour1[i]) dE = L1-L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *=0.9999 # lower the temperature # keep tour changes in tour_log loop += 1 if loop % N == 0: tour_log += [[T, tour]] tour_log += [[T, tour]] # the final tour print(tour) animate(X, Y, tour_log[-1000:] ) # let's animate |
_main_: cluster #23 (2)
| # 6331128321 264 (2020-09-13 18:48) %diff = 0.44 old_dist = cal_dist(tour) T = N # starting temperature while(T >= 1e-8) : # while not finished # create a new tour from the current tour i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list # reversed tour tour1[i : j] = reversed(tour1[i : j]) # compute dE = length_of_tour1 - length_of_tour new_dist = cal_dist(tour1) dE = new_dist - old_dist # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : old_dist = new_dist tour = tour1 T *= 0.9995 # lower the temperature print(tour) | # 6330065221 111 (2020-09-13 19:15) %diff = 0.44 old_dist = cal_dist(tour) T = N # starting temperature while(T >= 1e-8) : # while not finished # create a new tour from the current tour i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list # reversed tour tour1[i : j] = reversed(tour1[i : j]) # compute dE = length_of_tour1 - length_of_tour new_dist = cal_dist(tour1) dE = new_dist - old_dist # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : old_dist = new_dist tour = tour1 T *= 0.99995 # lower the temperature print(tour) |
_main_: cluster #24 (2)
| # 6231001121 17 (2020-09-13 20:56) %diff = 0.45 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.0001 : # while not finished r = random.random() if r < 0.7 : i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else : a = random.randint(0 , N-5) b = random.randint(a+1 , N-3) c = random.randint(b+1 , N-2 ) d = c+1 tour1 = tour[:a] + tour[b+1:c+1] +tour[a:b+1] + tour[d:] L0 = L1 = 0 for i in range(N) : L0 += dist(tour[i-1] , tour[i]) L1 += dist(tour1[i-1] , tour1[i]) dE = L1-L0 # accept new tour if shorter or within prob. if ( dE < 0) or ( random.random( ) < math.exp(-dE/T) ) : tour = tour1 else : T = T*0.9981 # lower the temperature print(tour) | # 6231014321 26 (2020-09-13 23:42) %diff = 0.45 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.0008 : # while not finished r = random.random() if r < 0.4 : i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else : a = random.randint(0 , N-5) b = random.randint(a+1 , N-3) c = random.randint(b+1 , N-2 ) d = c+1 tour1 = tour[:a] + tour[b+1:c+1] +tour[a:b+1] + tour[d:] L0 = L1 = 0 for i in range(N) : L0 += dist(tour[i-1] , tour[i]) L1 += dist(tour1[i-1] , tour1[i]) dE = L1-L0 # accept new tour if shorter or within prob. if ( dE < 0) or ( random.random( ) < math.exp(-dE/T) ) : tour = tour1 else : T = T*0.9988 # lower the temperature print(tour) |
_main_: cluster #25 (2)
| # 6330084121 128 (2020-09-12 22:12) %diff = 0.48 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.01 : # while not finished # create a new tour from the current tour mek = random.randint(0, 1) if mek == 0: i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap elif mek == 1: i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) tour11 = tour1[:i+1] tour12 = tour1[i+1:j] tour13 = tour1[j] tour14 = tour1[j+1:] tour1 = tour11 + [tour13] + tour12 + tour14 # compute dE = length_of_tour1 โ€“ length_of_tour if mek == 0: dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) elif mek == 1: dE = dist(tour1[i], tour1[i+1]) + \ dist(tour1[i+1], tour1[(i+2)%N]) + \ dist(tour1[j], tour1[(j+1)%N]) - \ dist(tour[i], tour[i+1]) - \ dist(tour[j-1], tour[j]) - \ dist(tour[j], tour[(j+1)%N]) # accept new tour if shorter or within prob. if (dE < 0) or random.random() < math.exp(-dE/T) : tour = tour1 T *= 0.9999 # lower the temperature # keep tour changes in tour_log loop += 1 if loop % N == 0: tour_log += [[T, tour]] tour_log += [[T, tour]] # the final tour print(tour) animate(X, Y, tour_log[-1:] ) # let's animate | # 6330068121 113 (2020-09-12 22:37) %diff = 0.48 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T>0.00001: # while not finished # create a new tour from the current tour pear = random.randint(0,1) if pear ==0: i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap elif pear ==1 : i = random.randint(0,N-2) j = random.randint(i+1,N-1) tour1= list(tour) tourr = tour1[:i+1] tourrr = tour1[i+1:j] tourrrr = tour1[j] tourrrrr = tour1[j+1:] tour1=tourr+[tourrrr]+tourrr+tourrrrr # compute dE = length_of_tour1 โ€“ length_of_tour if pear ==0 : dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) elif pear == 1: dE = dist(tour1[i],tour1[i+1]) + \ dist(tour1[i+1],tour1[(i+2)%N])+\ dist(tour1[j],tour1[(j+1)%N]) - \ dist(tour[i],tour[i+1]) -\ dist(tour[j-1],tour[j]) -\ dist(tour[j],tour[(j+1)%N]) # accept new tour if shorter or within prob. if (dE < 0) or random.random() < math.exp(-dE/T) : tour = tour1 T*=0.99999 # lower the temperature # keep tour changes in tour_log loop += 1 if loop % N == 0: tour_log += [[T, tour]] tour_log += [[T, tour]] # the final tour print(tour) animate(X, Y, tour_log[-1:] ) # let's animate |
_main_: cluster #26 (2)
| # 6330100521 144 (2020-09-13 23:20) %diff = 0.58 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T>0.00001 : # while not finished r = random.random() i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list if r < 0.33 : tour1[i], tour1[j] = tour1[j], tour1[i] # swap dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) elif r < 0.55 : c = tour1[i] tour1.remove(tour1[i]) tour1.insert(j,c) dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) elif r < 0.75 : j = i+1 tour1[i], tour1[j] = tour1[j], tour1[i] dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else : a = random.randint(0,N-5) b = random.randint(a+1,N-3) c = random.randint(b+1,N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 = 0 for i in range(N): L0 +=dist(tour[i-1],tour[i]) L1 +=dist(tour1[i-1],tour1[i]) dE = L1-L0 if dE < 0 or random.random() < math.e**(-dE/T) : tour = tour1 T = 0.9999*T # lower the temperature print(tour) | # 6330115021 159 (2020-09-13 23:38) %diff = 0.58 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.00001 : # while not finished r = random.random() i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list if r < 0.2 : tour1[i], tour1[j] = tour1[j], tour1[i] # swap dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) elif r < 0.5 : c = tour1[i] tour1.remove(tour1[i]) tour1.insert(j,c) dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) elif r < 0.7 : j = i+1 tour1[i], tour1[j] = tour1[j], tour1[i] dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else : a = random.randint(0,N-5) b = random.randint(a+1,N-3) c = random.randint(b+1,N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 = 0 for i in range(N): L0 +=dist(tour[i-1],tour[i]) L1 +=dist(tour1[i-1],tour1[i]) dE = L1-L0 if dE < 0 or 2*random.random() < math.e**(-dE/T) : tour = tour1 T = 0.9999*T # lower the temperature print(tour) |
_main_: cluster #27 (2)
| # 6331806121 334 (2020-09-12 17:26) %diff = 0.66 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*100 # starting temperature while T > 100000 : loop += 1 # while not finished # create a new tour from the current tour i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) # accept new tour if shorter or within prob. if dE < 0 or random(0,1) < exp(-dE/T) : tour = tour1 T = 0.99*T # lower the temperature if T < 0.001: break print(tour) | # 6331233521 294 (2020-09-13 21:17) %diff = 0.66 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 100000: # while not finished loop += 1 # create a new tour from the current tour i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) # accept new tour if shorter or within prob. if dE < 0 or random(0,1) < exp(-dE/T) : tour = tour1 T = 0.99*T # lower the temperature if T < 0.01: break print(tour) |
_main_: cluster #28 (5)
| # 6331004121 218 (2020-09-11 21:21) %diff = 1.6 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T>0.0009 : # while not finished # create a new tour from the current tour i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) # accept new tour if shorter or within prob. if dE<0 or random.random()<math.e**(-dE/T) : tour = tour1 T*=0.99998 # lower the temperature print(tour) | # 6330093821 137 (2020-09-13 21:08) %diff = 0.68 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 10**-10 : # while not finished # create a new tour from the current tour i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T = 0.99999*T # lower the temperature print(tour) | # 6330138421 179 (2020-09-13 21:46) %diff = 0.68 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > (10**-7) : # while not finished # create a new tour from the current tour i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T = 0.99999*T # lower the temperatur print(tour) | # 6231106421 34 (2020-09-13 23:17) %diff = 1.37 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T>1e-317 : # while not finished # create a new tour from the current tour i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *= 0.9999 # lower the temperature print(tour) | # 6331131121 266 (2020-09-13 23:27) %diff = 1.37 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.1 : # while not finished # create a new tour from the current tour i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *= 0.99999 # lower the temperature print(tour) |
_main_: cluster #29 (3)
| # 6331203721 272 (2020-09-12 23:33) %diff = 0.89 map_name = input("Map file name: ") X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.0001 : # while not finished # create a new tour from the current tour r = random.random() if r < 0.5: # always false i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else: #prob = 0.5 a = random.randint(0, N-5) b = random.randint(a+1, N-3) c = random.randint(b+1, N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *= 0.9999 # lower the temperature print(tour) | # 6331213021 279 (2020-09-13 19:32) %diff = 0.89 map_name = input("Map file name:") X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.1 : # while not finished # create a new tour from the current tour r = random.random() if r < 0.2: i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else: a = random.randint(0, N-5) b = random.randint(a+1,N-3) c = random.randint(b+1,N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour[i-1], tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *= 0.9999 # lower the temperature print(tour) | # 6331218121 284 (2020-09-13 23:38) %diff = 1.61 map_name = input("Map file name: ") X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.001 : # while not finished # create a new tour from the current tour r = random.random() if r < 0.5: i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else : a = random.randint(0, N-5) b = random.randint(a+1, N-3) c = random.randint(b+1, N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T): tour = tour1 else: # lower the temperature T *= 0.9999 print(tour) |
_main_: cluster #30 (2)
| # 6330114321 158 (2020-09-13 21:10) %diff = 0.94 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.001: # while not finished # create a new tour from the current tour r=random.random() if r <0.5 : i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) elif r<0.7: a = random.randint(0,N-5) b = random.randint(a+1,N-3) c = random.randint(b+1,N-1) d = c+1 tour1 = tour[0:a+1]+tour[b:c+1]+tour[a+1:b]+tour[d:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1],tour[i]) L1 += dist(tour1[i-1],tour1[i]) dE = L1-L0 else : a = random.randint(0,N-2) b = random.randint(a+1,N) tour1 = tour[0:a]+tour[b:a:-1]+tour[a:a+1]+tour[b+1:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1],tour[i]) L1 += dist(tour1[i-1],tour1[i]) dE = L1-L0 # accept new tour if shorter or within prob. if dE < 0 or random.randint(0,1) < math.exp(-dE/T): tour = tour1 T *=0.9999 # lower the temperature print(tour) | # 6330091521 135 (2020-09-13 21:38) %diff = 0.94 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.000001: # while not finished # create a new tour from the current tour r=random.random() if r <0.3 : i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) elif r<0.56: a = random.randint(0,N-5) b = random.randint(a+1,N-3) c = random.randint(b+1,N-1) d = c+1 tour1 = tour[0:a+1]+tour[b:c+1]+tour[a+1:b]+tour[d:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1],tour[i]) L1 += dist(tour1[i-1],tour1[i]) dE = L1-L0 else : a = random.randint(0,N-18) b = random.randint(a+1,N) tour1 = tour[0:a]+tour[b:a:-1]+tour[a:a+1]+tour[b+1:] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1],tour[i]) L1 += dist(tour1[i-1],tour1[i]) dE = L1-L0 # accept new tour if shorter or within prob. if dE < 0 or random.randint(0,1) < math.exp(-dE/T): tour = tour1 T *=0.9999 # lower the temperature print(tour) |
_main_: cluster #31 (2)
| # 6330054321 102 (2020-09-13 19:32) %diff = 1.05 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.00001 : # while not finished # create a new tour from the current tour r = random.random() tour1 = list(tour) #tour2 = list(tour1) if r < 0.5 : i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1 = tour1[:i] + tour1[j:i:-1] + tour1[i:i+1] + tour1[j+1:]# swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ j ], tour[ (j+1)%N]) elif r < 0.7 : a = random.randint(0, N-5) b = random.randint(a+1, N-3) c = random.randint(b+1, N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 = 0 for i in range(N) : L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r < 0.8: i = random.randint(0,N-2) j = random.randint(i+1,N-1) tour1 = tour1[:i+1]+tour1[j:j+1:]+tour1[i+1:j:]+tour1[j+1::] L0 = L1 = 0 dE = dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[i+1], tour1[(i+2)%N]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) elif r < 0.9: a = random.randint(0,N-5) b = random.randint(a+1,N-4) c = random.randint(b+1,N-3) d = random.randint(c+1,N-1) tour1 = tour1[:a]+tour1[c:d+1]+tour1[b+1:c]+tour1[a:b+1]+tour1[d+1::] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r < 1: i = random.randint(0,N-2) j = random.randint(i+1,N-1) tour1[i], tour1[j] = tour1[j], tour1[i] dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) # accept new tour if shorter or within prob. #a = random.random() if dE < 0 or random.random() < math.exp((-dE)/T) : tour = tour1 T = 0.9999*T # lower the temperature print(tour) | # 6330092121 136 (2020-09-13 23:30) %diff = 1.05 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.00001 : # while not finished # create a new tour from the current tour r = random.random() tour1 = list(tour) #tour2 = list(tour1) if r < 0.28 : i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1 = tour1[:i] + tour1[j:i:-1] + tour1[i:i+1] + tour1[j+1:]# swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ j ], tour[ (j+1)%N]) elif r < 0.64 : a = random.randint(0, N-5) b = random.randint(a+1, N-3) c = random.randint(b+1, N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = L1 = 0 for i in range(N) : L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r < 0.75: i = random.randint(0,N-2) j = random.randint(i+1,N-1) tour1 = tour1[:i+1]+tour1[j:j+1:]+tour1[i+1:j:]+tour1[j+1::] L0 = L1 = 0 dE = dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[i+1], tour1[(i+2)%N]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) elif r < 0.86: a = random.randint(0,N-5) b = random.randint(a+1,N-4) c = random.randint(b+1,N-3) d = random.randint(c+1,N-1) tour1 = tour1[:a]+tour1[c:d+1]+tour1[b+1:c]+tour1[a:b+1]+tour1[d+1::] L0 = L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 elif r <= 1: i = random.randint(0,N-2) j = random.randint(i+1,N-1) tour1[i], tour1[j] = tour1[j], tour1[i] dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) # accept new tour if shorter or within prob. #a = random.random() if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T*= 0.99995 # lower the temperature print(tour) |
_main_: cluster #32 (2)
| # 6330018821 67 (2020-09-13 19:46) %diff = 1.18 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.001 : # while not finished r = random.random() if r < 0.50: # create a new tour from the current tour i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) elif r < 0.99: i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) x = tour1.pop(j) tour1.insert(i, x) dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else: i = random.randint(0, N-2) j = random.randint(0, N-2) tour1 = list(tour) revtour = tour1[min(i, j):max(i, j)] revtour.reverse() for x in range(j-i): tour1[i+x] = revtour[x] dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[j ], tour1[j+1]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ j ], tour[ j+1]) # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *= 0.9999 # lower the temperature print(tour) | # 6331511021 319 (2020-09-13 21:46) %diff = 1.18 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T>=0.1 : # while not finished r = random.random() # create a new tour from the current tour if r < 0.25: i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) elif r < 0.45: i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) x = tour1.pop(j) tour1.insert(i, x) dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else : i = random.randint(0, N-2) j = random.randint(0, N-2) tour1 = list(tour) revtour = tour1[min(i, j):max(i, j)] revtour.reverse() for x in range(j-i): tour1[i+x] = revtour[x] dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[j ], tour1[j+1]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ j ], tour[ j+1]) # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T = T*0.999 # lower the temperature print(tour) |
_main_: cluster #33 (2)
| # 6330027421 76 (2020-09-13 21:48) %diff = 1.22 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.0001 : # while not finished # create a new tour from the current tour r = random.random() if r < 0.5: i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 – length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) elif r > 0.8: tour1 = list(tour) # copy if N % 2 == 0: tour1 = tour1[N//2:]+tour1[:N//2 ] L0 = 0 L1 = 0 for i in range(N): L0 += dist(tour[i-1],tour[i]) L1 += dist(tour1[i-1],tour1[i]) dE = L1 - L0 else: i = random.randint(0,N//2) j = random.randint(N//2,N) tour1 = list(tour) a = list(tour1[i:j]) a.reverse() tour1 = tour1[:i]+a+tour1[j:] L0 = 0 L1 = 0 for i in range(N): L0 += dist(tour[i-1],tour[i]) L1 += dist(tour1[i-1],tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.pow(math.e,(-dE/T)) : tour = tour1 T *= 0.9999 # lower the temperature print(tour) | # 6330037721 85 (2020-09-13 22:24) %diff = 1.22 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.001 : # while not finished # create a new tour from the current tour r = random.random() if r < 0.5: i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 – length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) elif r > 0.8: tour1 = list(tour) # copy if N % 2 == 0: tour1 = tour1[N//2:]+tour1[:N//2 ] L0 = 0 L1 = 0 for i in range(N): L0 += dist(tour[i-1],tour[i]) L1 += dist(tour1[i-1],tour1[i]) dE = L1 - L0 else: i = random.randint(0,N//2) j = random.randint(N//2,N) tour1 = list(tour) a = list(tour1[i:j]) a.reverse() tour1 = tour1[:i]+a+tour1[j:] L0 = 0 L1 = 0 for i in range(N): L0 += dist(tour[i-1],tour[i]) L1 += dist(tour1[i-1],tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.pow(math.e,(-dE/T)) : tour = tour1 T *= 0.9999 # lower the temperature print(tour) print(T) |
_main_: cluster #34 (2)
| # 6231007021 22 (2020-09-13 20:56) %diff = 1.22 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*7 # starting temperature while T>1e-137 :# while not finished # create a new tour from the current tour i = random.randint(0, N-3) j = random.randint(i+1, N-2) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *= 0.99 # lower the temperature # keep tour changes in tour_log loop += 1 if loop % N == 0: tour_log += [[T, tour]] tour_log += [[T, tour]] # the final tour print(tour) animate(X, Y, tour_log[-1:] ) # let's animate | # 6231003421 19 (2020-09-13 21:34) %diff = 1.22 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*2 # starting temperature while T>1e-250 :# while not finished # create a new tour from the current tour i = random.randint(0, N-3) j = random.randint(i+1, N-2) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 โ€“ length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *= 0.898 # lower the temperature # keep tour changes in tour_log loop += 1 if loop % N == 0: tour_log += [[T, tour]] tour_log += [[T, tour]] # the final tour print(tour) animate(X, Y, tour_log[-1:] ) # let's animate |
_main_: cluster #35 (3)
| # 6331118021 254 (2020-09-13 21:03) %diff = 1.49 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.0001 : # while not finished # create a new tour from the current tour r = random.random() if r <0.5: i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 – length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else: a = random.randint(0,N-5) b = random.randint(a+1,N-3) c = random.randint(b+1,N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] +tour[a+1:b]+ tour[d:] L0 = 0 L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1],tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T *= 0.999 # lower the temperature print(tour) | # 6331022421 234 (2020-09-13 21:33) %diff = 1.5 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T>0.0001 :# while not finished r=random.random() if r<0.5: # create a new tour from the current tour i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else: a = random.randint(0, N-6) b = random.randint(a+1, N-4) c = random.randint(b+1, N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = 0 L1 = 0 for i in range(N): L0 += dist(tour[i-1], tour[i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE<0 or random.randint(0,2)<math.exp(-dE/T) : tour = tour1 T*=0.9999 print(tour) | # 6331202021 271 (2020-09-13 23:58) %diff = 1.49 map_name = input() X, Y = read_map(map_name) D = calc_all_pair_distances(X, Y) N = len(X) # number of points tour_log = [] tour = list(range(N)) # [0,1,2,3,4,...,N-1] #--- let's the SA begins -------------- loop = 0 T = N*10 # starting temperature while T > 0.0001 : loop += 10 r = random.random()# while not finished # create a new tour from the current tour if r < 0.5 : i = random.randint(0, N-2) j = random.randint(i+1, N-1) tour1 = list(tour) # copy list tour1[i], tour1[j] = tour1[j], tour1[i] # swap # compute dE = length_of_tour1 – length_of_tour dE = dist(tour1[i-1], tour1[i ]) + \ dist(tour1[i ], tour1[i+1 ]) + \ dist(tour1[j-1], tour1[j ]) + \ dist(tour1[j ], tour1[(j+1)%N]) - \ dist(tour[ i-1], tour[ i ]) - \ dist(tour[ i ], tour[ i+1 ]) - \ dist(tour[ j-1], tour[ j ]) - \ dist(tour[ j ], tour[(j+1)%N ]) else : a = random.randint(0, N-5) b = random.randint(a+1, N-3) c = random.randint(b+1, N-2) d = c+1 tour1 = tour[:a+1] + tour[b:c+1] + tour[a+1:b] + tour[d:] L0 = 0 L1 = 0 for i in range(N): L0 += dist(tour[ i-1], tour[ i]) L1 += dist(tour1[i-1], tour1[i]) dE = L1 - L0 # accept new tour if shorter or within prob. if dE < 0 or random.random() < math.exp(-dE/T) : tour = tour1 T = T*0.9997# lower the temperature print(tour) |