重新排列点列表以使其之间的距离最短 [英] Rearrange a list of points to reach the shortest distance between them

问题描述

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

I have a list of 2D points for example:

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

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

The distance between these points is known (using math.hypot for example.) I want to sort the list so that there is a minimum distance between them. I'm OK with any possible solution order, as long as the points are in the shortest order.

实现此目标的最Python方式是什么?

What is the most pythonic way to achieve this?

我正在考虑计算任何物品与其他物品之间的距离，并每次选择最小的距离，但这在我正在处理的列表上会是一个缓慢的算法(1,000个物品并不稀奇.)

I was considering working out the distance between any item and any other item, and choosing the smallest each time, but this would be a slow algorithm on the lists I am working on (1,000 items would not be unusual.)

推荐答案

您要提出的技术问题类似于什么是图的最小哈密顿路径"(您的元组是顶点，它们之间的距离是边的权重).这个问题无法在多项式时间内解决，因此您的数据集最好较小.由于您的图是完整的(所有节点都已连接)，因此最小哈密顿路径问题可能不会完全适用.

The technical question you're asking is similar to "What is the minimum hamiltonian path of a graph" (your tuples are vertices, and the distance between them are the weight of the edges). This problem can't be solved in polynomial time, so your dataset had better be small. Since your graph is complete (all nodes are connected), the minimum hamiltonian path problem may not completely apply.

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

In any case, the answer below uses brute force. It permutes all possible paths, calculates the distance of each path, and then gets the minimum.

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

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

Note that the reverse path is an equivalent minimum

这篇关于重新排列点列表以使其之间的距离最短的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！