Reorganizar una lista de puntos para alcanzar la distancia más corta entre ellos

Tengo una lista de puntos 2D por ejemplo:

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

La distancia entre estos puntos es conocida (usando math.hypot, por ejemplo). Quiero ordenar la lista para que haya una distancia mínima entre ellos. Estoy de acuerdo con cualquier orden de solución posible, siempre que los puntos estén en el orden más corto.

¿Cuál es la forma más pythonica de lograr esto?

Estaba considerando calcular la distancia entre cualquier elemento y cualquier otro, y elegir el más pequeño cada vez, pero este sería un algoritmo lento en las listas en las que estoy trabajando (1,000 elementos no serían inusuales).

La pregunta técnica que está haciendo es similar a “¿Cuál es la ruta hamiltoniana mínima de un gráfico” (sus tuplas son vértices y la distancia entre ellos es el peso de los bordes). Este problema no se puede resolver en tiempo polinomial, por lo que es mejor que su conjunto de datos sea pequeño. Dado que su gráfico está completo (todos los nodos están conectados), es posible que el problema de la ruta hamiltoniana mínima no se aplique por completo.

En cualquier caso, la respuesta a continuación utiliza la fuerza bruta. Permuta todas las rutas posibles, calcula la distancia de cada ruta y luego obtiene el mínimo.

 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] 

Salida:

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

Tenga en cuenta que la ruta inversa es un mínimo equivalente

La otra respuesta aquí es correcta: esta es una clase de problema de NP. Si realmente necesita 1000 nodos, no hay forma de que lo resuelva realmente. ¿Pero tiene que ser exacto? Si no es así, ¿quizás pueda intentar simplemente elegir un punto al azar y caminar desde allí hasta el punto más cercano cada vez? No se garantiza que te dé el camino más corto, pero quizás sea lo suficientemente cerca. P.ej:

 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 

Esto es O (n ^ 2) en los cálculos y comparaciones de distancia, y solo O (n) en la memoria, que es al menos alcanzable para 1000 puntos.