7

たとえば、2D ポイントのリストがあります。

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

これらのポイント間の距離はわかっています (たとえば、math.hypot を使用します)。それらの間の距離が最小になるようにリストを並べ替えたいと思います。ポイントが最短の順序である限り、可能なソリューションの順序で問題ありません。

これを達成するための最もpythonicな方法は何ですか?

アイテムと他のアイテムの間の距離を計算し、毎回最小のものを選択することを検討していましたが、これは私が取り組んでいるリストでは遅いアルゴリズムになります (1,000 アイテムは珍しいことではありません.)

4

2 に答える 2

2

ここでの他の答えは、これがある種の 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-16T20:59:02.487 に答える