algorithm - N-Puzzle with 5x5 grid，理论问题

Question

我正在编写一个程序，该程序使用两个启发式来解决 24 拼图(5x5 网格)。第一个使用错误位置的 block 数，第二个使用 block 当前位置和所需位置之间的曼哈顿距离。

我在程序中有不同的功能，它们将每个启发式算法与 A* 和贪婪搜索结合使用并比较结果(因此总共有 4 个不同的部分)。

我很好奇我的程序是否有误，或者这是否是拼图的局限性。拼图是随机生成的，棋子会被移动几次，大多数情况下 (~70%) 大多数搜索都能找到解决方案，但有时会失败。

我能理解为什么贪婪会失败，因为它不完整，但看到 A* 是完整的，这让我相信我的代码中存在错误。

所以有人可以告诉我这是我的想法错误还是拼图的局限性？抱歉，如果措辞不当，我会在必要时重新措辞。

谢谢

编辑:

所以我很确定这是我做错了什么。这是我如何进行搜索的分步列表，这里有什么问题吗？

• 为边缘创建一个新列表，按使用的启发式排序
• 创建一个集合来存储访问过的节点
• 将拼图的初始状态添加到边缘
• 虽然边缘不是空的..
  • 从边缘弹出第一个元素
  • 如果该节点之前访问过，则跳过
  • 如果节点是目标，返回它
  • 将节点添加到我们的访问集
  • 扩展节点并将所有后代添加回边缘

Answer 1

如果您的意思是滑动拼图:如果您交换一个有效解决方案的两部分，这是可以解决的 - 所以如果您没有找到解决方案，这并不能说明您的算法是否正确。

只是你的种子有缺陷。

编辑:如果您从解决方案开始并进行(随机)合法移动，那么正确的算法会找到解决方案(因为颠倒顺序是一种解决方案)。