Przegrupuj listę punktów, aby osiągnąć najkrótszą odległość między nimi

Question

Mam listę punktów 2D na przykład:

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

Odległość między tymi punktami jest znany (. Za pomocą math.hypot na przykład) chcę aby posortować listę tak, aby istniała minimalna odległość między nimi. Jestem w porządku z każdą możliwą kolejnością rozwiązań, o ile punkty są w najkrótszej kolejności.

Jaki jest najbardziej pythonic sposób na osiągnięcie tego?

Zastanawiałem się nad wyznaczeniem odległości między dowolnymi przedmiotami i dowolnymi innymi przedmiotami, wybierając za każdym razem najmniejszy, ale byłby to powolny algorytm na listach, nad którymi pracuję (1000 pozycji nie byłoby niezwykłe).

Answer 1

Pytanie techniczne, które zadajesz, jest podobne do "Co to jest minimum hamiltonian path wykresu" (twoje krotki są wierzchołkami, a odległość między nimi jest wagą krawędzi). Ten problem nie może zostać rozwiązany w czasie wielomianowym, więc twój zbiór danych powinien być mały. Ponieważ Twój wykres jest kompletny (wszystkie węzły są połączone), minimalny problem z hamiltonianami może nie mieć zastosowania.

W każdym przypadku poniższa odpowiedź wykorzystuje brutalną siłę. Przekazuje wszystkie możliwe ścieżki, oblicza odległość każdej ścieżki, a następnie pobiera 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] 

wyjściowa:

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

Uwaga że odwrotna droga jest odpowiednikiem minimum

Answer 2

Druga odpowiedź tutaj jest, że to jest jakiś problem klasy NP. Jeśli naprawdę potrzebujesz 1000 węzłów, nie ma szans, że kiedykolwiek naprawdę go rozwiążesz. Ale czy musi być dokładny? Jeśli nie, możesz spróbować wybrać losowy punkt i przejść stamtąd do najbliższego punktu za każdym razem? Nie ma gwarancji, że podasz najkrótszą ścieżkę, ale może jest wystarczająco blisko. Np .:

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 

to O (N^2) do obliczeń odległości i porównań, a tylko O ​​(n) w pamięci, który jest co najmniej do osiągnięcia do 1000 punktów.