A* 曼哈顿距离

Question

我搜索了A*算法/伪代码，按照它的步骤编写了代码。我使用曼哈顿距离作为h(n)的评估函数（f(n) = g(n) + h(n)）。以下是结果，
_{（来源：uploadir.com）} 当没有墙阻挡路径时，这种情况总是发生。但是当我放置了很多墙壁时，似乎它选择了最短路径。这是最短路径吗？为什么不像下面这个呢？
_{（来源：uploadir.com）} 这个也是A*曼哈顿算法，它们的大小都是一样的（19x19）。这个来自http://qiao.github.com/PathFinding.js/visual/。

- Zik

---

嗯，距离是一样的，33个立方体...除非我数错了。 - Samy Vilar

由于你不能斜着走，所以你不会比第一个例子更短。你可以找到许多其他方式（例如第二种方式）具有相同的距离和看起来更短，但它们实际上并不是更短的。对于你提供的这些例子，你总是需要向右移动16个块并向下移动16个块。 - Nobody moving away from SE

啊，原来还有其他的最短路径。 - Zik

我的意思是，第一个也是最短路径，但第二个看起来更短，因为路径直接通往目标。 :) - Zik

这是最优距离，因为您不使用对角线。如果您为每个单元格选择8个邻居，则路径将从起点到终点成为对角线。 - Mensur Grišević

Answer 1

两条路径的曼哈顿距离相同。因此，选择哪条路径取决于实现方式。要解释为什么选择了这个特定部分，我们需要查看此特定A*实现的代码。

提示：从源单元格到目标单元格的每条仅使用Von Neumann neighborhood（即不对角行走）且不朝“错误”方向迈出步伐（例如，在您的示例中从未向上或向左行走）的路径具有相同的曼哈顿距离。因此，如果您在纽约，无论您选择哪个十字路口到达曼哈顿的某个地方都没有关系 :)

- gexicide

---

那么第一个仍然是最短路径之一吗？ - Zik

Answer 2

使用曼哈顿距离，第一个路径是最短的。它只是计算水平和垂直步数的数量。如果你想要看起来更像欧几里得距离的最短路径，你可以尝试改变你的算法，使得当它在某一点有水平或垂直移动的选择时，如果水平距离大于垂直距离，就选择水平移动，反之亦然。

- nhkode

Answer 3

你需要从起点到每个曼哈顿/A*结果的每个点投射一个视线（勾股/欧几里得距离），直到完成。如果向某个点投射一条线被障碍物阻挡/隐藏，你就使用之前投射的点并从该阻塞点开始再次投射另一条线，直到完成。

当一个点被线段/线的初始点的视线所遮挡时，它就是一个阻塞点。

因此，它就像这样：

第一条线：起点--------->S+N（在阻塞点之前）

第二/中间线：阻塞点---------->S+N（在另一个阻塞点之前）重复以上步骤（新的线段/线）直到建立起与目标的视线。

最后一条线：阻塞点------------->目标

连接所有线条，你就得到了更短的最短路径。你可以再次执行，但反过来以增加另一个精度，这样视线将从目标开始直到起点。

- D.R.Bendanillo