0

问题是要找到一个点，使不同地区的大约 100 个想要在同一个地方见面的人的旅行距离最小化。旅行是乘汽车而不是乘飞机。

假设我可以访问一个 API，为我提供任意两点之间的高速公路行驶里程/公里距离，我怎样才能找到最好的会面地点？

在其他 Stackexchange 网站（gis.stackexchange.com/questions/65563/meeting-point-minimizing-travel-distance-for-participants）上，我被定向到 Weiszfeld 算法来解决这个几何中位数问题。

我怀疑千米距离会使问题复杂化，因为有可能陷入局部最小值。我真的不知道从哪里开始。任何指针将不胜感激。

4

2 回答 2

1

即使它可能受到局部最小值的影响，我也会尝试局部搜索，因为道路网络不是对抗性设计的。选择一个随机起点，然后按如下方式迭代。计算从当前点到 100 个客户端的方向。评估方向上的每个倒数第二个停靠点，并将该点移动到最佳位置。

于 2013-07-09T13:23:55.940 回答
0

如果考虑的距离是曼哈顿距离，则最佳会合点是 x 坐标等于某个输入点的 x 坐标且 y 坐标等于某个输入的 y 坐标的点之一观点。

于 2013-07-09T11:28:57.843 回答