如何在节点之间寻找最短路径？

Question

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

- GBleaney

---

@duffymo：Dijkstra会找到起始节点和每个目的地之间的最短路径，而不是访问它们所有的最短旅行路线。 （实际上，“旅行路线”是正确的谷歌词汇。） - Fred Foo

谷歌搜索“最短路径神经网络”... - Keshav Saharia

Answer 1

这个问题的解决方法是引入一个新的图 G':

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

在这个图中（它非常大，因此不要在内存中显式表示它），可以使用类似 A* 搜索的算法找到所需的路径。

- Fred Foo

Answer 2

少量物品

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

为每个位置和您收集的物品组合制作一个节点。

使用Djikstra查找从起点到任何已收集所有物品的节点的最短路径。

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

大量物品

我发现蚁群优化在我最近研究的类似问题中得到了非常好的结果，所以这也值得一看。

- Peter de Rivaz

Answer 3

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

首先，我会为每个节点分配一个权重，该权重基于其到下一个最近资源节点的距离。例如，距离面包节点5个单位、距离沃尔玛节点8个单位的加油站节点将具有权重13；现在前往具有最低权重+距离当前位置的加油站节点。

这种启发式方法的问题在于它没有考虑面包和沃尔玛节点之间的距离-它们可能紧挨着，也可能相距13个单位。另一种启发式方法是找到由加油站-面包-沃尔玛三角形（或正方形或五边形等，取决于您需要访问多少类型的位置）形成的子图的质心，将质心到子图中的点的距离相加，并将其用作顶点权重。

- Zim-Zam O'Pootertoot