algorithm - 如何找到节点之间的最短路径？

Question

我正在开发一个地图应用程序，它可以找到用户想要的东西之间的最短路径。用户想要的每样东西（例如面包或汽油）都有多个可能的位置。目前，我只是在规划用户和每个项目的最接近用户的实例之间的路线，但是；这并不总是最好的路线。如下图所示，最快的路线有时涉及访问更远节点的集群： 对于每个项目，我有多达 50 个可能的节点（位置）。如何规划访问每个节点的最短路径（以任何顺序）？虽然指向如何解决这个问题的具体示例的指针会很棒，但我真正要寻找的只是一个开始解决这个问题的正确方向的点。

Answer 1

可以通过引入一个新图G'来找到该问题的解决方案：

• G'中的节点是通过原始图的简单路径
• 当两个节点对应于部分路径 p 和 p' 时，在两个节点之间存在一条边，可以通过向其添加节点将 p' 扩展为p '。

在这个图表中（它很大，所以不要在内存中明确表示它），您可以使用类似 A* 搜索的方式找到您想要的游览。

Answer 2

少量物品

如果您的项目数量很少，您可以通过在新图表上使用 Djikstra 来解决它。

为每个位置组合和您收集的项目创建一个节点。

使用 Djikstra 找到从起点到收集所有项目的任何节点的最短路线。

对于 L 个位置和 N 个项目，这些新节点将有 L*2^(N-1) 个，因此这仅适用于小 N。

大量项目

我发现蚁群优化对于我最近看到的一个类似问题给出了非常好的结果，所以这可能也值得一看。

Answer 3

您可能想查看本论文的第 3 章，了解解决车辆路径问题的技术概述。

首先，我会根据每个节点到下一个最近的资源节点的距离为每个节点分配一个权重，例如，距离 Bread 节点 5 且距离 Walmart 节点距离 8 的 Gas 节点的权重为 13；现在转到权重最小的 Gas 节点 + 与当前位置的距离。

这种启发式的问题在于它没有考虑 Bread 和 Walmart 节点之间的距离——它们可能彼此相邻，或者它们之间的距离可能达到 13。另一种启发式方法是找到由 Gas-Bread-Walmart 三角形（或正方形或五边形等，具体取决于您需要访问的位置类型）形成的子图的质心，将质心到点的距离相加子图，并将其用作顶点权重。