我正在编写一个程序，它使用两个启发式来解决一个 24 谜题（5x5 网格）。第一个使用不正确位置的块数，第二个使用块当前位置和所需位置之间的曼哈顿距离。
我在程序中有不同的函数，它们将每个启发式与 A* 和贪婪搜索一起使用并比较结果（总共 4 个不同的部分）。
我很好奇我的程序是否错误，或者是否是拼图的限制。拼图是随机生成的，碎片被移动了几次，大部分时间（~70%）通过大多数搜索找到了解决方案，但有时它们会失败。
我可以理解为什么贪婪会失败，因为它不完整，但是看到 A* 是完整的，这让我相信我的代码中有错误。
那么有人可以告诉我这是我的思维错误还是谜题的限制？对不起，如果这措辞不好，我会在必要时重新措辞。
谢谢
编辑：
所以我相当肯定这是我做错了。这是我如何进行搜索的分步列表，这里有什么问题吗？
如果您的意思是滑动难题：如果您从一个工作解决方案中交换两个部分，这是可以解决的 - 因此，如果您没有找到解决方案，这并不能说明您的算法的正确性。
只是你的种子有缺陷。
编辑：如果您从解决方案开始并进行（随机）合法移动，那么正确的算法将找到解决方案（因为颠倒顺序是解决方案）。
不完全清楚是谁发明的，但 Sam Loyd 在 19 世纪后期普及了 14-15 拼图，这是 5x5 的 4x4 版本。
从Wikipedia文章中，奇偶性论证证明了一半可能的配置是无法解决的。当您的搜索失败时，您可能会遇到类似的情况。
虽然您列出的步骤似乎有点不完整，但您已经列出了足够多的内容，以确保您的 A* 将达到一个解决方案，如果有一个解决方案（尽管只要您只是跳过节点就不是最佳的）。
听起来您的拼图生成有缺陷，或者您的算法没有正确实施。为了轻松验证您的拼图生成，存储用于生成拼图的步骤，然后反向运行并检查结果是否为解决方案状态，然后再将拼图发送到搜索例程。如果您曾经生成过无效的拼图，请转储拼图和预期步骤，然后查看问题出在哪里。如果谜题通过并且算法失败，那么您至少已经缩小了问题所在。
如果结果证明是您的算法，请发布您实际执行的步骤的更详细说明（不仅仅是 A* 的工作原理，我们都知道），例如，当您运行评估函数时，以及您在哪里使用充当您的队列的列表。这将使您更容易确定实施中的问题。
我将假设您的代码是正确的，并且您正确地实现了所有算法和启发式方法。
这给我们留下了拼图初始化的“随机生成”部分。你确定你正在生成正确的拼图状态吗？如果你产生一个非法状态，显然没有办法解决。