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

Question

我正在做一个作业，我必须使用 a-star 来解决 15-puzzle (在 C 中)。

启发式函数是Manhattan distance (又名出租车距离)。

我们得到了一个示例输入/输出，其中棋盘在 22 步中解决，并且在扩展 395 节点(棋盘状态)之后(即我们必须查看395 个节点的 child )

“正确”启发式是指我的函数与用于生成样本输出并生成正确距离的函数相同。

问题是我的解决方案扩展了 400 多个节点来找到解决方案(它是最优的 22 步，但不同)。

我注意到数字会根据我生成子节点的顺序发生变化(向上、左、下、右或其他方向移动空间图 block )。

有 24 种方法可以上下左右移动空间 block 来生成 child ，我尝试了所有这些方法，但没有一种方法扩展了 395 个节点。

为什么会这样？

术语:

• 节点:每个节点都是15拼板的一个配置
• children:你可以通过移动空间实现的配置从当前节点向上、向下、向左或向右平铺

PS:如果重要的话，我正在为 open 列表使用二进制堆

谢谢

Answer 1

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

我觉得你可以试试:

• 检查您的距离加成本启发式函数。 (每个 Action 的成本为 1？您以正确的方式将每个方 block 与其正确位置的距离相加？)
• 检查你的堆。它返回正确的节点？您可以在同一步骤中拥有多少个具有相同启发值的节点？

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