algorithm - 在使用 A* 时实现快捷方式(reach)修剪

Question

我正在做一个寻找最短路径的项目。我查看了很多在线资源来想出一个好的算法。

我正在处理 openstreetmap 数据，我很清楚我必须使用 A* 算法。

在寻找不同的解决方案时，我发现因为一条路是由不同的节点组成的，所以可以剪掉不是连接点的中间节点。我怎样才能用编程语言做到这一点？如果有人有想法或可以帮助我的进一步文章，那将非常感激。

我找到的关于这个与osm相关的修剪的确切信息是这个

parse all ways a second time; a way will normally become one edge, but if any nodes apart from the first and the last have a link counter greater than one, then split the way into two edges at that point. Nodes with a link counter of one and which are neither first nor last can be thrown away unless you need to compute the length of the edge.

Answer 1

查看 GraphHopper project (我是作者)或其他 routing projects for OSM已经这样做了。这个想法是计算一个节点是成员的方式的数量，如果节点的数量为三个或更多(或者如果是一个结束的“连接”，则只有一个)将节点标记为连接。

仍然应该可以访问中间的节点，因为您需要在计算路线后为最终结果绘制路线。在 GraphHopper 中我们称它们为支柱节点(路口之间的节点)和塔节点(路口)。 Here是更详细的信息。

另一个问题是您必须计算 GPS 精确路线，而不仅仅是从路口到路口的路线。查看this change我们如何通过虚拟节点和边缘解决这个问题。