7

我遇到了Jump Point Search，这对我来说似乎很甜蜜。但是，我不确定他们的修剪规则实际上是如何工作的。更具体地说，在图 1 中，它指出

我们可以立即修剪所有灰色邻居，因为这些邻居可以从 x 的父节点以最佳方式到达，而无需经过节点 x

然而，这似乎有些矛盾。在第二幅图像中，可以通过首先通过节点 7 并x完全跳过对称路径来到达节点 5，也就是说，6 -> x -> 5似乎与 对称6 -> 7 -> 5。这与无需通过x第一张图像即可到达节点 3 的方式相同。因此，我不明白这两个图像如何不完全等效，而不仅仅是彼此的旋转版本。

其次，我想了解如何将此算法推广到三维搜索量。

4

3 回答 3

0

我理解这是关于优先事项。为了枚举每个非对称路径，您必须枚举所有节点 - 但您选择哪条路径并不重要，因为它们是对称的。因此，作者决定采用对角线优先——也就是说，任何对角线运动总是出现在路径中的任何直线运动之前。这就是为什么直线有更多的节点被修剪 - 因为它必须在考虑所有对角线之后发生。

于 2012-04-19T13:05:20.897 回答
0

第二张图片显示不正确。如果您看一下随附的文本：“在这两种情况下，我们都可以立即修剪所有灰色邻居，因为这些邻居可以从 x 的父节点以最佳方式到达，而无需经过节点 x。”

强调“两种情况”。

就将概念应用于 3 维空间（或者说，甚至是 n 维空间）而言，该算法与 A* 没有什么不同，因为它只是一个节点和连接的网格。维度完全由您自行决定。

于 2012-04-15T12:17:02.777 回答
0

是的，JPS 很不错，但仅限于具有特定约束的地图：

  1. 地图必须代表一个网格。
  2. 网格中所有可访问的单元格必须具有相同的遍历成本。
  3. 移动代理必须有 8 个可能的行进方向：4 个基本方向和 4 个对角线。

该算法的关键是这些约束允许一些关键假设：

  1. 两点之间的最短几何路线（在没有障碍物的情况下）也是成本最低的路线。
  2. 两点之间的最低成本路径（在没有障碍物的情况下）不需要不止一次改变方向。

这些假设允许算法忽略对称路径选项并按如下方式操作：

  1. 当沿基本方向行驶时，您只需考虑在论文中所示位置之一遇到障碍物时改变方向。这些要考虑改变方向的点是“跳跃点”。
  2. 当沿对角线行驶时，您只需考虑在两个包围“前视”基本方向之一中“看到”跳跃点时改变方向，再次如论文所示。
于 2015-08-19T02:15:02.683 回答