A* 搜索算法陷入困境
我正在尝试实现 A* 搜索算法。现在我只是想在充满墙壁的环境中找到一条好路。墙壁是随机生成的，在某些情况下我的路径会“卡住”。如果搜索在其前面及其所有侧面（除了导致其陷入混乱的那一侧）遇到一堵墙，它就会停止。 我可以采取什么措施来防止这种情况发生？我对 H 值使用“直线上升”点系统，该系统忽略墙壁，仅估计到达目的地所需的距离。这有时会导致它陷入这个陷阱。
谢谢。
I am trying to implement an A* Search algorithm. For now I am just trying to find a good path through an environment littered with walls. The walls are randomly generated, and in some cases my path gets "stuck". If the search encounters a wall in front of it, and to all of its sides (except the one that led it into this mess), it stops.
Is there something I can do to prevent this? I am using a "as the crow flies" point system for my H value, which ignores the walls and just estimates how far it will take to get to the destination. This sometimes leads it into this trap.
Thanks.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
对于 A* 来说，低估距离是“适当的”。
但听起来你有深度/广度问题。
当从给定位置评估选项时，您应该将它们添加到选项列表中以按分数对其进行检查和排序。在评估给定位置后，您没有理由立即检查该位置的可用选项 - 即每个位置的所有选项都应进入同一列表。这样，当您遇到死胡同时，它根本不会生成进一步的选项，您可以通过从列表中取出下一个得分最高的选项并对其进行评估来继续。
Underestimating the distance is 'proper' for A*.
But it sounds like you have a depth/breadth problem.
When evaluating options from a given position, you should add them to a list of options to check and sort them by score. There should be no reason why you would check the options available from a given position immediately after you've evaluated that position - i.e. all options from each position should go into the same list. This way, when you hit a dead end, it simply does not generate further options and you proceed by taking the next highest scored option off the list and evaluating that.
将状态空间想象成有向无环图，如果 A* 遇到不是终端节点的叶节点，那么它应该不是问题，因为该节点已经被移动到关闭列表中。
如果您的 A* 实现在遇到非终端（目标）叶节点后立即停止，并且打开列表中仍有其他节点，那么您的 A* 实现是不正确的。
Thinking of the state space like a Directed Acyclic Graph, if A* encounters a leaf node that isn't a terminal node, it shouldn't be a problem, since that node will simply have been already moved to the closed list.
If your implementation of A* immediately stops after encountering a non-terminal (goal) leaf node, and there are other nodes still on the open list, then your implementation of A* is incorrect.
如果它进入了死胡同，那应该不是什么问题。您的 A* 算法应该简单地找到具有最低启发式的下一个非阻塞节点并重新开始。
If it's led into a dead-end, it shouldn't be a problem. Your A* algorithm should simply find the next non-blocked node with the lowest heuristic and start over.