在使用 A* 时实现快捷方式（reach）修剪
Implementing shortcuts (reach) pruning while using A*
我正在做一个寻找最短路径的项目。我查看了很多在线资源来想出一个好的算法。
我正在处理 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.
看看 GraphHopper project (where I'm the author of) or other routing projects for OSM 已经这样做了。这个想法是计算一个节点作为成员的方式的数量，如果节点的数量为三个或更多（或者如果一个节点 'junction' 则只有一个）。
仍然应该可以访问中间的节点，因为您需要在计算路线后为最终结果绘制路线。在 GraphHopper 中我们称它们为支柱节点（路口之间的节点）和塔节点（路口）。 Here是更详细的信息。
另一个问题是您必须计算 GPS 精确路线，而不仅仅是从路口到路口的路线。查看 this change 我们如何通过虚拟节点和边缘解决此问题。
我正在做一个寻找最短路径的项目。我查看了很多在线资源来想出一个好的算法。
我正在处理 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.
看看 GraphHopper project (where I'm the author of) or other routing projects for OSM 已经这样做了。这个想法是计算一个节点作为成员的方式的数量，如果节点的数量为三个或更多（或者如果一个节点 'junction' 则只有一个）。
仍然应该可以访问中间的节点，因为您需要在计算路线后为最终结果绘制路线。在 GraphHopper 中我们称它们为支柱节点（路口之间的节点）和塔节点（路口）。 Here是更详细的信息。
另一个问题是您必须计算 GPS 精确路线，而不仅仅是从路口到路口的路线。查看 this change 我们如何通过虚拟节点和边缘解决此问题。