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

Question

我有一个2D点列表,例如:

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

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

实现这一目标的最pythonic方法是什么？

我正在考虑计算任何项目和任何其他项目之间的距离,并且每次都选择最小的项目,但这对我正在处理的列表来说是一个缓慢的算法(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

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