在地图上为一组坐标创建最佳路线

Question

我有一组坐标，我将从一个位置的地址中提取坐标。 现在，我的任务是为这些点生成最佳路径。 我怎样才能完成这项任务？我见过两点生成路线的例子。但是当有多个目的地被覆盖时，我无法想象它在更大的范围内。 我正在使用此功能的Android应用程序。

Answer 1

如果您必须以特定顺序访问它们，问题可以简化为解决两点的路径：使用相邻坐标对以相同方式简单解决问题，然后将路径连接起来，将起点连接到终点。

如果您必须以任意顺序访问它们并优化行进距离，那么您正在解决实际上是NP-Hard的traveling salesman problem。唯一确切的解决方案是尝试所有排列，事实上，它与前一种情况相似，但是对于大量点而言，练习需要太多时间。首先，解决每对点的最短路径，只保留距离以节省内存。这将需要n（n-1）/ 2次操作。接下来，使用之前计算的数据生成坐标集的每个排列并计算与它们相关的路径。具有最小距离的置换（以及与其相关的路径）将是您的最佳序列。再次使用第一段中提到的方法生成路径。

该算法的第一步似乎很费时，但实际上它是第二步是非多项式。有非确切的解决方案运行速度更快，但它们的可靠性各不相同。您将必须使用试验和错误来决定它们是否适合您的应用程序。

Answer 2

这是一种 “寻路” 或 “路由” 问题：

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

这是更快，更高效。

这里有几个寻路/路由引擎。最好的一个可以说是开源路由机械：

http://project-osrm.org/

你可以多找几个引擎在那里。只是谷歌周围的“地图路由”或“寻路”。

通常，引擎是一个（RESTful）Web服务，您必须通过网络访问，而不是您可以嵌入到Java/Android项目中的库。