# Untitled

unknown
python
2 years ago
2.8 kB
2
Indexable
Never
```all_edges = list(itertools.combinations(np.arange(int(np.ceil(len(data_c) * 0.5))), 2))
all_edges = list(zip(['e' for _ in range(len(all_edges))], all_edges))
all_nodes = list(itertools.product(np.arange(int(np.ceil(len(data_c) * 0.5))), np.arange(len(data_c) - int(np.ceil(len(data_c) * 0.5)))))
all_nodes = list(zip(['n' for _ in range(len(all_nodes))], all_nodes))
all_e_n = all_edges + all_nodes

#%%time
distances=[]
paths = []
for column in range(20):
distance_sum, path = local_TSP(data_c, c_distance, column, all_e_n)
distances.append(distance_sum)
print(distances)
paths.append(path)

print("Min: ", min(distances), " Avg: ", np.mean(distances)," Max: ", max(distances))

def local_TSP(data, distance_matrix, starting_point, all_e_n):
distance, path = random_search(data, distance_matrix, starting_point)
is_better = True

while is_better:
is_better, path, distance = steepest_local_search(data, distance_matrix, path, distance, all_e_n)

return distance, path

def edges_exchange(dist_matrix, path, node):
path.append(path[0])
a, b = node
if b - a > 2:
i_1, i_2, j_1, j_2 = path[a], path[a + 1], path[b - 1], path[b]
current = dist_matrix[i_1][i_2] + dist_matrix[j_1][j_2]
new = dist_matrix[i_1][j_1] + dist_matrix[i_2][j_2]
else:
new, current = 0, 0
path.pop()
return new - current

def steepest_local_search(data, distance_matrix, start_path, distance, all_e_n):
path = copy.deepcopy(start_path)
not_selected = list(set(range(len(data))) - set(path))
best_delta, best_node = 0, None
for sel in all_e_n:
i, node = sel
if i == 'e':
delta = edges_exchange(distance_matrix, path, node)
else:
delta = node_select(data, distance_matrix, path, node, not_selected)

if delta < best_delta:
best_delta, best_node = delta, sel

if best_delta < 0:
what_type, (a, b) = best_node
if what_type == 'e':
path[a + 1:b] = path[b - 1:a:-1]
return True, path, distance + best_delta
else:
path[a] = not_selected[b]
return True, path, distance + best_delta

return False, path, distance

def node_select(data, dist_matrix, path, node, not_selected):
a, b = node
path.insert(0, path[-2])
if len(path) <= a+2 or len(not_selected) <= b:
path.pop(0)
return 0
current = dist_matrix[path[a]][path[a + 1]] + dist_matrix[path[a + 1]][path[a + 2]] + data['cost'][path[a + 1]]
new = dist_matrix[path[a]][not_selected[b]] + dist_matrix[not_selected[b]][path[a + 2]] + data['cost'][not_selected[b]]
path.pop(0)
return new - current```