网格迷宫仅四向移动场景下的最短路径算法选型咨询

首先你遇到的A*问题并非算法本身的缺陷，而是实现细节处理不当导致的：

• A*的核心逻辑是通过开放集合（Open Set）维护待探索节点，闭集合（Closed Set）记录已确认最短路径的节点。如果出现无法回溯的情况，大概率是错误地将节点过早放入闭集合，或者在优先级相同时没有选对探索方向。
• 针对四向移动、网格权重为1的场景，Manhattan距离是完全可采纳的启发函数（满足h(n) ≤ h*(n)），理论上A*一定能找到最短路径，不会陷入死路——除非你的闭集合逻辑错误，比如把还没找到最优路径的节点标记为已处理。

修正A*实现的关键要点 #

• 不要过早将节点加入闭集合：只有当你确定当前路径是该节点的最短路径时，才放入闭集合。如果后续发现更优路径（静态网格中虽少见，但优先级相同时的探索顺序可能影响），需要重新将节点移回开放集合。
• 优先级相同时的探索策略：当两个节点的f值（f(n)=g(n)+h(n)）相同时，优先选择h值更小的节点（更靠近目标），或者优先选择未探索过的方向，避免盲目进入死胡同。
• 移除闭集合的冗余性：在很多优化的A*实现中，甚至可以去掉闭集合，只通过开放集合的记录判断节点是否已被探索，避免错误锁死节点。

关于D*-Lite和LPA* #

这两个算法属于动态路径规划算法，主要用于环境会动态变化（比如迷宫中突然出现新墙体、目标位置移动）的场景。如果你的迷宫是静态的（无动态障碍物或目标变化），这两个算法完全没必要，反而会增加复杂度。

替代方案：BFS或Dijkstra #

如果对A*的实现感到棘手，可考虑以下更简单的替代方案：

• BFS：因为网格移动成本均为1，BFS天然能找到最短路径，实现逻辑简单，不需要启发函数。但在大网格中效率不如A*。
• Dijkstra算法：本质是A启发函数h(n)=0的特殊情况，同样能找到最短路径，适合无启发信息的场景，但你有Manhattan距离的前提下，A效率更高。

总结：优先修正你的A实现，这是最适配你场景的算法；如果不想折腾A，用BFS即可满足需求。

内容的提问来源于stack exchange，提问作者StimMarine