Rearrange a list of points to reach the shortest distance between them [closed]

Question

I have a list of 2D points for example:

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

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.

What is the most pythonic way to achieve this?

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.)

Answer 1

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]

Output:

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

Note that the reverse path is an equivalent minimum

Answer 2

The other answer here is correct that this is some class of NP problem. If you really need 1000 nodes, there's no way you're ever going to truly solve it. But does it need to be exact? If not, perhaps you can try to just pick a random point and walk from there to the nearest point each time? It's not guaranteed to give you the shortest path, but perhaps it's close enough. E.g.:

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

This is O(n^2) in distance computations and comparisons, and only O(n) in memory, which is at least achievable for 1000 points.