重新排列點的列表，以達到他們之間的最短距離

我有例如2D點的列表：重新排列點的列表，以達到他們之間的最短距離

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

這些點之間的距離被稱爲（例如使用math.hypot）我想對列表進行排序，以便它們之間有最小距離。對於任何可能的解決方案訂單，只要點數是最短的，我都可以。

什麼是達到這個最pythonic方式？

我正在考慮研究任何物品與其他物品之間的距離，並且每次選擇最小的物品，但這對我正在處理的物品清單來說是一個很慢的算法（1,000件物品並不罕見）

來源

2013-08-16 Thomas O

可能類似於[點間最短距離算法]（http://stackoverflow.com/questions/1602164/shortest-distance-between-points-algorithm），即按X座標先排序（快速）然後根據距離進行冒泡排序。 –

«對列表進行排序，以便它們之間存在最小距離»「_them_」之間的含義是「連續點之間」？ –

如果你想盡量減少連續點之間的距離，你會問到旅行商問題，它沒有有效的解決方案;你只需要嘗試所有的排序，看看哪一個是最短的。 –

你問的技術問題類似於「什麼是圖的minimum hamiltonian path」（你的元組是頂點，它們之間的距離是邊的權重）。這個問題不能用多項式時間來解決，所以你的數據集最好是小的。由於你的圖是完整的（所有節點都連接），最小哈密爾頓路徑問題可能並不完全適用。

在任何情況下，下面的答案都使用強力。它排列所有可能的路徑，計算每條路徑的距離，然後得到最小值。

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

注意，反向路徑是等效的最低

來源

2013-08-16 19:50:58 egafni

你有沒有嘗試過1000點作爲o.p.需要嗎？它花了多少時間？ – Paddy3118

當我發現我的問題的答案是「這是NP問題」時，我得出結論說我提出了錯誤的問題 –

對方回答這裏是正確的，這是一些類NP問題。如果你真的需要1000個節點，你不可能真正解決它。但是它需要準確嗎？如果不是，也許你可以試着隨便挑一個點，然後從那裏走到最近的點？不保證給你最短的路徑，但也許它足夠接近。例如爲：

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

這是在距離計算和比較爲O（n^2），和只爲O（n）的存儲器，其至少可實現爲1000點。

來源

2013-08-16 20:59:02 JoshG79

重新排列點的列表，以達到他們之間的最短距離

回答

相關問題