寻路算法:A* Vs 跳转点搜索 [英] Path finding Algorithms : A* Vs Jump Point Search

问题描述

我知道 A* 比 Dijkstra 的算法更好，因为它考虑了启发式值，但是从 A* 和 Jump Point 搜索来看，哪个是在有障碍物的环境中找到最短路径的最有效算法?有什么区别?

I know that A* is better than Dijkstra's algorithm because it takes heuristic values into account, but from A* and Jump Point search which is the most efficient algorithm for finding the shortest path in an environment with obstacles? and what are the differences?

推荐答案

Jump Point Search 是基于图形上的某些条件改进的 A*.因此，如果您满足这些条件(主要是均匀成本网格)，则 JPS 绝对优于 A*(相同的最优性，最好的情况可以好几个数量级，最坏的情况可能具有相同的复杂性，但是一个稍差的常数)，但如果不满足条件，则无法使用.

Jump Point Search is an improved A* based on some conditions on the graph. Thus, if you meet these conditions (uniform-cost grid mostly), JPS is strictly better than A* (same optimality, best cases can be order of magnitudes better and worse case is probably the same complexity but with a slightly worse constant), but if you do not meet the conditions, you cannot use it.

JPS 对 A* 的改进基本上是，如果你有一个具有统一成本函数的图(从 A 到 B 和从 B 到 C 的成本相同，在同一方向)，你可以跳过一些在某些情况下，直接从 A 到 C，而无需扩展 B 中的节点.

The improvements of JPS over A* is basically, if you have a graph with an uniform cost function (it costs the same to go from A to B and from B to C, in the same direction), you can skip some steps in some cases and go directly from A to C without expanding nodes in B.

JPS 是 A* 上的修剪技术，您可以删除不需要评估的案例，因为您知道它们将是次优的.您知道这一点是因为统一成本网格条件.
从概念上讲，这相当于在非均匀网格上使用 A*，其中相邻节点表示您可以在不遇到障碍物的情况下在该方向上走多远，以及您执行跳跃的成本.因此，如果您可以向右走 10 个节点而不会遇到障碍，则可以减少(或直接跳到)一个成本为 10*c 的单个节点，其中 c 是从一个节点到另一个节点的(恒定)成本另一个在右边.

JPS is a pruning technique over A*, you remove cases you do not need to evaluate, because you know they will be sub-optimal. You know this because of the uniform-cost grid condition.
Conceptually, this is equivalent to using A* over a non uniform grid, where neighbouring nodes represent how far you can go in that direction without encountering an obstacle, with the cost of the jump you performed. So if you can go 10 nodes on the right without encountering an obstacle, you can reduce this (or jump directly to) a single node with a cost of 10*c, where c is the (constant) cost to go from one node to another on the right.

原始论文可以在这里找到.

这篇关于寻路算法:A* Vs 跳转点搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！