时间戳

首页 > 解决方案 > 我需要通过选择最接近的排序来减少节点之间的弧数

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

问题描述

我正在处理一个 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)]

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

标签： pythonnumpygurobi

解决方案

首先，您可以使用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]

推荐阅读