我正在尝试实现 A* 搜索算法。现在我只是想在一个到处都是墙壁的环境中找到一条好路。墙壁是随机生成的，在某些情况下，我的路径会“卡住”。如果搜索在它前面遇到一堵墙，并且在它的所有侧面（除了把它带入这个烂摊子的那一面），它就会停止。我能做些什么来防止这种情况发生吗？我正在为我的 H 值使用“如乌鸦飞”点系统，它忽略了墙壁，只是估计到达目的地需要多远。这有时会导致它陷入这个陷阱。
谢谢。
问问题
1517 次
3 回答
2
低估距离对于 A* 来说是“正确的”。
但听起来你有深度/广度问题。
从给定位置评估选项时，您应该将它们添加到选项列表中，以按分数检查和排序它们。没有理由在评估该职位后立即检查给定职位的可用选项 - 即每个职位的所有选项都应放在同一个列表中。这样，当您遇到死胡同时，它根本不会生成更多选项，您可以继续从列表中取出下一个得分最高的选项并对其进行评估。
于 2010-12-14T02:27:14.577 回答
1
将状态空间考虑为有向无环图，如果 A* 遇到不是终端节点的叶节点，这应该不是问题，因为该节点已经被移动到封闭列表中。
如果您的 A* 实现在遇到非终端（目标）叶节点后立即停止，并且还有其他节点仍在打开列表中，那么您的 A* 实现不正确。
于 2010-12-14T02:34:23.737 回答
0
如果它被引入死胡同，那应该不是问题。您的 A* 算法应该简单地找到具有最低启发式的下一个非阻塞节点并重新开始。
于 2010-12-14T02:28:11.303 回答