5x5滑模快速低动解决方案

Question

我正试图找到一种方法，通过编程解决一个24件滑动拼图，在合理的时间和移动。下面是我所描述的谜题中已解决的状态的一个例子：

​

​

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

有什么特定的算法可以实现这一点吗？

Answer 1

已经证明，找到n-难题的最少移动次数是NP-完全的，见Daniel和Manfred ，https://www.sciencedirect.com/science/article/pii/S0747717108800016，符号计算杂志(1990) 10,111-137。

有趣的事实评论在格雷厄姆肯德尔，https://www.researchgate.net/publication/220174445_A_Survey_of_NP-Complete_puzzles，2008年：

• 8-难题可以用算法解决；
• 15-难题不能用A*算法求解，而算法算法可以解决；
• 使用IDA*算法无法在合理的时间内生成24难题的最优解。

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

似乎有一个在多项式时间内可用的算法可以找到次优解，见Ian ，https://www.mdpi.com/1999-4893/8/3/459，Algorithms 2015，8(3)，459-465。这可能是你要找的东西。

Answer 2

IDA*的工作原理很好，可以实现4x4的拼图，因为这是“仅”16！(20,922,789,888,000‬)可能的状态。一个5x5的谜题有25！(15,511,210,043,330,985,984,000,000)可能的状态，比这大7.4亿倍。

你需要改变策略。‘最简单’的方法解决上面一行的谜题，然后先左列。，反复，直到你有一个3x3拼图，这可以很容易地解决使用现有的技术。

解决这个难题涉及三个不同的阶段：

1. 解上一行(将第1-N-2列的部分移到适当的位置，然后将N列的部分移动到N列，将N列的部分移动到colum N，但在下面一行，完成这一行)
2. 解左列(将2-N-2行的碎片移到适当的位置，然后将N-1行的块移动到N行，N块移动到N行，而右边的一列，完成该列)
3. (剩余3列的2行)：使用A*来解决剩余部分。

所以第一阶段和第二阶段交替直到你可以运行第三阶段；在解完前五块瓷砖(第一阶段)之后，你解决了左边--其他行上最多的四块瓷砖(第二阶段)，然后剩下的拼图的最上面一行(四块，第一阶段)，然后左列(三块，第二阶段)，然后解出第三阶段。第一阶段和第二阶段基本上是相同的，只是方向不同，第二阶段第一个瓷砖已经就位了。

使用查找表很容易地解决第1和第2阶段，不需要搜索；您正在移动特定的瓷砖，而不关心其他任何事情：

• 定位所需的瓷砖
• 取瓷砖旁边的缝隙(这取决于运动方向，哪一边最好)
• 将瓷砖移到适当的位置；有标准的移动方向(垂直或水平移动5次，对角线6次)。

这并不能给出一个解决方案的最短路径，但是在没有状态搜索的情况下，问题是严格绑定的，最坏的情况是已知的。解决5x5难题的第一行和第一列最多需要427个这样的移动，下一个行和下一个列最多要移动256次。

该算法是伊恩·帕伯里，在一篇题为“于1995年首次提出的。我认为GuiPing Wang和任Li仍然描述了一种更有效的查找表方法，但是由于这篇论文还没有免费提供，所以我还没有研究过它。

Answer 3

一个可能起作用的两个字符的改变是将启发式乘以2(或其他常量)。它不再是可接受的，但所找到的解将在最优因子2的范围内。这个技巧叫做/Static加权。