我正在编写一个程序，使用两个启发式解决24拼图（5x5网格） . 第一个使用多少块不正确的地方，第二个使用块当前位置和所需位置之间的曼哈顿距离 .
我在程序中有不同的功能，它使用每个启发式A *和贪婪的搜索并比较结果（因此总共有4个不同的部分） .
我很好奇我的节目是否错误或是否是这个难题的限制 . 拼图是随机生成的，片段移动几次，大多数时间（约70％）找到大多数搜索的解决方案，但有时它们会失败 .
我可以理解为什么贪婪会失败，因为它不完整，但看到A *完成后，这让我相信我的代码中存在错误 .
那么有人可以告诉我这是我的想法中的错误还是谜题的限制？对不起，如果措辞不当，我会在必要时重新措辞 .
谢谢
编辑：
所以我相当肯定这是我做错了 . 这里有一个关于我如何进行搜索的逐步列表，这里有什么不对吗？
-
为条纹创建一个新列表，按照使用的任何启发式排序
-
创建一个用于存储受访节点的集合
-
将拼图的初始状态添加到边缘
-
虽然边缘不是空的..
-
弹出边缘的第一个元素
-
如果之前访问过该节点，请跳过它
-
如果节点是目标，则返回它
-
将节点添加到我们的访问集
-
展开节点并将所有后代添加回边缘
4 回答
如果你的意思是滑动拼图：如果你从工作解决方案中交换两个部分，这是可以解决的 - 所以如果你没有找到解决方案，这并不能说明算法的正确性 .
这只是你的种子有缺陷 .
编辑：如果您从解决方案开始并进行（随机）合法移动，那么正确的算法将找到解决方案（因为撤销订单是一种解决方案） .
发明它的人并不完全清楚，但Sam Loyd在19世纪后期推广了14-15拼图，这是5x5的4x4版本 .
从Wikipedia文章中，一个奇偶校验参数证明了一半可能的配置是无法解决的 . 当您的搜索失败时，您可能会遇到类似的问题 .
我将假设您的代码是正确的，并且您正确地实现了所有算法和启发式 .
这给我们留下了拼图初始化的“随机生成”部分 . 你确定你正在产生拼图的正确状态吗？如果您生成非法状态，显然不会有解决方案 .
虽然您列出的步骤看起来有点不完整，但您已经列出足够的内容以确保您的A *将在有一个解决方案时达到解决方案（尽管只要您只是简单地跳过节点就不是最佳的） .
这听起来好像你的谜题生成有缺陷或你的算法没有正确实现 . 要轻松验证您的拼图生成，请存储用于生成拼图的步骤，然后反向运行并检查结果是否为解决方案状态，然后才能将拼图发送到搜索例程 . 如果您生成了无效拼图，请转储拼图，预期步骤并查看问题所在 . 如果拼图通过并且算法失败，则至少缩小了问题所在的位置 .
如果它被证明是你的算法，请发布你实际实现的步骤的更详细的解释（不仅仅是A *如何工作，我们都知道），例如当你运行评估函数时，以及你在哪里求助充当队列的列表 . 这样可以更轻松地确定实施中的问题 .