A *搜索算法卡住

Question

我正在尝试实现A *搜索算法。就目前而言，我只是想通过散布着墙壁的环境找到一条好路径。墙壁是随机生成的，在某些情况下，我的路径会“卡住”。如果搜索遇到它前面的一面墙以及它的所有面（除了导致它进入这个混乱的面），它就会停止。 有什么我可以做，以防止这种情况？我正在使用一个“作为乌鸦”的点数系统来表示我的H值，它忽略了墙壁，只是估计到达目的地需要多长时间。这有时会导致它陷入这个陷阱。

感谢。

Answer 1

低估A *的距离是'正确的'。

但它听起来像你有深度/广度问题。

评估某个特定位置的选项时，应该将它们添加到选项列表中，以便按照评分对它们进行检查和排序。在评估该位置后，您应该没有理由立即检查某个特定位置的可用选项 - 即每个位置的所有选项都应该放入同一个列表中。这样，当你遇到死胡同时，它根本不会产生更多的选择，并且通过从列表中取下一个最高评分选项并对其进行评估。

Answer 2

如果它被引入死胡同，它应该不成问题。你的A *算法应该简单地找到下一个非阻塞的节点，它具有最低的启发式并重新开始。

Answer 3

考虑状态空间就像有向无环图一样，如果A *遇到一个不是终端节点的叶节点，它不应该是一个问题，因为该节点已经被移动到了关闭状态名单。

如果您的A *实现在遇到非终端（目标）叶节点后立即停止，并且其他节点仍在打开列表中，那么您的A *实现不正确。