場所からの最小総距離のポイントを見つけるアルゴリズム

Question

私は、場所の集合を与えられた "便利なミーティングポイント"を見つけることに基づいてアプリケーションを構築しています。

現在、「総走行距離を最小限にする」と「便利」を定義しています。

• Aは、（0,0）
• Bがであるである（0：これは、（デカルト座標ではなく、便宜上、緯度と経度を使用して）次の例で示すように、重心を見つけることから別の問題です、0）
• Cは、（0,12）

でこれらの点の最小総旅行の位置は（0,0になっている）12の総走行距離を持ちます。重心は（0,4）にあり、合計移動距離は16（4 + 4 + 8）である。

場所がポイントの1つに限定されていた場合、問題はより簡単になるように見えますが、これは私が持つ予定の制約ではありません（たとえば、this otherwise similar questionとは異なります）。提案は歓迎してください - 私がやるように見えることはできませんどのような

は、これを解決するためのアルゴリズムの任意の並べ替えを思い付くています！あなたが探しているように見えるどのようにして

Answer 1

は、地理的中心点を見つけ、その後反復最小合計距離点に向かってそれを調整するために近くの位置を探る溶液です。

http://www.geomidpoint.com/calculation.html

この質問はまた、ここで

Minimum Sum of All Travel Times

と非常によく似ていますが解決しようとしている一般的な問題にWikipediaの記事です：

http://en.wikipedia.org/wiki/Geometric_median

Answer 2

は頂点に等しい重みを持つ三角形の重心です。それは重心座標を指すでしょう。

が一般重心座標のためのソリューションがあり、あなたが頂点の重みを変更することによって、人に優先順位を与えることができる三角形を超えて行きます。それでも説明できないことは、実際の地図上の距離です（どんな方向にもまっすぐに進むことはできません）が、それはスタートかもしれません。ここ

Answer 3

1つのオプションは、目的関数（および勾配関数）を定義し、gener ic最適化ライブラリ（scipy.optimizeなど）。 fmin_cgはあなたの問題を解決するのに良いアルゴリズムになります。あなたの目標は、hatchetによって参照されるGeometric median Wikipedia pageの「定義」セクションで定義されている距離の合計です。目的関数の引数はyです。