我有100个点，使用距离函数我想寻找最短的路径

Question

import random
radius = 200
rangeX = (0, 2500)
rangeY = (0, 2500)
qty = 100  

s = set()
for x in range(-radius, radius+1):
for y in range(-radius, radius+1):
if x*x + y*y <= radius*radius:
s.add((x,y))
rp = []
excluded = set()
i = 0
while i<qty:
x = random.randrange(*rangeX)
y = random.randrange(*rangeY)
if (x,y) in excluded: 
continue
rp.append((x,y))
i += 1
excluded.update((x+dx, y+dy) for (dx,dy) in s)
#This is to find 100 random points based on the range and the radius

import math
points = rp

paths = ((0, 1, 2, 3), (0, 1, 3, 2), (0, 2, 1, 3), (0,2, 3, 1), (0, 3, 1, 2), (0, 3, 2, 1))
def dist(p1, p2):
return math.sqrt((p2[0]-p1[0])**2 + (p2[1]p1[1])**2)
distances = []

for path in paths:
distances.append(dist(points[path[0]], points[path[1]]) +
dist(points[path[1]], points[path[2]]) +
dist(points[path[2]], points[path[3]]) +
dist(points[path[3]], points[path[0]]))

print(f"the shortest path is {min(distances):.2f} cm and the longest path is {max(distances):.2f} cm")
#this allows the points from the 100 random points function to passed it going through the equation

到目前为止，我遇到了一些问题，运行100点代码所需的时间很长，这使得代码效率低下，我还需要一种方法让我知道什么路线"构成最短路径的所有点"；允许距离最短，而不仅仅是向我显示最短的路径。

提前感谢您的帮助。

Answer 1

要发现代码运行缓慢的地方，最简单的方法是添加几个time1 = time.time()并在print("1->2:", time2-time1)末尾打印差异
通过这样做，我发现99999%的时间都花在了while i<qty循环中
我删除了excluded.update行，代码立即运行
我不理解你的代码(也没有花时间去做(，但那一行扼杀了你的效率。您正在添加400平方米的新点，100次
你应该寻找一个聪明的方法来避免这样做。如果你不知道怎么做，这将是一个在另一篇帖子中问的确切问题(解释你在做什么以及为什么(。

至于打印哪个路径最短，哪个路径最长，这很容易：对于每个路径，您都要计算其长度，因此最终会得到一个包含6个值的distances，每个值对应一个值，顺序相同。所以我们可以把它们放在一起zip：

print(*zip(distances, paths))
# (5937.1207124153025, (0, 1, 2, 3))
# (7675.498300727197, (0, 1, 3, 2))
# (5715.663112364403, (0, 2, 1, 3))
# (7675.498300727197, (0, 2, 3, 1))
# (5715.663112364404, (0, 3, 1, 2))
# (5937.1207124153025, (0, 3, 2, 1))

并依靠Python的元组排序来返回我们想要的：

shortest_path_length, shortest_path = min(zip(distances, paths))
longest_path_length, longest_path = max(zip(distances, paths))
print(f"the shortest path is {shortest_path_length:.2f} cm : {shortest_path}")
print(f"the longest path is {longest_path_length:.2f} cm : {longest_path}")
# the shortest path is 5715.66 cm : (0, 2, 1, 3)
# the longest path is 7675.50 cm : (0, 2, 3, 1)

提示：您可以使用random.seed使运行具有可复制性。在调用rendom函数之前，只需添加random.seed(42)(或您喜欢的任何数字(，您就可以设置了。