我正在做一个作业，需要使用 A* 算法来解决一个 15 拼图 (用 C 语言实现)。

启发式函数是 曼哈顿距离 (也称为出租车距离)。

我们得到了一个输入/输出示例，其中拼图在 22 步内解决，并扩展了 395 个节点（拼图状态）（即，我们必须查看 395 个节点的子节点）。

我所说的“正确”启发式函数是指我的函数与生成示例输出时使用的函数相同，并且产生正确的距离。

问题是 我的解决方案扩展了超过 400 个节点才能找到解决方案（它是最优的 22 步，但与示例不同）。

我注意到 数字会随着我生成子节点的顺序而变化（向上、左、下、右移动空格瓷砖，或者其他方向）。

总共有 24 种方法可以向上、向下、向左和向右移动空格瓷砖以生成子节点，我尝试了所有这些方法，但没有一种方法扩展 395 个节点。

为什么会这样？

术语：

• 节点：每个节点都是 15 拼图的一个配置
• 子节点：可以通过从当前节点向上、向下、向左或向右移动空格瓷砖来实现的配置

PS：我在开放列表中使用二叉堆，如果这很重要的话

谢谢

回答：

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

我认为您可以尝试：

• 检查您的距离加成本启发式函数。（每个动作成本为 1 吗？您是否正确地计算了每个方块到其正确位置的距离之和？）
• 检查您的堆。它返回正确的节点吗？在同一步骤中，您可以拥有多少个具有相同启发式值的节点？

根据这些信息，我只能告诉您这些了。:)