我有一组坐标，我将从一个位置的地址中提取。现在，我的任务是为这些点生成一条最佳路径。我怎样才能完成这项任务？我已经看到了为两点生成路线的示例。但是当有多个目的地要覆盖时，我无法想象它的规模更大。我正在将此功能用于 android 应用程序。
问问题
687 次
2 回答
0
如果您必须按特定顺序访问它们，则问题可以简化为求解两点的路径：只需使用相邻的坐标对以相同的方式解决问题，然后将连接起点和终点的路径缝合在一起。
如果您必须以任何顺序访问它们并优化行驶距离，那么您正在解决实际上是 NP-Hard的旅行商问题。唯一确切的解决方案是尝试所有排列，实际上，它与前面的情况类似，但是对于大量点的练习将花费太多时间。首先，求解每对点的最短路径，只保留距离以节省内存。这将需要 n(n-1)/2 次操作。接下来，生成坐标集的每个排列，并使用先前计算的数据计算与它们关联的路径。距离最短的排列（以及与之相关的路径）将是您的最佳序列。使用第一段中提到的方法再次生成路径。
算法的第一步可能看起来很耗时，但实际上第二步是非多项式的。有运行速度更快的非精确解决方案，但它们的可靠性各不相同。您将不得不使用反复试验来确定它们是否适合您的应用程序。
于 2012-11-27T12:13:22.443 回答
0
这是一个“寻路”或“路由”问题：
http://en.wikipedia.org/wiki/Pathfinding
并且经常遇到 Dijikstra 的算法：
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
或将其概括称为“A* 算法”：
http://en.wikipedia.org/wiki/A-star_algorithm
最近几年，这些东西已经演变成“收缩层次”算法：
http://en.wikipedia.org/wiki/Contraction_hierarchies
这更快，更有效。
那里有一些寻路/路由引擎。最好的可以说是开源路由机：
你可以在那里找到更多的引擎。只需谷歌搜索“地图路由”或“寻路”。
通常，引擎是您必须通过网络访问的（RESTful）Web 服务，而不是可以嵌入到 Java/Android 项目中的库。
于 2012-11-27T16:59:15.600 回答