寻找多名旅行者最合适的位置妥协算法

Question

寻找多名旅行者最合适的位置妥协算法

algorithmgeolocation

3

我一直在想，是否已经有一个已知的算法来解决以下问题或至少其中的一部分。

假设有一组有限的位置(x,y)，每个位置还有一个类型（房子、餐厅、咖啡馆、电影院等）和一个权重（用户评级、性价比...）。此外，有一些路径比其他路径更快（取决于交通方式和所需到达时间）。

需要回答的问题是：我们是一群位于n个不同位置的人，我们想在时间T内见面，请找到我们类型为t（电影院...）的最佳位置（最小化每个人的路径长度和旅行时间）。

这听起来像任何已知的算法吗？

此致敬礼， Rolf

- fbiville

我选择笛卡尔坐标系，至少在开始时是这样的，因为我不打算在一个大型网络中实现它。当然，这对于分散在世界各地的人来说是行不通的。 - fbiville

2

只要你喜欢皮划艇，就可以将它延伸到全世界。 :) - mmgp

呵呵 :-) 但笛卡尔坐标和欧几里得几何学并不适合计算地球上的距离（据我远古数学课程所记）:P - fbiville

1

没错，但这是最简单的问题要解决。你需要一些大地测量距离，参见http://www.ga.gov.au/earth-monitoring/geodesy/geodetic-techniques/distance-calculation-algorithms.html。 - mmgp

非常清晰的内容，感谢分享。一个潜在的问题现在已经解决 :) - fbiville

2

有P个人和L（x，y）个位置，您似乎能够计算goTime [i，j] = calcTravel（Pi，Lj，T），其中O（P.L.a） a是算法（如Djikstra），同时消除所有不满足T约束的goTime。然后为每个L计算interest[j]。基于主观标准定义一个函数weight(goTime, interest)，最小化时间，最大化兴趣。取最佳值...这是一个过于简单化的方法吗？ :-) - Déjà vu

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Miguel A. Carrasco · Accepted Answer

有几种算法可以解决这个问题，这个问题被称为设施位置或k中心问题http://en.wikipedia.org/wiki/Facility_location，它是一个NP Hard问题。有一些算法可以近似解决方案，还可以搜索“最优会议点”问题，它在空间数据库中使用。