重新排列一个点列表以获得它们之间最短的距离

Question

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

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

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

最Pythonic的方法是什么？

我考虑计算任何项与任何其他项之间的距离，并每次选择最小值，但这将是我正在处理的列表上的缓慢算法（1000个项目不会很少见）。

- Thomas O

---

可能类似于点之间最短距离算法，即首先按X坐标对列表进行排序（快速），然后根据距离进行冒泡排序。 - PP.

将列表排序，以便它们之间的距离最小化。这里的“它们之间”是指相邻点之间的距离吗？ - jscs

如果你试图最小化相邻点之间的距离，那么你正在探讨旅行商问题，它没有高效的解决方案；你只能尝试所有排列，并找出哪个是最短的。 - Josh Buell

点的坐标在两个轴上总是整数吗？它们被限制在某个范围内吗？ - Bitwise

@JoshBuell 这实际上是在平面上使用欧几里得距离的TSP问题。不幸的是，已经证明即使这个“简化”版本也是NP难问题。另外请注意，NP难并不意味着您不能改进尝试所有排序的解决方案。 - Bitwise

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

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

- egafni

---

你尝试过为 o.p. 需求测试 1000 点吗？需要多长时间？ - Paddy3118

当我发现我的问题的答案是“这是一个 NP 问题”时，我得出结论说我问错了问题。 - Juh_

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个点至少是可行的。

- JoshG79