我需要通过选择最近的排序来减少节点之间的弧数

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。如果您想使用 euclidean，则必须先取正方形然后取根，或者使用 @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()}

我需要通过选择最近的排序来减少节点之间的弧数

I need to reduce the number of arcs between nodes by choosing the closests with sort

python

numpy

gurobi