A*跳点搜索 - 剪枝是如何实现的？

Question

我发现 Jump Point Search，似乎对我很有用。然而，我不确定它们的修剪规则实际上是如何工作的。更具体地说，在图1中，它指出：

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

但是，这似乎有些不一致。在第二个图像中，节点5可以通过首先通过节点7并完全跳过x来到达-也就是说，6 -> x -> 5 看起来对称于 6 -> 7 -> 5。这与第一个图像中可以不经过x到达节点3的方式相同。因此，我不明白为什么这两个图像不完全等价，而不仅仅是彼此旋转。

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

- Puppy

---

我上周一直在研究同一个算法，也发现图片很令人困惑。你考虑过给丹尼尔·哈拉博尔发邮件询问吗？ - Fred Foo

@larsmans：我有一个关于它的想法。来C++聊天室，我会讨论一下。 - Puppy

第一张图片是有意义的，因为它只考虑了水平和垂直移动，而没有考虑对角线。因此，在这个限制条件下，修剪是有意义的。但是，像你说的那样，第二张图片对我来说没有意义。 - Magnus

Answer 1

是的，JPS很好，但仅限于具有特定约束条件的地图：

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

算法的关键在于这些约束条件允许做出一些关键的假设：

1. 两点之间的最短几何路径（在没有障碍物的情况下）也是一条最小成本路径。
2. 两点之间的最小成本路径（在没有障碍物的情况下）不需要有多个方向变化。

这些假设使算法能够忽略对称路径选项并按以下方式运行：

1. 当沿着基本方向行进时，只有在遇到论文中所示的某些位置的障碍物时才需要考虑方向变化。这些需要考虑方向变化的点称为“跳点”。
2. 当沿对角线行进时，只有在两个括号“前瞻”基本方向中的一个中可以“看到”跳点时才需要考虑方向变化，同样如论文所示。

- Terrible Tadpole

Answer 2

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

- Puppy

Answer 3

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

重点在于“这两种情况”。

就将该概念应用于三维空间（甚至是n维空间）而言，该算法与A *没有任何区别，因为它只是节点和连接的网格。维度完全由您自行决定。

- Scott Maskiel

---

我不相信这是真的。如果第二张图片只是第一张图片的旋转版本，那么为什么要同时显示两张呢？为什么不只显示第一张呢？此外，图3中的系列也展示了一个不等式。 - Puppy