最小総距離ですべてのドットを接続するアルゴリズム

Question

私は、ポイントのセットとポイントの各ペアに適用される距離関数を持っています。私は最小の合計距離で、すべてのポイントを一緒に接続したいと思います。あなたはそれに使用できる既存のアルゴリズムについて知っていますか？

各点はいくつかのポイントにリンクさせることができるので、これは通常の「セールスマンの旅程」の問題:)

おかげではありません！

Answer 1

希望するものはです。

1を生成するための2つの最も一般的なアルゴリズムは以下のとおりです。

• Prim's algorithm
• Kruskal's algorithm

Answer 2

探しているアルゴリズムを最小スパニングツリーといいます。水、電話、または電力網の最低コストを見つけることは有益です。 PrimのアルゴリズムやKruskalアルゴリズムがあります。 IMO Primのアルゴリズムは少しわかりやすいです。

Answer 3

ここ

http://en.wikipedia.org/wiki/Minimum_spanning_treeあなたが最小スパニングツリーに関する詳細な情報を見つけることができますので、あなたにそれを適応させることができますあなたの問題を解決してください。

Answer 4

ダイクストラのアルゴリズムを見てみましょう：

ダイクストラ法、1956年にオランダのコンピューター科学者Edsgerダイクストラによって考え出さと1959年に出版さは、グラフのための単一ソース最短経路問題を解くグラフ探索アルゴリズムであります非負のエッジパスコストで最短パスツリーを生成します。このアルゴリズムは、他のグラフアルゴリズムのルーティングやサブルーチンとしてよく使用されます。

http://en.wikipedia.org/wiki/Dijkstra「s_algorithm

Answer 5

他の人が言ったように、minimum spanning tree（MST）は、あなたのすべての点を結ぶ最短距離のサブグラフを形成することができるようになります。

まず、データセットのグラフを作成する必要があります。無向グラフを効率的に作成するには、ポイントセットのDelaunay triangulationを計算することができます。三角測量からグラフへの変換は、かなりリテラルです。三角測量のどの辺も、三角測量エッジの長さで重み付けされたグラフの辺です。

MST（Prim/Kruskal's O(E*log(V))）とDelaunay三角測量（Divide and Conquer O(V*log(V))）フェーズの両方に効率的なアルゴリズムがあるため、効率的な全体的なアプローチが可能です。

これが役に立ちます。