在网格状迷宫中只允许移动到相邻节点的最短路径

Question

我搜索了很多不同的算法，但似乎没有一种适合我的情况。

我的情况是：

1. 智能体只能向上、向下、向右、向左（4个方向）移动
2. 代理知道它所在的当前节点和目标节点之间的曼哈顿距离。
3. 代理知道当前节点的邻居和目标节点之间的曼哈顿距离。
4. 移动成本为 1 的网格状迷宫（即每条边的权重为 1）

我尝试使用 A* 算法。但是，问题是，在我的情况下，如果该节点不是当前节点的邻居，则代理无法传送或跳转到优先节点。这意味着当有两个具有相同优先级的节点时，代理可能会选择一个最终进入死胡同的节点（前一个节点处于代理无法移动到的“关闭”或“已解决”集合中，并且代理也被围墙包围）。 换句话说，使用 A* 算法，由于移动限制，回溯是不可能的。

我也看过 D-Lite 和 LPA，但我认为它们不适用于我的情况（或者它们是？）

在这样的设置中应该使用什么寻路算法？谢谢。

Answer 1

A* 正是你想要的算法。您提到的“传送”仅作为搜索的一部分在内部发生。算法的输出是你的单位将采取的路径，不会涉及任何传送。

如果你的单位在四处移动时显示地图，你将需要在每次地图更改时重新运行 A*。这个问题在机器人技术中极为常见，因此 LPA* 正是为这种情况而设计的——它做的事情与 A* 相同，但重复使用先前搜索的信息来加速后续搜索。然而，它的实现也更复杂，所以我建议从普通的旧 A* 开始，只有当 A* 对您的需求来说太慢时才转向 LPA*。