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

问题描述

我知道A *比Dijkstra的算法要好，因为它考虑了启发式值，但是从A *和跳转点搜索(这是在有障碍物的环境中查找最短路径的最有效算法)来看呢?有什么区别?

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?

推荐答案

跳转点搜索是基于图形上某些条件的改进的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.

与A *相比，JPS的改进基本上是，如果您有一个具有统一成本函数的图形(从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屋！