# Untitled

unknown
python
a year ago
2.1 kB
0
Indexable
Never
```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```