尽管具有正确的启发式算法,为什么我的a-star算法会扩展太多节点？

Question

我正在做一项任务,我必须使用一颗星来解决一个15谜题(在C中).

启发函数是曼哈顿距离(又名出租车距离).

我们给出了一个示例输入/输出,其中电路板在22次移动中和扩展395个节点(电路板状态)后解决(即我们必须查看395个节点的子节点)

通过'正确'启发式,我的意思是我的功能与用于产生样本输出的功能相同并产生正确的距离.

问题是我的解决方案扩展了超过400个节点以找到解决方案(它是最佳的22个移动而不是另一个).

我注意到数字的变化取决于我生成子节点的顺序(向上,向左,向下,向右或其他方向移动空间区域).

有24种方法可以向上,向下,向左和向右移动空间磁贴以生成子项,我尝试了所有这些,但它们都没有扩展395个节点.

为什么会这样？

术语:

• node:每个节点都是15-puzzle board的配置
• children:通过从当前节点向上,向下,向左或向右移动空间磁贴可以实现的配置

PS:如果重要的话,我正在使用二进制堆作为开放列表

谢谢

Answer 1

嗯...在理想情况下，A* 不依赖于生成子项的顺序。不幸的是，如果“队列”中有两个或多个具有相同距离加成本启发值的节点，则算法可能会“随机”选择这些节点之一并找到不同的解决方案（并探索不同的搜索路径）。

我认为你可以尝试：

• 检查您的距离加成本启发式函数。（每个动作花费 1？你用正确的方式将每个方块到正确位置的距离相加？）
• 检查你的堆。它返回正确的节点？在同一步骤中可以有多少个具有相同启发值的节点？

这是我能用这些信息告诉你的唯一一件事。:)