寻找最小总距离点的算法，基于位置。

Question

我正在构建一个基于给定一组位置找到“方便的会议点”的应用程序。

目前，我将“方便”定义为“最小化总旅行距离”。这是与寻找重心所示问题不同的问题（为了方便起见，使用笛卡尔坐标而不是纬度和经度）：

• A位于（0,0）
• B位于（0,0）
• C位于（0,12）

这些点的最小总旅行位置为（0,0），总旅行距离为12；重心在（0,4）处，总旅行距离为16（4 + 4 + 8）。

如果将位置限制为一个点，则该问题似乎变得更简单，但这不是我打算拥有的约束条件（与此相似的问题不同）。

我似乎无法想出任何解决此问题的算法-欢迎提出建议！

- Kristian Glass

---

您希望使用哪种语言来实现您的解决方案？ - calebds

Python是理想的选择，但我接受几乎任何不是APL / INTERCAL或类似的编程语言。 - Kristian Glass

Answer 1

这里有一个解决方案，它找到了地理中心点，然后迭代地探索附近的位置以将其调整为最小总距离点。

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

这个问题也非常类似于

所有旅行时间最小的总和

这是一个关于你正在尝试解决的一般问题的维基百科文章:

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

- hatchet - done with SOverflow

---

那个问题以及大部分答案都涉及到“位置是其中一个点”的限制，而我不想要这个限制；然而你提供的链接解决方案似乎可行，谢谢。 - Kristian Glass

@KristianGlass - 请查看维基百科文章，它没有考虑到这个限制，并提到第一个链接的方法是常用的解决方案。 - hatchet - done with SOverflow

所有这些答案似乎都在看几何中位数，这根本没有回答问题。你只需要用L1范数而不是L2范数找到质心即可。 - Cameron Chandler

Answer 2

以某种方式，您似乎正在寻找等权重三角形的重心。这将指向重心坐标系。 当超出三角形时，存在广义重心坐标系的解决方案，并且可以通过修改顶点的权重来为人员设置优先级。但是，这仍然无法考虑实际地图上的距离（不能沿任意方向直线行驶），但可能是一个开始？

- Chris

Answer 3

一种选择是定义一个目标（和梯度）函数，并使用通用优化库，例如scipy.optimize。对于您的问题，fmin_cg将是一个不错的算法。您的目标将是在hatchet引用的Geometric median Wikipedia page的“定义”部分中定义的距离总和。您的目标函数参数为y。

- jrennie