我需要通过选择带有排序的闭包来减少节点之间的弧数

Question

我正在处理一个tsp问题，因为执行需要很长时间，所以我决定通过只为每个节点选择5个最接近的位置来减少弧的数量。我开始使用sort来解决我的问题，但我不太了解如何使用它。我的代码是：

import numpy as np
import pandas as pd
from numpy import random
n = 21  # Houses
N = [i for i in range(n)]

arcs = [(i, j) for i in N for j in N if i != j]  
# random coordenates 
list_coord_x = [random.randint(100) for i in N]
list_coord_y = [random.randint(100) for i in N]
df = pd.DataFrame({
"coord_x": list_coord_x,
"coord_y": list_coord_y
})
# Distances for each arc
D = {(p, j): abs(df["coord_x"][p]-df["coord_x"][j]) + abs(df["coord_y"][p]-df["coord_y"][j]) for p, j in arcs}  

我的目标是将圆弧减少到最接近的5，这样程序运行得更快。在这个例子中，我的弧线是：

arcs = [(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (0, 9), (0, 10), (0, 11), (0, 12), (0, 13), (0, 14), (0, 15), (0, 16), (0, 17), (0, 18), (0, 19), (0, 20), .................................., (20, 3), (20, 4), (20, 5), (20, 6), (20, 7), (20, 8), (20, 9), (20, 10), (20, 11), (20, 12), (20, 13), (20, 14), (20, 15), (20, 16), (20, 17), (20, 18), (20, 19) ]

例如，我想要

reduced_arcs = [(0, 1), (0, 7), (0, 8), (0, 10), (0, 14), (1, 3), ....., (20, 3), (20, 4), (20, 10), (20, 11), (20, 12)]

因为这些弧线是它们之间最接近的。

Answer 1

首先，您可以使用scipy.spatial.distance_matrix来计算距离矩阵：

import numpy as np
from scipy.spatial import distance_matrix
points = [(x, y) for x,y in zip(list_coord_x, list_coord_y)]
D = distance_matrix(points, points)

然后，您可以使用距离矩阵D，提取每行(节点(的5个最低距离条目的索引：

x_indices, y_indices = np.where(np.argsort(D) < 5) 
reduced_arcs = [(i, j) for i, j in zip(x_indices, y_indices) if i != j]

Answer 2

我建议您处理numpy或pandas中的数据，因为这在dict中是不必要的困难。由于您的示例中已经有pandas代码，您可以在没有新导入的情况下使用此代码。在您的示例中，您使用Taxicab Geometry。如果你想使用欧几里得，你必须取平方，然后求根，或者使用@joni建议的函数。

pd_D = pd.DataFrame.from_dict(((k[0],k[1],v) for k,v in D.items())) # so you have 
pd_D.columns = ['from','to','distance']
pd_D_reduced = pd_D.groupby('from').apply(lambda x: x.nsmallest(n=5, columns='distance'))
pd_D_reduced.droplevel(0) # to ungroup
# back to dict if you want it
D_reduced = {(row['from'],row['to']):row['distance'] for index, row in pd_D_reduced.iterrows()}