求Python坐标系中某些点之间的最短路径

Question

我写了一段代码，可以在坐标系中的特定宽度和长度范围内生成所需数量的点。它计算并列出我使用欧几里德方法生成的这些点的距离矩阵。

我的代码在这里：

import pandas as pd
from scipy.spatial import distance_matrix, distance

import random

npoints = int(input("Type the npoints:"))
width = float(input("Enter the Width you want:"))
height = float(input("Enter the Height you want:"))

sample = []
for _ in range(npoints):
    sample.append((width * random.random(), height * random.random()))
print(*[f"({w:.2f}, {h:.2f})" for w, h in sample], sep=', ')

mat_dist = distance.cdist(sample, sample, 'euclidean')
df_mat_dist = pd.DataFrame(mat_dist)
print(df_mat_dist)

输出为：

Type the npoints:5
Enter the Width you want:6
Enter the Height you want:7
(3.25, 3.55), (5.51, 6.47), (5.87, 5.31), (2.27, 3.20), (0.96, 3.83)
          0         1         2         3         4
0  0.000000  3.690201  3.153510  1.047022  2.305800
1  3.690201  0.000000  1.209096  4.608588  5.257688
2  3.153510  1.209096  0.000000  4.176733  5.123103
3  1.047022  4.608588  4.176733  0.000000  1.450613
4  2.305800  5.257688  5.123103  1.450613  0.000000

Process finished with exit code 0

我想创建一种算法，从输入的随机点开始，绕过最短路径中的所有点。（最近邻法继续根据欧氏距离找到距离起点最近的点，然后在未纠缠的点中，找到离这个新点最近的点，一直这样下去，直到遍历完所有点，完成一轮).我怎样才能在 10 个不同的点重复这个过程 10 次并得到这样的输出：

Tour Number:1
Number of points visited in order in the relevant round: 0-7-3-8-2...
Total route length of the tour: 18,75755

Tour Number:2
The number of the points visited in order in the relevant round: 6-9-11-2-7...
Total route length of the tour: 14,49849
.
...

非常感谢您的帮助。

Answer 1

如果我没有正确理解你的问题，这应该可以解决单一路径的问题。

import random
import pandas as pd
from scipy.spatial import distance_matrix, distance

npoints = int(input("Type the npoints: "))
width = float(input("Enter the Width you want: "))
height = float(input("Enter the Height you want: "))

sample = []
for _ in range(npoints):
    sample.append((width * random.random(), height * random.random()))
print(*[f"({w:.2f}, {h:.2f})" for w, h in sample], sep=', ')

mat_dist = distance.cdist(sample, sample, 'euclidean')
df_mat_dist = pd.DataFrame(mat_dist)
print(df_mat_dist)

#Randomly select the first point
closest_idx = random.randrange(npoints)
path_points = [closest_idx]

#Find the closest point to the starting point, different from diagonal and save results
path_length = 0

for _ in range(npoints-1):
    closest_dist = df_mat_dist.loc[closest_idx, ~df_mat_dist.index.isin(path_points)].min()
    closest_idx = df_mat_dist.loc[closest_idx, ~df_mat_dist.index.isin(path_points)].idxmin()
    path_points.append(closest_idx)
    path_length += closest_dist

print(path_points, path_length)

输出

Type the npoints: 5
Enter the Width you want: 6
Enter the Height you want: 7
(2.45, 6.66), (3.01, 3.94), (5.06, 0.51), (5.89, 1.04), (1.37, 5.03)
          0         1         2         3         4
0  0.000000  2.775327  6.677550  6.587089  1.950042
1  2.775327  0.000000  3.993631  4.086550  1.970787
2  6.677550  3.993631  0.000000  0.988898  5.834766
3  6.587089  4.086550  0.988898  0.000000  6.030719
4  1.950042  1.970787  5.834766  6.030719  0.000000
[1, 4, 0, 3, 2] 11.49681560383563

由此您应该能够将代码调整为运行 10 次。

求Python坐标系中某些点之间的最短路径

Finding the Shortest Path Between Certain Points in the Coordinate System in Python

python

for-loop

data-structures

shortest-path

nearest-neighbor

输出