Untitled

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