python - 5x5 滑动拼图快速低移动解决方案

Question

我试图找到一种方法，在合理的时间和 Action 中以编程方式解决 24 块滑动拼图。这是我描述的谜题中已解决状态的示例:



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

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

Answer 1

已经证明，找到最少次数的 n-Puzzle 是 NP-Complete，见 Daniel Ratner 和 Manfred Warmuth , The (n2-1)-Puzzle and Related Relocation Problems ，符号计算杂志 (1990) 10, 111-137。

在 中回顾了有趣的事实格雷厄姆·肯德尔 , A Survey of NP-Complete Puzzles , 2008:

8 谜题可以用 A* algorithm 解决;

15-puzzle 不能用 A* 算法解决，但 IDA* algorithm能够;

使用 IDA* 算法无法在合理的时间内生成 24 拼图的最佳解决方案。

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

似乎在多项式时间内有一个可用的算法可以找到次优解，参见 伊恩·帕伯里 , Solving the (n^2−1)-Puzzle with 8/3n^3 Expected Moves , 算法 2015, 8(3), 459-465。这可能是您正在寻找的。