python - 重新排列点列表以达到它们之间的最短距离

Question

我有一个二维点列表，例如：

1,1 2,2 1,3 4,5 2,1

这些点之间的距离是已知的（例如使用 math.hypot。）我想对列表进行排序，以便它们之间有最小距离。我可以接受任何可能的解决方案顺序，只要这些点的顺序最短。

实现这一目标的最蟒蛇方式是什么？

我正在考虑计算任何项目与任何其他项目之间的距离，并每次选择最小的，但这在我正在处理的列表中将是一个缓慢的算法（1,000 个项目并不罕见。）

Answer 1

您要问的技术问题类似于“什么是图的最小哈密顿路径”（您的元组是顶点，它们之间的距离是边的权重）。这个问题不能在多项式时间内解决，所以你的数据集最好很小。由于您的图是完整的（所有节点都已连接），因此最小哈密顿路径问题可能并不完全适用。

无论如何，下面的答案使用蛮力。它排列所有可能的路径，计算每条路径的距离，然后得到最小值。

import itertools as it
import math

def dist(x,y):
    return math.hypot(y[0]-x[0],y[1]-x[1])

paths = [ p for p in it.permutations([(1,2),(2,3),(5,6),(3,4)]) ]
path_distances = [ sum(map(lambda x: dist(x[0],x[1]),zip(p[:-1],p[1:]))) for p in paths ]
min_index = argmin(path_distances)

print paths[min_index], path_distances[min_index]

输出：

((1, 2), (2, 3), (3, 4), (5, 6)) 5.65685424949

请注意，反向路径是等效的最小值

Answer 2

这里的另一个答案是正确的，这是一类 NP 问题。如果你真的需要 1000 个节点，那么你永远无法真正解决它。但这需要准确吗？如果没有，也许您可​​以尝试只选择一个随机点，然后每次从那里走到最近的点？不能保证给你最短的路径，但也许它已经足够接近了。例如：

data [ (1,2), (3,4), ... ]

cur = 0
path = [cur]
totalDist = 0
for i in range(1,len(data)):
    dists = [(dist(data[i],p), pi) for (pi,p) in enumerate(data) if pi != i and pi not in path]
    nextDist, cur = min(dists)
    totalDist += nextDist
    path.append(cur)

print path, totalDist

这在距离计算和比较中是 O(n^2)，而在内存中只有 O(n)，这至少对于 1000 个点是可以实现的。