5x5快速滑动拼图

Question

我正试图找到一种方法，以编程方式在合理的时间和移动量内解决一个24块的滑动拼图。下面是我正在描述的谜题中已解决状态的一个示例：

我已经发现IDA*算法可以很好地完成15个拼图（4x4网格）。IDA*算法能够在非常合理的时间内找到任何4x4滑动拼图的最小移动次数。我对这段代码进行了修改，以测试4x4滑动拼图，并通过使用PyPy进一步显著减少了运行时间。不幸的是，当这段代码被改编为5x5滑动拼图时，它的运行速度非常慢。我运行了一个多小时，最终放弃了看它完成，而在4x4网格上只运行了几秒钟。我理解这是因为需要搜索的节点数量随着网格的增加呈指数增长。然而，我并不想找到5x5滑动拼图的最佳解决方案，只想找到接近最优的解决方案。例如，如果一个给定谜题的最佳解是120步，那么我对任何少于150步并且可以在几分钟内找到的解都会感到满意。

是否有任何特定的算法可以实现这一点？

Answer 1

两个字符的更改可能会起到作用，即将启发式乘以2（或其他常数）。它不再是可接受的，但找到的解将在最优解的2倍以内。这种技巧称为加权A*/静态加权。

Answer 2

艾达*对于4x4拼图来说效果很好，因为那只是16个！(20,922,789,888,000‬) 可能的状态。一个5x5的拼图有25个！（155112100433309885984000000）可能的状态，大于740000万的因素。

您需要切换策略。“最简单”的方法首先沿着最上面的行解决难题，然后重复地沿着左边的列解决难题，直到您有一个3x3的难题，这可以使用现有技术轻松解决。

解决这个难题涉及三个不同的阶段，您可以在这三个阶段之间进行选择：

1. 求解顶行（将列1-N-2的块移动到位，然后将列N-1的块移动到列N，将列N的块移动到列N，但在下面一行，完成该行）
2. 求解左列（将第2-N-2行的工件移动到位，然后将第N-1行的工件移动到第N行，将第N行的工件移动到第N行，但向右移动一列，完成该列）
3. （剩余2行3列）：使用*解余数

因此，阶段1和2交替进行，直到可以运行阶段3；解算前5个图块（阶段1）后，解算其他行（阶段2）上最左侧的4个图块，然后解算拼图其余部分的顶行（4个图块，阶段1），然后解算左侧列（3个图块，阶段2），然后解算阶段3。第1阶段和第2阶段基本相同，只是方向不同，第2阶段的第一块瓷砖已经就位。

阶段1和2可以使用查找表轻松解决，无需搜索；您正在移动特定的磁贴，而不关心其他任何事情：

• 找到所需的磁贴
• 获取瓷砖旁边的空隙（取决于移动方向哪边最好）
• 将磁贴移动到适当的位置；有标准的移动可以向任何方向移动磁贴（垂直或水平移动5次，对角线移动6次）。

这并没有给你解决方案的最短路径，但是没有状态搜索，问题是严格约束的，并且已知的最坏情况。解决5x5难题的第一行和第一列最多需要427步，下一行和下一列需要256步。

Ian Parberry在一篇题为（n2）的实时算法的论文中首次描述了该算法− 1） -1995年的拼图。我认为，王桂平和任力提出的一种新型高效的大规模滑动谜题智能算法DSolving仍然描述了一种更高效的查找表方法，但由于该论文尚未免费提供，我还没有对其进行研究。

Answer 3

已经证明，找到n-拼图的最少移动次数是NP完全的，参见Daniel Ratner和Manfred Warmuth，《n2-1-拼图和相关重定位问题》，符号计算杂志（1990）10，111-137。

Graham Kendall回顾的有趣事实，《NP完全谜题调查》，2008年：

• 8字谜可以用A*算法解决；
• 15个谜题不能用A*算法解决，但IDA*算法可以；
• 使用IDA*算法无法在合理的时间内生成24个谜题的最佳解。

因此，停止计算以改变方法论是正确的做法。

在多项式时间中似乎有一种可用的算法可以找到次优解，参见Ian Parberry，用8/3n^3预期移动解决（n^2−1）-难题，算法2015, 8(3), 459-465。它可能是您正在寻找的。