Untitled
unknown
python
2 years ago
2.1 kB
6
Indexable
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
Editor is loading...